Advanced Distributed Systems #Raft #Paxos #quorum #leader-election

Consensus Algorithms

5 exercises — master consensus algorithm vocabulary: Raft vs Paxos, leader election, log replication, quorum calculation, log compaction via snapshots, and the pre-vote extension.

0 / 5 completed

Consensus algorithm quick reference

Raft — consensus via leader election + log replication + safety. Designed for understandability.
Multi-Paxos — equivalent guarantees, but less prescriptive implementation. Harder to implement correctly.
Term — Raft's monotonic epoch; a new term begins with each election attempt.
Quorum = ⌊n/2⌋ + 1. For 5 nodes: quorum = 3, fault tolerance = 2.
Commit — a log entry is committed when replicated to a quorum of nodes.
Log compaction — snapshotting state machine; discards already-applied log entries.
Pre-vote — partitioned nodes check election viability before incrementing the term (prevents term inflation).

1 / 5

A senior engineer says: "We're using Raft for leader election and log replication in our key-value store. Why Raft specifically, not Paxos?"

What's the key difference?

Raft = same guarantees as Paxos, but explicitly designed to be understandable and straightforward to implement correctly.

What consensus algorithms solve:
A set of nodes must agree on a single value (or a sequence of values — a log) even if some nodes crash. They must satisfy:
• Safety — all nodes that decide, decide the same value
• Liveness — given enough time and message delivery, a decision is eventually reached
• Both Raft and Paxos tolerate up to ⌊(n-1)/2⌋ crash-fail faults in a cluster of n nodes

Raft's three sub-problems:

Sub-problem	Mechanism
Leader election	Randomised election timeouts → candidates request votes from quorum → term-based leadership
Log replication	Leader accepts writes → appends to log → replicates to followers → commits when majority acknowledge
Safety	Election restriction: candidates must have up-to-date log; only one leader per term

Raft key concepts:
• Term — monotonically increasing epoch number; each election starts a new term
• Log index + term — uniquely identifies a log entry; used to detect log inconsistencies
• Commit index — the highest log entry acknowledged by a quorum; safe to apply to the state machine
• Leader completeness property — a leader always has all committed entries; followers' logs can lag

Why Paxos is harder:
• Multi-Paxos (for log replication) requires many implementation choices not specified by the paper
• Leader "distinguished proposer" election is underspecified
• Handling log gaps and leadership recovery is left as an exercise
• Real-world Paxos: Chubby (Google), Zookeeper ZAB (Paxos-like), Spanner

Real-world Raft: etcd (Kubernetes), CockroachDB, TiKV, Consul

Key vocabulary:
• Raft — consensus protocol decomposed into leader election, log replication, and safety; designed for understandability
• Multi-Paxos — extension of Paxos for replicated logs; correct but leaves many design choices unspecified
• Term — Raft's epoch number; a new term begins with each election attempt
• Quorum — majority of nodes (⌊n/2⌋ + 1); required for election and commit

2 / 5

An interviewer asks: "We have a 5-node Raft cluster. How many nodes can fail before the cluster stops accepting writes? And what happens to reads during that time?"

Quorum = ⌊n/2⌋ + 1. For 5 nodes, quorum = 3. Fault tolerance = 5 - 3 = 2 failures.

Quorum mathematics:
$$ ext{Quorum} = lfloor n/2 floor + 1$$ $$ ext{Fault tolerance} = n - ext{Quorum} = lfloor (n-1)/2 floor$$

Cluster size	Quorum	Can tolerate
3	2	1 failure
5	3	2 failures
7	4	3 failures

What happens during leader failure:
1. Leader stops sending heartbeats
2. Followers' election timers expire (randomised 150-300ms in Raft)
3. A candidate increments its term and requests votes
4. First candidate to get a quorum of votes becomes the new leader
5. Downtime ≈ election timeout duration (typically 200-500ms in LAN environments)

Read semantics during failure:
• Linearizable reads — require leader confirmation; blocked during election
• Stale (follower) reads — follower may serve reads from its local log, even if slightly behind leader. Returns stale data but may be available during leader election.
• Read-your-writes — requires routing reads through the leader or using read index mechanism (Raft ReadIndex)

Why even cluster sizes are discouraged:
Adding a 6th node raises quorum to 4 — same fault tolerance as 5 nodes (2 failures) but one more node to manage. Odd clusters are optimal: 5-node is standard for critical services.

Key vocabulary:
• Quorum — minimum number of nodes that must participate for a decision to be valid
• Leader election — process by which a Raft cluster selects a new leader after leader failure
• Linearizable read — a read that is guaranteed to reflect the most recently committed write
• Stale read — a follower read that may return data not yet reflecting the latest committed write

3 / 5

A team is designing a distributed database and debates whether to use leader-based replication (like Raft) or leaderless replication (like Dynamo-style quorum reads/writes). What are the key trade-offs?

Leader-based = strong consistency at the cost of write bottleneck + election downtime. Leaderless = high availability at the cost of conflict resolution complexity.

Leader-based replication (Raft, Multi-Paxos):
• All writes go through the elected leader
• Leader serialises writes → total order → linearizable reads from leader
• Commit = acknowledged by quorum → consensus on every write
• Use cases: coordination services (etcd, Zookeeper), financial ledgers, configuration stores

Leaderless replication (Dynamo-style):
• Clients send writes to W nodes (write quorum); reads to R nodes
• If W + R > N, read quorum overlaps write quorum → can detect latest write
• No leader election downtime; any node can serve reads and writes
• Concurrent writes to different nodes can create conflicts → need resolution strategy

Conflict resolution strategies:
• Last-Write-Wins (LWW) — highest timestamp wins; fast but data loss possible
• CRDTs (Conflict-free Replicated Data Types) — algebraic data structures that merge automatically without conflicts (counters, sets with add/remove semantics)
• Vector clocks — detect causal ordering; expose conflicts to the application for resolution
• Multi-version concurrency — keep all versions; reconcile at read time or via explicit merge

Real-world examples:

System	Type	Conflict resolution
etcd	Leader-based (Raft)	No conflicts (total order)
DynamoDB	Leaderless	LWW by default; conditional writes
Cassandra	Leaderless	LWW; tunable consistency (ONE/QUORUM/ALL)
Riak	Leaderless	Vector clocks; CRDTs

Key vocabulary:
• Leader-based replication — all writes routed through a single elected leader for total ordering
• Leaderless replication — any node accepts writes; consistency achieved through overlapping read/write quorums
• W, R, N — number of write acknowledgements required, read replicas queried, total replicas respectively
• CRDT — Conflict-free Replicated Data Type; data structure that merges concurrent updates without conflicts

4 / 5

An architect says: "We need to understand Raft's log compaction mechanism. Without it, the replicated log grows unbounded. How does Raft handle this?"

Snapshotting allows Raft to discard log entries that are already reflected in the state machine, bounding log growth.

Log compaction via snapshots:

Before compaction:
  Log: [idx:1 set x=1][idx:2 del x][idx:3 set y=5][idx:4 set z=3] ...
       ^committed^

After snapshot at idx 4:
  Snapshot: { state: {y:5, z:3}, lastIndex:4, lastTerm:2 }
  Log: [idx:5 set x=10] ...   ← only entries after snapshot retained

Snapshot contents:
• Serialised state machine state (the current value of all data)
• lastIncludedIndex — the last log index reflected in the snapshot
• lastIncludedTerm — the term of that entry; needed for safety checks on subsequent AppendEntries
• Configuration (cluster membership at snapshot time)

InstallSnapshot RPC:
When a follower is so far behind that the leader has already discarded the entries it needs:
1. Leader sends snapshot via InstallSnapshot RPC (may require multiple chunks for large snapshots)
2. Follower loads the snapshot into its state machine, replacing all current state
3. Follower updates lastIncludedIndex/Term and discards its log up to that point
4. Normal log replication resumes from the snapshot point forward

Who triggers snapshots?
Each node independently decides when to snapshot (typically: log exceeds N MB, or after N applied entries). The snapshot is not coordinated across nodes — each node snapshots independently. This is safe because snapshots are derived from committed (applied) state.

Real-world example — etcd:
etcd defaults to snapshotting every 10,000 applied entries (configurable via --snapshot-count). The snapshot file stores the current key-value store state serialised as protobuf.

Key vocabulary:
• Log compaction — the process of discarding old replicated log entries to prevent unbounded log growth
• Snapshot — a serialised point-in-time image of the state machine; replaces the compacted log entries
• InstallSnapshot RPC — Raft mechanism for bringing a severely lagging follower up to date via state transfer instead of log replay
• lastIncludedIndex / lastIncludedTerm — metadata stored in the snapshot allowing safety verification of subsequent log entries

5 / 5

A distributed systems engineer describes a scenario: "During a network partition, the minority partition's nodes keep incrementing their term number, trying to elect a leader. When the partition heals, these nodes have a higher term than the real leader — causing an unwanted leader change."

How does Raft handle this, and what is the pre-vote extension?

Pre-vote prevents "term inflation" — partitioned minority nodes incrementing the term counter without actually being able to win, then disrupting the live cluster when partitions heal.

The original problem:

Cluster: A, B, C, D, E (5 nodes)
Partition: {A, B} | {C, D, E}
Leader: C (running with term 5, quorum with D, E)

{A, B} cannot elect a leader (only 2 nodes; need 3 quorum)
But A's election timer fires → A increments term to 6, broadcasts RequestVote
B votes for A (term 6) → A still can't win (only 2 votes)
A increments to 7, 8, 9... until partition heals

Partition heals:
C receives message with term 9 → C steps down (stale leader protection)
New election needed → brief downtime during re-election

Pre-vote mechanism:
Before sending real RequestVote (which increments the term), candidate A first sends a pre-vote:
• "If I were to start an election, would you vote for me?"
• Does NOT increment the term number
• Other nodes respond with whether they have heard from the current leader recently (within election timeout)
• If A cannot get pre-votes from a quorum → A knows it's in a minority partition → does NOT start a real election and does NOT increment its term

Result: when the partition heals, A's term is still 5, not 9 — no disruption to the existing leader.

Other Raft liveness improvements:
• Check quorum — leaders periodically verify they can still reach a quorum of followers. If not, they step down voluntarily (prevents split-brain where a partitioned leader thinks it's still active).
• Leadership transfer — graceful, intentional leader transfer (e.g., before leader shutdown) using a RequestVote with special flag.

Key vocabulary:
• Term inflation — a partitioned node incrementing its term counter without winning an election, poisoning the term space
• Pre-vote — Raft extension where a candidate checks viability before starting a real election; prevents term inflation
• Check quorum — Raft extension where the leader periodically verifies quorum reachability; steps down if unreachable
• Leader step-down — Raft safety rule: a leader that receives a higher-term message must immediately revert to follower