Distributed Consensus (Paxos/Raft)

Distributed consensus is the process by which a cluster of machines agrees on a single value or state, even if some of the machines crash or the network drops messages. It is the hardest problem in distributed systems and the foundation of strongly consistent stores. Paxos and Raft are the two dominant algorithms used to achieve it.

Consensus is required whenever a system must act as a single, highly available source of truth, such as for leader election, distributed locks, or committing distributed transactions. The fundamental rule of consensus is the majority quorum: to agree on a value, a strict majority (N/2 + 1) of the nodes must acknowledge it. If a cluster has 5 nodes, 3 must agree. This ensures that any two quorums will always overlap by at least one node, preventing split-brain scenarios.

Paxos

Paxos (by Leslie Lamport) was the first rigorously proven consensus algorithm. It achieves agreement in two phases (Prepare and Accept). While elegant in theory, basic Paxos is notoriously difficult to understand and even harder to implement correctly for a continuous stream of decisions (Multi-Paxos). Almost no two Paxos implementations are identical.

Raft

Raft was explicitly designed for understandability as a reaction to Paxos. It decomposes the consensus problem into three distinct, easier-to-manage subproblems:

• Leader Election: The cluster elects a strong leader. If the leader fails, a randomized timeout triggers a new election.
• Log Replication: The leader accepts all client writes (log entries) and streams them to the followers. Only when a majority of followers acknowledge the entry does the leader "commit" it.
• Safety: Raft guarantees that if a leader commits an entry, that entry will never be overwritten, even if leadership changes.

Consensus provides absolute safety (strong consistency) and fault tolerance at the cost of latency and availability. Because every write must wait for a network round-trip to a majority of nodes, consensus is too slow for high-throughput data paths (like a user activity feed). It is also bound by the CAP theorem: if a partition separates a cluster of 5 into a group of 2 and a group of 3, the group of 2 will halt completely because it cannot form a quorum.

• You rarely need to implement Raft or Paxos yourself. In a system design interview, propose using a coordination service like ZooKeeper or etcd, which run these algorithms under the hood.
• If asked how to survive two node failures, state that you need a cluster of 5 nodes (because N/2 + 1 = 3, leaving 2 allowed failures).
• Mention that consensus is strictly for the control plane (metadata, leader election, config) and not the data plane (high-volume user data), because it is too slow.