(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.
Five homeworks (35%), one midterm exam (30%), and a final exam (35%)
Midterm Exam on Thursday, October 3, in class.
Please follow this link for CLAS Teaching Policies and Resources
|
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) |
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)