(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,
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 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.
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 Tuesday, October 2, in class.
Please follow this link for CLAS Teaching Policies and Resources
|
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) |
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)