Spring 2023-CS 539-Distributed Algorithms-ECE 526
Spring 2023-CS 539-Distributed Algorithms-ECE 526
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. Despite not having 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 important problems in distributed computing, including graph algorithms, synchronization, consensus, broadcast, state machine replication, distributed shared memory, mutual exclusion, shared objects, and threshold cryptography. The course studies foundational models and assumptions regarding shared memory vs. message passing, synchrony vs. asynchrony, reliability of message delivery, crash and Byzantine faults. The course introduces common algorithm design techniques, including synchronization, cryptographic primitives, leader election, randomization, optimistic case, 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 of the course, and many topics covered in the course will be of theoretical interest primarily at present.
Prerequisite: None required. But a course on algorithms (like CS/ECE 374 or CS 473) 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.
- Distributed Algorithms by Nancy Lynch.
- Decentralized Thoughts
Lectures: Monday and Wednesday 9:30 -- 10:45 am in 114 Transportation Building.
Lecture recordings will be available shortly after each class on our course channel on Mediaspace. But in-person attendance to lectures is recommended.
Office Hours: Monday 2 - 3 pm in 4312 Siebel Center AND after each class.
Tentative Schedule: (subject to change)
Date | Topic | Suggested Reading |
01/18 | Introduction and Models | |
01/23 | Basic Graph Algorithms | |
01/25 | Clock Synchronization | |
01/30 | Synchronizers | Complexity of Network Synchronization (Sections 1-3) |
02/01 | Causality and Logical Clocks | Time, Clocks and Ordring of Events in a Distributed System |
02/06 | The Consensus Problem | The Byzantine Generals Problem (Sections 1-3) |
02/08 | Dolev-Strong Broadcast | Dolev-Strong Authenticated Broadcast |
02/13 | Complexity Bounds of Consensus | A Simple Bivalency Proof that t-Resilient Consensus Requires t+1 Rounds |
02/15 | Fault Bounds of Consensus | |
02/20 | FLP Impossibility | Impossibility of Distributed Consensus with One Faulty Process |
02/22 | Randomized Agreement | Another advantage of free choice |
02/27 | Weak Broadcasts | Bracha's Reliable Broadcast |
03/01 | Paxos | The Part-Time Parliament Paxos Made Simple |
03/06 | PBFT | Practical Byzantine Fault Tolerance (Sections 1-4) |
03/08 | Midterm | |
03/13 | Spring Break | |
03/15 | Spring Break | |
03/20 | Distributed Shared Memory | Sharing memory robustly in message-passing systems (Sections 1-4) |
03/22 | Shared Registers | |
03/27 | Mutual Exclusion Algorithms | |
03/29 | Mutual Exclusion Bounds | |
04/03 | Atomic Snapshots | |
04/05 | Wait-free Hierarchy | Wait-free synchronization |
04/10 | TBD | |
04/12 | TBD | |
04/17 | Nakamoto Consensus | Bitcoin: A Peer-to-Peer Electronic Cash System |
04/19 | Nakamoto Consensus Proof | Bitcoin's Latency--Security Analysis Made Simple |
04/24 | Secret Sharing and Error Correction | How to share a secret |
04/26 | Threshold Cryptography | Fast and Scalable BLS Threshold Signatures |
05/01 | Multi-party Computation | |
05/03 | TBD |