Distributed Systems I

Course outline

Part I: Synchronous Distributed Systems

1. Asynchronous Distributed Systems: model, link failures, process failures, Byzantine failures.
2. Design principles of distributed algorithms, message complexity and time complexity.
3. Leader election in synchronous ring, the LCR algorithm and the HS algorithm.
4. Leader election in general networks, the FloodMax and OptFloodMax algorithms.
5. Breadth First Search (BFS) problem, the SynchBFS algorithm, variants and applications.
6. Consensus problems (without failures), the SimpleConsensus algorithm.
7. Consensus with link failures, the coordinated attack problem (deterministic and probabilistic algorithms).
8. Consensus with process failures, FloodSet algorithm, the Commit problem, the TwoPhaseCommit and ThreePhaseCommit algorithms.

Part II: Asynchronous Distributed Systems

9. Asynchronous Distributed System: the model.
10. Leader election algorithms in asynchronous ring.
11. Fundamental asynchronous distributed algorithms on trees: broadcast, flooding, echo, analysis and applications of the flooding/echo algorithm.
12. Asynchronous Breadth First Search, Dijkstra’s algorithm, Bellman-Ford algorithm.
13. Asynchronous construction of a minimum spanning tree, the Gallager-Humblet-Spira algorithm.
14. Asynchronous algorithms for the vertex coloring, independent set, and dominating set problems.
15. Order of events, “happened-before” relation, logical time, Lamport’s logical clock.
16. Shared memory distributed systems and mutual exclusion.