Lesson 31 / 33
Cheat Sheet: Everything on One Page
Recall the key definitions, numbers and rules of consensus in one pass before an exam or interview.
By Rahul Agarwal · 15 years in web development
The one-page summary
Models: crash-recovery nodes, unreliable network, partial synchrony; Byzantine needs 3f + 1, crash needs 2f + 1. Time: never order events by wall clocks across nodes; Lamport clocks give a causal total order, vector clocks detect concurrency. Quorums: W + R > N for overlap; consensus uses majorities, and any two majorities intersect. Consensus: agreement, validity, termination; FLP forbids guaranteed termination in a fully asynchronous system with one crash. Paxos: Prepare(n) -> Promise (report accepted values) -> Accept(n, v) with the highest-ballot reported value -> chosen on a majority. Multi-Paxos skips phase 1 with a stable leader. Raft: follower, candidate, leader; terms as a logical clock; RequestVote with the up-to-date check; AppendEntries with prevLogIndex/prevLogTerm; commit only current-term entries by counting; single-server membership changes; snapshots with InstallSnapshot; ReadIndex for linearizable reads; Pre-Vote and CheckQuorum for stability. Practice: odd cluster sizes, fsync before replying, fencing tokens at the resource.
How to revise this course
Re-read the cheat sheet, rehearse the common interview questions aloud, then test yourself with the mixed self-check.
Numbers worth memorising
3 nodes tolerate 1 crash, 5 tolerate 2, 7 tolerate 3. BFT: 4 tolerate 1, 7 tolerate 2. 2PC needs every participant; consensus needs a majority. Raft paper example election timeout: 150-300 ms, randomised.
Quick check: Which pairing is correct?
- Vector clocks: detect concurrent events; Lamport clocks: total order consistent with causality
- Lamport clocks: detect concurrent events; vector clocks: wall-clock order
- Both give the real-time order of events
- Neither respects happens-before
Answer
Vector clocks: detect concurrent events; Lamport clocks: total order consistent with causality — Lamport clocks respect causality and can be made a total order with tie-breaking, but cannot prove concurrency; vector clocks can.