Fall 2009 - CS 553 (Call no 10696) Distributed Systems

Resources

• Textbook: Distributed Computing: Principles, Algorithms, and Systems, by Kshemkalyani and Singhal, Cambridge University Press, 2008.
• Course notes are here
• Selected papers and other material from the literature will be posted on the web or distributed in class.
  • P. Chandra, P. Gambhire, A. D. Kshemkalyani, Performance of the Optimal Causal Multicast Algorithm: A Statistical Analysis, IEEE Transactions on Parallel and Distributed Systems, 15(1): 40-52, January 2004.
• Implementation project

Course Description

Topics

1. Models: synchronous/asynchronous; shared memory/message-passing
2. Global states and snapshots; time models
3. Distributed graph algorithms
4. Group communication (including multicast), managing group views
5. State predicate detection
6. Reasoning with knowledge
7. Distributed mutual exclusion, distributed deadlock detection, leader election, termination detection
8. Distributed shared memory - coherence, models, register constructions, atomic snapshots
9. Checkpointing, rollback recovery; distributed debugging
10. Agreement and consensus
11. Failure detectors
12. Self-stabilizing systems
13. Peer-to-peer computing
14. other current topics

Prerequisites

Grading

• 2 Exams + final (70%)
• Implementation project and report (30%)

TENTATIVE course progress chart: Will be updated as we progress.

• Week 1: Introduction, models (Chapter 1)
• Week 2: failure models, synchronous/asynchronous communication, blocking/nonblocking communication (Chapter 1)
• Week 3: Elementary distributed algorithms (Chapter 5)
• Week 4: Elementary distributed algorithms (Chapter 5)
• Week 5: Elementary distributed algorithms (Chapter 5)
• Week 6: Model (Chapter 2); time in a distributed system (Chapter 3: exclude Sections 3.4.3, 3.5.2, 3.6, 3.8)
• Week 7: Global state recording (Chapter 4: exclude Sections 4.4 onwards), group communication (Chapter 6)
• Week 8: Midterm on Monday Oct 12.
  Causal order; total order, multicast and group communication; fault-tolerant communication specifications; layered protocol design; (Chapter 6)
• Week 9: Knowledge in distributed systems (Chapter 8)
• Week 10: Distributed Shared memory (Chapter 12)
• Week 11: Distributed Shared memory (Chapter 12)
• Week 12: Agreement and consensus (Chapter 14);
  Midterm on Wednesday Nov 11.
• Week 13: Agreement and consensus (Chapter 14)
• Week 14: Peer-to-peer systems (Chapter 18)
• Week 15: Global Predicate Detection (Chapter 11)
• Final: Thursday December 10, 10:30am-12:30pm.

Auxiliary information

Literature sources: The following is an additional listing of traditional journals and conferences that you may find useful in your literature search for your term paper. Note that there are many more journals and conferences not listed here. All can be accessed online via the library UIC portal, i.e., from a campus IP address or after logging in to the library network using your UID account.

1. IEEE Transactions on Parallel and Distributed systems (TPDS)
2. IEEE Transactions on knowledge and data engineering (TKDE)
3. Journal of Parallel and Distributed Computing (JPDC) - Elsevier
4. Distributed Computing - Springer
5. Journal of the ACM
6. Journal of Algorithms - Elsevier
7. SIAM Journal on Computing
8. Ad-Hoc Networks - Elsevier
9. ACM Symp. on Principles of Distributed Computing (PODC)
10. IEEE Symp. on Parallel and Distributed Processing (SPDP)
11. IEEE Network Computing and Applications Symposium (NCA)
12. Inter. Conference on Distributed Computing Systems (ICDCS)
13. Symoisum on DIstributed Computing (DISC)