Distributed System Design - Consensus Algorithms

Distributed consensus is the fundamental problem of getting a cluster of distributed nodes to agree on a single data value, log entry, or state machine sequence, even when some nodes or network links fail.

Core Guarantees of Consensus

Any valid consensus protocol must satisfy three fundamental properties:

1. Agreement (Safety): All non-faulty nodes must agree on the same value.
2. Validity / Integrity: The agreed value must have been proposed by one of the participating nodes.
3. Termination (Liveness): All non-faulty nodes eventually reach a decision (subject to network timing assumptions).

FLP Impossibility Result (Fischer, Lynch, Paterson, 1985): In an asynchronous network, no deterministic consensus protocol can guarantee both safety and liveness in the presence of even a single unannounced node crash. Modern protocols (Paxos, Raft) trade strict liveness during network partitions to guarantee absolute safety.

Major Consensus Protocols

1. Raft

Designed specifically for understandability and operational simplicity, decomposing consensus into explicit subproblems:

• Leader Election: Uses randomized election timeouts to elect a strong single leader.
• Log Replication: Leader accepts client writes, appends them to its write-ahead log, and broadcasts AppendEntries RPCs. An entry is committed once replicated to a majority quorum ($N/2 + 1$).
• Safety: Leaders only commit entries if they possess all previously committed entries.

2. Paxos (Multi-Paxos)

The foundational consensus algorithm by Leslie Lamport.

• Roles: Proposers, Acceptors, and Learners.
• Two Phases:
  1. Phase 1 (Prepare / Promise): Proposer selects proposal number $n$ and requests promises from a majority of Acceptors.
  2. Phase 2 (Accept / Accepted): Proposer submits the value with proposal number $n$. If a majority accepts, the value is chosen.
• Multi-Paxos streamlines steady-state throughput by electing a stable leader to bypass Phase 1 for successive log entries.

3. ZAB (ZooKeeper Atomic Broadcast)

A crash-recovery atomic broadcast protocol tailored for primary-backup systems (Apache ZooKeeper):

• Discovery & Sync Phase: Elects a primary leader and synchronizes historical state.
• Broadcast Phase: Two-phase commit (PROPOSE $\rightarrow$ ACK $\rightarrow$ COMMIT) preserving strict linearizable FIFO message ordering.

4. Byzantine Fault Tolerant (BFT) Protocols

Standard Paxos/Raft assume fail-stop (crash) faults without malicious or arbitrary behavior. BFT protocols tolerate adversarial/arbitrary messages:

• PBFT (Practical Byzantine Fault Tolerance): Tolerates up to $f$ faulty nodes in a cluster of $3f + 1$ nodes using three-phase message exchanges (Pre-prepare, Prepare, Commit).
• Nakamoto Consensus (Blockchain): Uses Proof-of-Work (PoW) or Proof-of-Stake (PoS) with longest-chain rules for decentralized, permissionless consensus.

Comparison Matrix

Protocol	Fault Model	Quorum Size	Leadership Model	Prominent Implementations
Raft	Crash Fault (CFT)	$\lfloor N/2 \rfloor + 1$ (tolerates $f$ failures out of $2f + 1$)	Strong Leader	etcd, HashiCorp Consul, CockroachDB, TiKV
Multi-Paxos	Crash Fault (CFT)	$\lfloor N/2 \rfloor + 1$	Proposer / Master	Google Chubby, Google Spanner, Apache Cassandra (LWT)
ZAB	Crash Fault (CFT)	$\lfloor N/2 \rfloor + 1$	Primary Leader	Apache ZooKeeper, ClickHouse Keeper
PBFT / Tendermint	Byzantine Fault (BFT)	$\lfloor 2N/3 \rfloor + 1$ (tolerates $f$ failures out of $3f + 1$)	Rotating Proposer	Cosmos Tendermint, Hyperledger Fabric

Practical Use Cases in Distributed Systems

1. Replicated State Machines (RSM): Ensuring all replicas process the exact same sequence of state transitions (e.g. metadata stores).
2. Distributed Locking & Coordination: Providing safe lease-based mutual exclusion (e.g. Google Chubby, etcd locks).
3. Leader Election & Split-Brain Prevention: Electing a single active primary in high-availability clusters.
4. Dynamic Cluster Membership: Safely adding or removing nodes from live clusters without downtime (joint consensus).
5. Distributed Configuration Store: Atomic, versioned rollout of system-wide configurations across thousands of microservices.