Fall 2025-CS 539-ECE 526-Distributed 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. 

Distributed Algorithms (CS539) vs. Distributed Systems (CS425): If you are wondering how to choose between these two classes or if you should take both, here is some information for you. CS425 covers basic concepts ranging from algorithmics to systems design principles that underlie distributed systems, especially those deployed in the industry. CS539 focuses on the theoretical underpinnings of distributed algorithms with an emphasis on their formal modeling, rigorous proofs, and fundamental limits. Neither course is a prerequisite for the other. The courses have a small overlap for the sake of continuity so that you can (if you wish) take both courses in either order and still benefit from each course. Take CS425 first if you want an intro course to distributed systems. Take CS539 first if you love doing algorithmics and proofs. 

Grading: four problem sets 60%; midterm 15%, final exams 20%; class participation 5%.    

Resources: No required textbook. The following textbooks and online resources may be helpful.

Lectures: Monday/Wednesday 3:30 pm -- 4:50 pm in 2406 Siebel Center for Computer Science.

Office Hours: Wednesday 3 to 3:30 pm in 4312 Siebel Center AND after each class in the lecture room.

Tentative Schedule: (subject to change)

Date Topic Suggested Reading (optional)
08/25 IntroductionDownload Introduction
08/27 Leader Election in a RingDownload Leader Election in a Ring An Improved Algorithm for Decentralized Extrema-Finding in Circular Configurations of ProcessesLinks to an external site. 
09/01 No Class (Labor Day)
09/03 Basic Graph Algorithms
09/08 Synchronization Complexity of Network SynchronizationLinks to an external site (Sections 1-3)
09/10 Causality, Logical Clocks, Global States
Download Clock Synchronization		 Time, Clocks and Ordring of Events in a Distributed System
09/15 Common Knowledge
Download Synchronizers		 Knowledge and common knowledge in a distributed environment
09/17 Introduction to Consensus
Download Causality, Logical Clocks, and Global States		 The Byzantine Generals Problem (Sections 1-3)
09/22 Time Bounds of Consensus Simple Bivalency Proof that t-Resilient Consensus Requires t+1 Rounds
09/24 Asynchrony and FLP Impossibility of Distributed Consensus with One Faulty Process     Another advantage of free choice
09/29 Partial Synchrony and Paxos
Download Time Bounds of Consensus		 Partial synchronyLinks to an external site.     The Part-Time Parliament      Paxos Made Simple
10/01 Distributed Shared Memory
Download FLP Impossibility		 Sharing memory robustly in message-passing systems (Sections 1-4)
10/06 Shared Registers
Download Randomized Agreement
10/08 Review
Download Partial Synchrony and Paxos
10/13 No Class (extra office hour)  
10/15 Midterm  
10/20 Mutual Exclusion
Download Distributed Shared Memory		 Peterson's Mutual Exclusion Algorithm     Bakery Algorithm
10/22 Mutual Exclusion
Download Shared Registers		 Mellor-Crummey and Scott Mutual Exclusion Algorithm
10/27 Wait-free Hierarchy
Download Mutual Exclusion		 Wait-free synchronization
Links to an external site.
10/29 Byzantine Broadcast and Agreement Dolev-Strong Authenticated Broadcast     Bracha's Reliable Broadcast
11/03 PBFT
Download Mutual Exclusion		 Links to an external site.Practical Byzantine Fault Tolerance (Sections 1-4)
Links to an external site.
11/05 Tendermint and Simplex
Download Wait-free Hierarchy		 From Tendermint to Simplex
11/10 Fault Tolerance Bounds
Download Byzantine Broadcast		  
11/12 Canceled
Download Reliable Broadcast
Links to an external site.
11/17 Nakamoto Consensus
Download PBFT		 Bitcoin: A Peer-to-Peer Electronic Cash System      Bitcoin's Latency--Security Analysis Made Simple
11/19 Secret Sharing and Threshold Cryptography
Download Fault Tolerance Bounds		 How to Share a Secret
11/24 No Class (Fall Break)
11/26 No Class (Fall Break)
12/01 Verifiable Secret Sharing
Download Communication Bounds of Consensus		 Verifiable Secret Sharing Simplified
Links to an external site.
12/03 Multi-party Computation
12/08 No Class (extra office hour)
12/10 Final Exam
Public Domain This course content is offered under a Public Domain license. Content in this course can be considered under this license unless otherwise noted.