Topic 1. Models of distributed systems:
- Two generals and Byzantium generals problems
- System models of network, node crash and timing behavior
- Availability and Fault Tolerance
Topic 2. Time, clocks and ordering:
- Usage of physical time for ordering
- Usage of logical time ordering
- Happens-before and causality relation
Topic 3. Logical Time and Broadcast protocols:
- Lamport clocks
- Vector clocks
- Broadcast ordering models and implementations: FIFO, causal, total order, etc…
- Gossip protocols
Topic 4. Replication:
- Retrying state updated
- Idempotence
- Reconciliation
- Concurrent writes
- State machine replication
Topic 5. Quorums:
- Quorums fault tolerance scheme
- Linearizable fault tolerant register implementation
Topic 6. Strong Eventual Consistency and Conflict-free Replicated Data Types:
- Convergent Replicated Data Types
- Commutative Replicated Data Types
- Complex CRDTs: texts, graphs, etc…
- Collaboration Software
Topic 7. Eventual Consistency (several lectures):
- CAP theorem
- Formal model of histories, visibility and arbitration order on events
- Session guarantees
- Eventual, PRAM, Causal, Sequential and Strong Consistency and their relations
- Return-Value consistency
- Key concepts of implementations of counters, registers and key-value stores with different consistency guarantees with examples
- Algebraic proofs that such implementations satisfy consistency guarantees
Topic 8. Consensus (several lectures):
- FLP theorem
- Problem Statement
- RAFT
- PAXOS
- Improvements
Topic 9. Formal verification of distributed systems algorithms via TLA+
Topic 10. Modern blockchain systems:
- Consensus algorithms and its verifications:
- Proof-of-work
- Proof-of-stake
- Smart contracts