Fall 2017: CS 553 (Call no 39828) Distributed Computing Systems


Instructor: Ajay Kshemkalyani
Email: ajay@uic.edu
Class meeting times: T and R 2:00-3:15pm
Room: LC A5
Office Hours in 915 SEO: T 5:00 - 6:00pm, and by appointment

Course Description

  1. Models: synchronous/asynchronous; shared memory/message-passing
  2. Global states and snapshots; time models and clock synchronization
  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 (applications to multicore architectures)
  9. Checkpointing, rollback recovery; distributed debugging
  10. Agreement and consensus (with malicious and non-malicious process behavior)
  11. Failure detectors
  12. Self-stabilizing systems
  13. Peer-to-peer systems, e.g., Chord, Tapestry, Content-Addressible Network, BitTorrent
  14. other current topics, e.g., sensor networks
See detailed table of contents of the textbook below by going to the link at Cambridge University Press or Amazon. This course focuses on distributed algorithms and theoretical principles. By the end of the course, you will be able to appreciate that these algorithms have wide applications in practical distributed systems.

Resources

  1. Textbook: Distributed Computing: Principles, Algorithms, and Systems, by Kshemkalyani and Singhal, Cambridge University Press, March 2011 edition
    South Asian reprint edition, Dec 2010 ISBN-10: 1107648904, ISBN-13: 978-1107648906
  2. Course notes are here
  3. An Overview Chart
  4. Winners of the Dijkstra Award for Most Influential Paper in Distributed Computing, 2000-.
  5. Selected papers and other material from the literature will be posted on the web or distributed in class.
  6. Suggested Topics and Papers for class presentation (tentative list)
    1. Chapter 13 (Checkpointing)
    2. Self-Stabilization:
      E.W. Dijkstra, Self-stabilizing systems in spite of distributed control, Communications of the ACM, vol. 17, no. 11, pp. 643-644, Nov. 1974.
      plus Chapter 17 (Self-stabilization)
    3. Failure Detectors:
      M. Raynal, A Short Introduction to Failure Detectors for Asynchronous Distributed Systems, ACM SIGACT News Distributed Computing Column 17. Vol 36(1), (134, March 2005).
      plus Chapter 15 (Failure Detectors)
    4. Paxos:
      L. Lamport, Paxos Made Simple, ACM SIGACT News (Distributed Computing Column) 32, 4 (121, December 2001) 51-58.
      W. Bolosky et al, Paxos replicated state machines as the basis of a high-performance data store, NSDI 2011
    5. Hadoop and Mapreduce:
      J. Dean and S. Ghemawat, MapReduce: Simplified Data Processing on Large Clusters, OSDI'04: Sixth Symposium on Operating System Design and Implementation, San Francisco, CA, December, 2004.
      plus Hadoop
    6. Cloud Computing
    7. Snapshot Isolation for distributed databases
    8. Transactional Memory - software and hardware
    9. Concurrent Data Structures
    10. Conflict-free Replicated Data Types (CRDTs)

Course Structure and Class Participation

The course format will be in two parts.
  1. For the first part, the instructor will teach.
    Attendance when the instructor is teaching is not compulsory, but you must attend all the tests/exams. However, if you miss class, it is your responsibility to find out what was announced and what was covered, from other students.
  2. The second part involves active student participation and is planned as follows. Each presentation will be made by a team of 3 or 4 students, depending on the final enrollment which will be known only in the third week of class. The topics will be assigned at least 3 weeks before its presentation date.
    The class presentations will be on an assortment of topics of current interest. Each group chooses a paper/topic from a list of topics provided around the 5th week of class. This is only a starting point. Once you select a topic from the list (to be provided), you may have to identify more basic or fundamental papers on that specific topic for presentation. Pick the most basic/ fundamantal papers that are rich in new ideas. They must also have algorithmic content.
    Attendance when the student presentations are going on is compulsory.
There is also a term paper requirement.

Prerequisites

Algorithm analysis and design (cs401); operating systems (cs385); networks (cs450); or permission of the instructor.

Grading

The following is only a tentative breakup of the evaluation scheme and will be finalized after the second week of class, depending on the final enrollment in the course. The final grade is on the curve, i.e., this is relative grading - how you perform with respect to the others in the class.

Tentative course progress chart (will be updated as we progress)

Anonymized Final Grades