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

(Fall 2018) 12:30-1:45PM, 61SH


Instructor: Sukumar Ghosh
201P MLH, sukumar-ghosh@@uiowa.edu, 319-335-0738
Class meeting time: 12.30-1.45PM on Tuesdays and Thursdays, 61 SH
Office Hours: 3:00PM - 4:30PM TTh or by appointment

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


Objective

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:

Textbook

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

In addition to the textbook, we may occasionally consult the following books as references:

[1] Dollimore, Tim Kindberg, George Coulouris: Distributed Systems: Concepts and Design [5th Edition], Addison-Wesley 2012
[2] Maarten van Steen, Andrew Tannenbaum: Distributed Systems (3rd Edition), Pearson 2017
[3] Nancy Lynch : Distributed Algorithms. Morgan Kaufmann 1996

The reference books should be available in the library.

Prerequisites

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 Tuesday, October 2, in class.

CLAS Teaching Policies

Please follow this link for CLAS Teaching Policies and Resources

Lecture Notes

August 20-24, 2018
Week 1. Introduction and Scope
Read Chapters 1 and 3.
August 27-31, 2018
Week 2. Atomicity, Non-determinism, Fairness
Read Chapters 4 and 5.
September 4-7, 2018
Week 3. Time and Clock
Read Chapter 6.
September 10-14, 2018
Week 4. Distributed Mutual Exclusion
Read Chapter 7.
September 17-21, 2018
Week 5. Distributed Snapshot
Read Chapter 8.
September 24-28, 2018
Week 6. Global State Collection
Read Chapter 9.
October 1-12, 2018
Week 7-8. Graph Algorithms
Read Chapter 10.
October 15-26, 2018
Weeks 9-10. Minimum Spanning Tree, Leader Election, Synchronizers
Read Chapter 11.
October 29-November 2, 2018
Week 11. Faults and Fault-tolerance
Read Chapter 12.
November 5-9, 2018
Week 12. Distributed Consensus
Read Chapter 13.
November 12-16, 2018
Week 13. More on Distributed Consensus
Read Chapter 13.
November 26-30, 2018
Week 14. Group communication (Read Chapter 15)
Replication (Read Chapter 16)
November 26-30, 2018
Week 15. Distributed Transactions (Read Chapter 16)
Raft Consensus (slides borrowed from the authors' original presentation)

Online resources

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. Jon Kleinberg. The small-world phenomenon: an algorithm perspective (2000) (pdf)

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

15. Hector Garcia-Molina: Elections in a Distributed Computing System. IEEE Trans. Computers (1982) (pdf)

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

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