CS 5620 (22C:166) Distributed Systems and Algorithms

(Fall 2019) 5:00-6:15PM, 16 EPB

Instructor: Sukumar Ghosh
201P MLH, sukumar-ghosh@@uiowa.edu, 319-335-0738
Class meeting time: 5.00-6.15PM on Tuesdays and Thursdays, 16 EPB
Office Hours: 2:30PM - 4:00PM TTh or by appointment

Announcements, Prerequisites, Handouts, Homework and Exams, Lecture Notes, On-line resources,


Life in the 21st century has a growing dependence on networked services that have changed the fabric of the society. Starting from web searching, video-conferencing, stock trading and net banking, to keeping in touch with friends and peers through various kinds of social networks, network-based services play a dominant role. While networks provide the basic connectivity, the various services built on top of these networks are examples of distributed systems. The objective of this course is to understand some of the foundational issues in the design of distributed systems. Topics will include:


Sukumar Ghosh: Distributed Systems and Algorithms (Second Edition), CRC Press 2014

In addition to the textbook, we will occasionally consult the papers listed at the bhottom of this page.


Some knowledge of Operating Systems and/or Networking, Algorithms, and interest in Distributed Computing. Our goal is to learn and analyze why and how distributed systems work, why some of them fail, and how to tolerate failures and cope with various dynamic behaviors.

Homework and Exams

Five homeworks (35%), one midterm exam (30%), and a final exam (35%)
Midterm Exam on Thursday, October 3, in class.

CLAS Teaching Policies

Please follow this link for CLAS Teaching Policies and Resources

Lecture Notes

August 26-30, 2019
Week 1. Introduction and Scope
Read Chapters 1 and 3.
September 3-6, 2019
Week 2. Non-determinism, Atomicity, Fairness; Program Correctness
Read Chapter 4 and 5.
September 9-13, 2019
Week 3. Time and Clock (Read Chapter 6)
Distributed Mutual Exclusion (Read Chapter 7)
September 16-20
Week 4. Distributed Snapshot (Read Chapter 8)
September 23-27
Week 5. Global State Collection (Read Chapter 9)
September 30-October 4
Week 6. Graph Algorithms (Read Chapter 10)
October 7-18
Weeks 7, 8. Graph Algorithms continued (Read Chapter 11)
October 21-25
Week 9. Faults and fault-tolerance (Read Chapter 12)
October 28-November 1
Week 10. Distributed Consensus (Read Chapter 13)
November 4-8
Week 11. Distributed Consensus (continued) (Read Chapter 13)
November 11-15
Week 12. Distribute transactions and Atomic Commit Protocols (Read Chapter 14)
November 18-22
Week 13. Group Communication (Read Chapter 15)
December 3-6
Replicated Data Management (Read Chapter 16)
December 10-13
Blockchain Basics (Read Paper number 16)

List of Papers

1. Leslie Lamport: Time, Clocks, and the Ordering of Events in a Distributed System. Commun. ACM 21(7): 558-565 (1978) (pdf)

2. Leslie Lamport, Robert E. Shostak, Marshall C. Pease: The Byzantine Generals Problem. ACM Trans. Program. Lang. Syst. 4(3): 382-401 (1982) (pdf)

3. K. Mani Chandy, Leslie Lamport: Distributed Snapshots: Determining Global States of Distributed Systems ACM Trans. Comput. Syst. 3(1): 63-75 (1985) (pdf)

4. Anish Arora, Mohamed Gouda: Closure and Convergence: A Foundation of Fault-Toler ant Computing. IEEE Trans. Software Eng 19 (11) pp. 1015-1027, November 1993. (pdf)

5. Leslie Lamport, P.M. Melliar-Smith: Byzantine Clock Synchronization. ACM PODC 19 84. (pdf)

6. Jeffrey Dean and Sanjay Ghemawat: MapReduce: simplified data processing on large clusters. Communications of the ACM 51 (1), January 2008. (pdf)

7. Tushar Deepak Chandra and Sam Toueg: Unreliable Failure Detectors for Reliable D istributed Systems. Journal of the ACM, 43:2, March 1996, 225-267. (pdf)

8. Edsger W. Dijkstra: Self-stabilizing Systems in Spite of Distributed Control. Commun. ACM 17(11): 643-644 (1974). (pdf)

9. Michael J. Fischer, Nancy A. Lynch, Michael S. Paterson: Impossibility of Dist ributed Consensus with One Faulty Process.Vol. 32, No. 2, pp. 374-382 (1985)

10. Ion Stoica, Robert Morris, David Liben-Nowell, David R. Karger, M. Frans Kaashoek, Frank Dabek, Hari Balakrishnan: Chord: a scalable peer-to-peer lookup protocol for internet applications. IEEE/ACM Trans. Netw. 11(1): 17-32 (2003) (pdf)

11. James Aspnes, Gauri Shah: Skip graphs. SODA 2003: 384-393 (pdf)

12. Watts, D.J.; Strogatz, S.H. (1998). "Collective dynamics of 'small-world' networks.". Nature 393 (6684)

13. Leslie Lamport: Paxos made Simple. ACM SIGACT News (Distributed Computing Column) 32, 4 (No. 121, December 2001) 51-58. (pdf)

14. Baruch Awerbuch: The Complexity of Network Synchronization. Journal of ACM (1985) (pdf)

15. Diego Ongaro, John K. Ousterhout: In Search of an Understandable Consensus Algorithm. USENIX Annual Technical Conference 2014: 305-319 (pdf)

16. Satoshi Nakamoto: Bitcoin: A Peer-to-Peer Electronic Cash System (pdf)