Outline for February 13, 2001
- Greetings and felicitations!
- Suzuki-Kasami's broadcast protocol
- uses sequence numbers, not clocks
- token has sequence numbers, associated queue
- how to handle stale requests? token's sequence number too high
- Raymond's tree-based protocol
- think of token as at root of tree, root moves around
- Distributed Agreement Protocols: system model
- synchronous vs. asynchronous
- different types of failure (crash, omission, malicious)
- Classification: agreement (on value), validity (the right value)
- Byzantine problem (all agree, initial value of source); review Byzantine Generals' problem
- consensus problem (all agree, if initial value of nodes is same, the final value is that value)
- interactive consistency problem (all agree on same vector, if ith processor non-faulty, ith element of vector is the value of that node)
- Solution to Byzantine Problem
- Can show: if 3m+1 processors, at most m can be faulty or agreement cannot be reached.
- Demonstration with 3 processors.
- Lamport-Shostak-Pease algorithm
- Application: clock synchronization in the face of faults
- interactive convergence algorithm
- interactive consistency algorithm
The handouts do not translate into HTML well because of the notations.
the PDF or Postscript version from the class home page.
Office: 3059 Engineering Unit II
Phone: +1 (530) 752-8060
Fax: +1 (530) 752-4767
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.
Page last modified on 2/12/2001