Part I: Synchronous Distributed Systems
- Asynchronous Distributed Systems: model, link failures, process failures, Byzantine failures.
- Design principles of distributed algorithms, message complexity and time complexity.
- Leader election in synchronous ring, the LCR algorithm and the HS algorithm.
- Leader election in general networks, the FloodMax and OptFloodMax algorithms.
- Breadth First Search (BFS) problem, the SynchBFS algorithm, variants and applications.
- Consensus problems (without failures), the SimpleConsensus algorithm.
- Consensus with link failures, the coordinated attack problem (deterministic and probabilistic algorithms).
- Consensus with process failures, FloodSet algorithm, the Commit problem, the TwoPhaseCommit and ThreePhaseCommit algorithms.
Part II: Asynchronous Distributed Systems
- Asynchronous Distributed System: the model.
- Leader election algorithms in asynchronous ring.
- Fundamental asynchronous distributed algorithms on trees: broadcast, flooding, echo, analysis and applications of the flooding/echo algorithm.
- Asynchronous Breadth First Search, Dijkstra’s algorithm, Bellman-Ford algorithm.
- Asynchronous construction of a minimum spanning tree, the Gallager-Humblet-Spira algorithm.
- Asynchronous algorithms for the vertex coloring, independent set, and dominating set problems.
- Order of events, “happened-before” relation, logical time, Lamport’s logical clock.
- Shared memory distributed systems and mutual exclusion.
Jun 06 2020