Distributed consensus is the problem of making a collection of separate processes agree on a single value, even when some of them fail and messages between them are delayed, reordered, or lost. It is the foundation beneath replicated databases, configuration stores, leader election, and coordination services: whenever several machines must act as if they were one consistent system, they need a way to agree.
The problem is harder than it first appears. In their 1985 paper “Impossibility of Distributed Consensus with One Faulty Process,” Michael Fischer, Nancy Lynch, and Michael Paterson proved that in a fully asynchronous system, no deterministic protocol can guarantee that every non-faulty process reaches agreement if even a single process may crash. This result, known as FLP, shows that consensus cannot be both always safe and always guaranteed to finish when timing makes a crashed process indistinguishable from a slow one.
Practical consensus algorithms work within that limit. Leslie Lamport’s Paxos, described in “The Part-Time Parliament,” and the Raft algorithm of Diego Ongaro and John Ousterhout both keep agreement safe at all times and make progress whenever the network behaves well enough, sidestepping the impossibility result by relaxing the guarantee of liveness rather than safety.
Consensus is what lets the rest of a distributed system pretend to be a single reliable machine. Once a group of nodes can agree on an ordered sequence of values, they can use that agreement to drive replication, elect leaders, and recover from failures without contradicting one another.