Theory
Distributed Consensus
For a distributed system to function correctly, nodes must agree on a single value or sequence of values. Consensus algorithms ensure this agreement despite node failures and network partitions.
- Agreement â All non-faulty nodes decide the same value
- Validity â Decided values were proposed by some node
- Termination â Algorithm eventually terminates
Consensus is the fundamental building block for replicated state machines.
The Consensus Problem
Multiple nodes must agree on a single value, even when some nodes fail or messages are delayed.
FLP Impossibility
Paxos
The foundational consensus algorithm, introduced by Leslie Lamport.
Paxos Phases
Raft
A consensus algorithm designed for understandability.
Raft Leader Election
Raft Properties
| Property | Description |
|---|---|
| Election Safety | At most one leader per term |
| Leader Append-Only | Leader never overwrites/deletes entries |
| Log Matching | If two logs contain entry with same index and term, all prior entries are identical |
| Leader Completeness | If entry committed in term T, present in leader's log for all higher terms |
| State Machine Safety | If server applied entry at index i, no other server applies different entry at i |
Raft vs Paxos
| Aspect | Raft | Paxos |
|---|---|---|
| Design goal | Understandability | Theoretical optimality |
| Leader | Strong leader required | Can work without stable leader |
| Log structure | Strict ordering | Flexible |
| Complexity | Moderate | High |
| Implementations | etcd, CockroachDB | Google Chubby, Spanner |
ZAB (ZooKeeper Atomic Broadcast)
Used by Apache ZooKeeper for coordination.
Leader Election
A critical subproblem in distributed systems.
Practice Exercises
-
Conceptual: Explain why consensus requires a majority quorum. What happens with a 3-node cluster during a network partition?
-
Raft: Trace through a Raft leader election with 5 nodes. Node 3's election timer fires first. Walk through the message exchanges.
-
Comparison: Compare Raft and Paxos for a distributed key-value store. When would you choose one over the other?
-
FLP Impossibility: The FLP result says deterministic consensus is impossible in asynchronous systems with crash failures. How do practical algorithms like Raft circumvent this?
What to Learn Next
-> CAP Theorem Consistency models, availability, and partition tolerance.
-> Data Replication Leader-follower, multi-leader, and conflict resolution.
-> Consistent Hashing Hash rings, virtual nodes, and load distribution.
-> Databases SQL vs NoSQL, indexing, replication, and sharding.
-> Service Mesh Envoy, Istio, and sidecar proxy patterns.
-> Event-Driven Architecture Event sourcing, CQRS, and saga patterns.