Spring 2012 - CS 553 (Call no 31243) Distributed Systems
Current standing spreadsheet
Instructor:
Ajay Kshemkalyani
Class meeting times: T,R 11:00-12:15am
Room: SH 303
Office Hours in 915 SEO:
T 2:00 - 3:00pm, and by appointment
- Models: synchronous/asynchronous; shared memory/message-passing
- Global states and snapshots; time models and clock synchronization
- Distributed graph algorithms
- Group communication (including multicast), managing group views
- State predicate detection
- Reasoning with knowledge
- Distributed mutual exclusion, distributed deadlock detection, leader election, termination detection
- Distributed shared memory - coherence, models, register constructions, atomic snapshots (applications to multicore architectures)
- Checkpointing, rollback recovery; distributed debugging
- Agreement and consensus (with malicious and non-malicious process behavior)
- Failure detectors
- Self-stabilizing systems
- Peer-to-peer systems, e.g., Chord, Tapestry, Content-Addressible Network, BitTorrent
- 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 theoretical principles, but will have some implementation projects, (probably) using Concurrent Java/ Java RMI/sockets.
Note, there are and have been many options to write distributed and parallel programs, from Java RMI to CORBA to MPI to OpenMP to MapReduce/ Hadoop, NetBeans, (Ruby-on-Rails, i just heard recently of) that come and go quickly with technology. The course focuses on the science principles and algorithms for distributed computing while having some understanding of how they can be implemented and engineered in a real system.
Algorithm analysis and design (cs401); operating systems (cs385); networks (cs450); or permission of the instructor.
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 (projects and /or presentations may be individual or group).
- midterm(s) + final (70%)
- Implementation projects (30%)
course progress chart (will be updated as we progress)
- Week 1 (Jan 10 -): Introduction, models (Chapter 1 full)
- Week 2 (Jan 17 -): Terminology and distributed algorithms (Chapter 5)
- Week 3 (Jan 24 -): Terminology and distributed algorithms (Chapter 5)
- Week 4 (Jan 31 -): Terminology and distributed algorithms (Chapter 5); Lab 1 assigned
- Week 5 (Feb 7 -): Model of a Distributed computation (self study) (Chapter 2);
Logical Time (Chapter 3; p 50-57, 59-62; 68-69; 78-82);
Global state recordings (Chapter 4; p 87-97)
- Week 6 (Feb 14 -): Message ordering and group communication (Chapter 6: p 189-199, 205-208, 215-221, 225-236)
- Week 7 (Feb 21 -): Message ordering and group communication
- Week 8 (Feb 28 -): Reasoning with knowledge (Chapter 8: p 282-297, 300-304); Lab 2 assigned
- Week 9 (Mar 6 -): Global predicate detection (Chapter 11: p 379-400)
- Week 10 (Mar 13 -): Global predicate detection; Distributed shared memory (Chapter 12)
- Week 11 (Mar 27 -): Distributed shared memory
- Week 12 (Apr 3 -):
- Apr 3: Midterm: syllabus - everything covered up to and including March 13 class
- Apr 5: Distributed shared memory; Consensus and agreement algorithms (Chapter 14: p 510-533; 538-539; 544-562); Lab 3 assigned
- Week 13 (Apr 10 -):
- Apr 10: Consensus and agreement algorithms
- Apr 12: Consensus and agreement algorithms
- Week 14 (Apr 17 -):
- Apr 17: Consensus and agreement algorithms
- Apr 19: Peer-to-Peer Computing and overlay graphs (Chapter 18: p 677-708)
- Week 15 (Apr 24 -):
- Apr 24: Peer-to-Peer Computing and overlay graphs
- Apr 26: Peer-to-Peer Computing and overlay graphs
Final: Monday April 30, 10:30-12:30pm. Syllabus - cumulative