Consensus

In a distributed system you have many machines that each hold their own copy of some state. If a client writes a value, every machine needs to end up agreeing on that value and on the order it happened relative to other writes. Consensus is the agreement procedure that makes this possible. Once a value is decided, every correct node sees the same decision and never changes its mind.

A correct consensus protocol has to guarantee three things at once. Agreement: no two nodes decide on different values. Validity: the value decided was actually proposed by some node, not made up. Termination: every node that stays up eventually decides. Getting all three while machines crash and the network drops or delays packets is the hard part.

The reason this is famously difficult is the FLP result from 1985, which proved that in a fully asynchronous network you cannot guarantee all three properties if even one node can crash. Real systems get around this by assuming the network is mostly timely most of the time, using timeouts and leader elections to make progress, and only sacrificing liveness, never safety, during the bad periods.

Most production systems use a leader-based protocol, with Raft and Multi-Paxos being the two common choices. One node is elected leader. Clients send writes to the leader, the leader appends the write to its log and forwards it to the followers. Once a majority of nodes have stored the entry, the leader marks it committed and tells everyone. Because every commit requires a majority, no two conflicting values can both be committed.

The majority rule is the heart of it. With 5 nodes you need 3 to agree, so the system survives 2 failures. Any two majorities of 5 nodes must overlap in at least one node, and that overlap is what prevents split decisions. This is why consensus clusters almost always run an odd number of nodes: 3, 5, or 7.

When the leader crashes, followers stop hearing heartbeats, a timeout fires, and they hold an election to pick a new leader. The protocol uses term numbers or ballot numbers so that an old leader that wakes up cannot overwrite decisions made after it left. A node will only vote for a candidate whose log is at least as up to date as its own, which guarantees no committed entry is ever lost.

Newer protocols like EPaxos and Raft variants reduce the cost in different ways, for example by letting any node accept writes when operations do not conflict, or by batching many client requests into one round of agreement to raise throughput.

Use consensus when correctness is more important than raw speed and you cannot tolerate two nodes disagreeing: leader election, distributed locks, configuration that everyone must read identically, and the metadata layer of a database. It is the tool for the small, critical state that everything else depends on.

The cost is latency and throughput. Every committed write needs at least one round trip to a majority of nodes. If your nodes sit in different regions, that round trip can be 50 to 150 milliseconds, so a single global consensus group rarely handles more than a few thousand writes per second. Reads can be faster if you accept reading from the leader or allow slightly stale follower reads.

Because of these limits, large systems do not run all their data through one consensus group. They shard the data into many independent groups, each running its own Raft or Paxos instance, so the consensus cost stays bounded per shard while total throughput scales out. They also keep the consensus layer small and push bulk data into systems that use cheaper replication.

A common mistake is using consensus where you do not need strong agreement. If eventual consistency is acceptable, gossip or asynchronous replication is far cheaper and avoids the latency floor that a majority round trip imposes.

Take a distributed lock service backed by a 5-node cluster. A client wants exclusive access to a resource, so it asks the cluster to create a lock key. That request goes to the leader, which proposes the write to the other four nodes. Once 3 of the 5 have persisted it, the lock is committed and the client gets the lock. No other client can be told it holds the same lock, because any competing write would need its own majority and the majorities would collide.

Now the leader machine loses power. The other four nodes stop getting heartbeats, time out after a few hundred milliseconds, and elect a new leader from among themselves. Because the new leader is chosen only from nodes that had the latest committed log, the lock state survives the failover. The client may see a brief pause but never sees the lock granted twice.

This is exactly how Apache ZooKeeper and etcd behave in practice, and it is why Kubernetes stores its entire cluster state in etcd: the control plane needs every component to read the same authoritative view of what should be running.