Time, Agreement, and Causality
Slides:
- Lamport/Logical Clocks
- Synchronized Consensus, Failure Detectors
- Asynchronous Consensus, Impossibility
- Broadcast: ABCast, CBCast, GBCast
Assigned Readings:
- Monday, 2/22
- Respond on Blackboard Discussion: Leslie Lamport for "Time, Clocks, and the Ordering of Events in a Distributed System," Communications of the ACM, July 1978, 21(7):558-565.
- Wednesday, 2/24
- Respond on Blackboard Discussion: Fischer, M. J., Lynch, N. A., and Paterson, M. S. 1983. Impossibility of distributed consensus with one faulty process. In Proceedings of the 2nd ACM SIGACT-SIGMOD Symposium on Principles of Database Systems (Atlanta, Georgia, March 21 - 23, 1983). PODS '83. ACM, New York, NY, 1-7.
- Monday, 3/1
- Respond on Blackboard Discussion: Birman, K. P. and Joseph, T. A. 1987. Reliable communication in the presence of failures. ACM Trans. Comput. Syst. 5, 1 (Jan. 1987), 47-76.
- Wednesday, 3/3
- Midterm Exam, no reading assignments
Additional Reading (not assigned):
- Birman, K. and Joseph, T. 1987. Exploiting virtual synchrony in distributed systems. SIGOPS Oper. Syst. Rev. 21, 5 (Nov. 1987), 123-138.
- Kistler, J. J. and Satyanarayanan, M. 1992. Disconnected operation in the Coda File System. ACM Trans. Comput. Syst. 10, 1 (Feb. 1992), 3-25.
- Terry, D. B., Theimer, M. M., Petersen, K., Demers, A. J., Spreitzer, M. J., and Hauser, C. H. 1995. Managing update conflicts in Bayou, a weakly connected replicated storage system. In Proceedings of the Fifteenth ACM Symposium on Operating Systems Principles (Copper Mountain, Colorado, United States, December 03 - 06, 1995). M. B. Jones, Ed. SOSP '95. ACM, New York, NY, 172-182.
- Chandra, T. D. and Toueg, S. 1996. Unreliable failure detectors for reliable distributed systems. J. ACM 43, 2 (Mar. 1996), 225-267.
- Chandy, K. M. and Lamport, L. 1985. Distributed snapshots: determining global states of distributed systems. ACM Trans. Comput. Syst. 3, 1 (Feb. 1985), 63-75.