Implementing Consensus Algorithms
1. Understanding Consensus Problem
| Property | Definition |
|---|
| Agreement | All correct nodes decide same value |
| Validity | Decided value was proposed by some node |
| Termination | Every correct node eventually decides |
| Integrity | Each node decides at most once |
| FLP Result | Impossible deterministically in async with 1 crash |
2. Implementing Paxos Algorithm (basic)
| Phase | Action |
|---|
| 1a Prepare(n) | Proposer picks ballot n; sends to acceptors |
| 1b Promise(n, v?) | Acceptor promises not to accept < n; returns prior accepted |
| 2a Accept(n, v) | If majority promised, proposer sends value (highest prior or own) |
| 2b Accepted(n, v) | Acceptor accepts unless promised higher |
| Decide | Once majority accepted, value chosen |
Warning: Basic Paxos decides one value; real systems need Multi-Paxos for log replication.
3. Implementing Multi-Paxos
| Optimization | Detail |
|---|
| Stable leader | Skip Phase 1 once elected; reuse ballot |
| Per-slot decision | Each log index = one Paxos instance |
| Pipelining | Multiple slots in flight |
| Used by | Chubby, Spanner, Megastore |
4. Implementing Raft Consensus
| Component | Detail |
|---|
| Roles | Leader, Follower, Candidate |
| Term | Monotonic logical epoch |
| Election | Randomized timeout (150-300ms) → candidate |
| RPCs | RequestVote, AppendEntries |
| Used by | etcd, Consul, CockroachDB, TiKV, RethinkDB |
5. Implementing Raft Log Replication
Raft Append Entries Flow
- Leader receives client command, appends to local log
- Leader sends
AppendEntries(term, prevIndex, prevTerm, entries[], leaderCommit)
- Follower verifies log matching property; replies success/failure
- Once majority ack, leader advances commit index
- Leader notifies followers via next AppendEntries
- State machines apply committed entries in order
6. Implementing Raft Membership Changes
| Method | Detail |
|---|
| Joint consensus | Transition Cold,new requires majority in both |
| Single-server change | Add/remove one at a time (etcd default) |
| Learner role | Catches up before voting (etcd v3.4+) |
7. Understanding Viewstamped Replication
| Property | Detail |
|---|
| Predates Paxos | Liskov & Oki, 1988 |
| Views | Equivalent to Raft terms |
| Primary-backup with view changes | Similar to Raft |
| Used by | Influenced Harp, BFT variants |
8. Understanding Zab Protocol (ZooKeeper)
| Property | Detail |
|---|
| Goal | Atomic broadcast for primary-backup |
| Phases | Discovery, synchronization, broadcast |
| zxid | (epoch, counter) — total order |
| Order guarantee | FIFO from leader |
9. Handling Split-Brain Scenarios
| Mechanism | How |
|---|
| Quorum requirement | Majority needed; minority cannot commit |
| Fencing tokens | Monotonic epoch invalidates stale leader |
| STONITH | "Shoot The Other Node In The Head" — power off old leader |
| Lease + clock bound | Leader lease expires before new election |
10. Implementing Quorum-Based Consensus
| N | Quorum (⌊N/2⌋+1) | Failures Tolerated |
|---|
| 3 | 2 | 1 |
| 5 | 3 | 2 |
| 7 | 4 | 3 |
Note: Odd cluster sizes are preferred — adding an even node increases quorum without increasing fault tolerance.
11. Understanding Byzantine Fault Tolerant Consensus (PBFT)
| Property | Value |
|---|
| Assumption | Up to f byzantine nodes |
| Required nodes | 3f + 1 total |
| Phases | Pre-prepare → prepare → commit |
| Use cases | Permissioned blockchains, high-security systems |
| Variants | Tendermint, HotStuff, LibraBFT |