Fall 2024-CS 539-ECE 526-Distributed Algorithms
Distributed algorithms are algorithms designed to run on multiple processes or mutually distrusting participants, often to increase performance through parallel processing or improve resilience by tolerating faults. Without centralized control, distributed algorithms typically require delicate coordination among processes. The concurrency, non-determinism, and potential faults make distributed algorithms hard to design and analyze compared to single-process algorithms.
This course covers foundations and recent advances in distributed algorithms. The course studies fundamental problems in distributed computing, including graph algorithms, leader election, synchronization, consensus, broadcast, state machine replication, distributed shared memory, mutual exclusion, shared objects, and distributed cryptography. The course studies foundational models and assumptions regarding shared memory vs. message passing, synchrony vs. asynchrony, reliability of message delivery, crashes and Byzantine faults. The course introduces common algorithm design techniques, including synchronization, cryptographic primitives, leader election, randomization, optimistic cases, simulation, and quorums.
This is a theory/algorithm course that emphasizes formal modeling, rigorous proofs, theoretical analysis, and fundamental limits in the form of lower bounds and impossibility results. While the course also touches on practical aspects whenever applicable, it will not be a priority, and many topics covered in the course will be of theoretical interest primarily at present.
Prerequisite: None required. However, a course on algorithms (like CS/ECE 374) OR distributed systems (like CS 425 / ECE 428) is strongly recommended.
Grading: five to six problem sets 60%; midterm 15%, final exams 20%; class participation 5%.
Resources: No required textbook. The following textbooks and online resources may be helpful.
- Distributed Computing: Fundamentals, Simulations, and Advanced Topics by Hagit Attiya and Jennifer Welch.
- Notes on Theory of Distributed Systems by James Aspnes.Links to an external site.
- Distributed Algorithms by Nancy Lynch.
- Decentralized ThoughtsLinks to an external site.
Lectures: Monday and Wednesday 11 am -- 12:15 pm in 0222 Siebel Center for Computer Science.
Office Hours: Monday 10 - 11 am in 4312 Siebel Center AND after each class in the lecture room.
Tentative Schedule: (subject to change)