CS514: Intermediate Computer Systems - Topics and Readings

Here is a high-level listing of the topics we will try to cover this semester. Suggested readings are noted along with each topic.

• Introduction [M94, chptrs 1, 2].
• Global states and event ordering [M94, chptr 4] (also: [L78]; [CL85]).
  • Logical clocks.
  • Vector clocks.
  • Consistent cuts and global property detection.
• Rollback-recovery and message-logging protocols [EAWJ 02].
• Primary-backup approach [M94, chptr 8]; [vRS04].
• State machine approach [M94, chptr 7].
• Synchronization and Coordination [M94, chptr 5]; [L01].
  • 2-Phase commit.
  • 3-Phase commit.
  • Paxos.
  • Byzantine greement.
• Time services [S87].
  • Approximate agreement algorithms.
  • Byzantine clock synchronization.
• Using quorums [H86; MR98]
  • Consistency models.
  • Quorum-based services.
  • Byzantine quorum systems.
• Middleware support for distributed computing [B05, chptr 15-19].
  • Virtual synchrony.
  • Failure detection.
  • Web services.
• Naming and directory services.
• Gossip and epidemic algorithms.
• Peer to Peer Systems [AS04].

References

[AS04] Stephanos Androutsellis-Theotokis and Diomidis Spinellis. A survey of peer-to-peer content distribution technologies. ACM Computing Surveys 36, 4 (December 2004), 335 -- 371.

[B05] Kenneth P. Birman. Reliable Distributed Systems Springer-Verlag, New York (2005).

[CL85] K. Mani Chandy and Leslie Lamport. Distributed snapshots: Determining global states of distributed systems. ACM Transactions on Computer Systems 3, 1 (February 1985), 63 -- 75.

[EAWJ02] Mootaz Elnozahy, Lorenzo Alvisi, Yi-Min Wang, and David B. Johnson. A survey of rollback-recovery protocols in message-passing systems. ACM Computing Surveys 34, 3 (September 2002), 375 -- 408.

[H86] M. Herlihy. A quorum-consensus replication method for abstract data types. ACM Transactions on Computer Systems 4, 1 (February 1986), 32--53.

[L78] Leslie Lamport. Time, clocks, and the ordering of events in a distributed system. Communications of the ACM 21, 7 (July 1978), 558 -- 565.

[L01] Leslie Lamport. Paxos Made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (Whole Number 121, December 2001), 18--25.

[M94] S. Mullender (editor). Distributed Systems, Second Edition. ACM Press, Addison-Wesley Publishing Company, Reading Mass., 1994.

[MR98] D. Malkhi and M. Reiter. Byzantine quorum systems. Distributed Computing 11 4 (1998), 203--213.

[vRS04] R. van Renesse and Fred B. Schneider. Chain Replication for Supporting High Throughput and Availability. Sixth Symposium on Operating Systems Design and Implementation (OSDI '04). USENIX Association, (San Francisco, California, December 2004), 91--104.

[S87] Fred B. Schneider. Understanding protocols for Byzantine clock synchronization. Cornell University Computer Science Technical Report TR 87-859, August 1987.