Outline for February 13, 2001

1. Greetings and felicitations!
2. Suzuki-Kasami's broadcast protocol
   1. token-based
   2. uses sequence numbers, not clocks
   3. token has sequence numbers, associated queue
   4. how to handle stale requests? token's sequence number too high
3. Raymond's tree-based protocol
   1. token-based
   2. think of token as at root of tree, root moves around
4. Distributed Agreement Protocols: system model
   1. synchronous vs. asynchronous
   2. different types of failure (crash, omission, malicious)
   3. authentication
5. Classification: agreement (on value), validity (the right value)
   1. Byzantine problem (all agree, initial value of source); review Byzantine Generals' problem
   2. consensus problem (all agree, if initial value of nodes is same, the final value is that value)
   3. interactive consistency problem (all agree on same vector, if ith processor non-faulty, ith element of vector is the value of that node)
   4. relationship
6. Solution to Byzantine Problem
   1. Can show: if 3m+1 processors, at most m can be faulty or agreement cannot be reached.
   2. Demonstration with 3 processors.
   3. Lamport-Shostak-Pease algorithm
7. Application: clock synchronization in the face of faults
   1. interactive convergence algorithm
   2. interactive consistency algorithm

The handouts do not translate into HTML well because of the notations. Please download the PDF or Postscript version from the class home page.

Matt Bishop Office: 3059 Engineering Unit II Phone: +1 (530) 752-8060 Fax: +1 (530) 752-4767 Email: bishop@cs.ucdavis.edu

Copyright Matt Bishop, 2001. All federal and state copyrights reserved for all original material presented in this course through any medium, including lecture or print.