Consensus Problem¶

Multiple nodes agreeing on a single value despite failures is the fundamental coordination primitive in distributed systems - all higher-level coordination (leader election, atomic broadcast, distributed transactions) reduces to consensus.

Tension Addressed¶

Agreement vs. Progress

Recognizable As¶

Leader election protocols; distributed locks; atomic commit; total order broadcast; configuration management; membership protocols

Canonical Sources¶

Lamport, "The Part-Time Parliament" (Paxos) (1998); Ongaro & Ousterhout, "In Search of an Understandable Consensus Algorithm" (Raft) (2014); Chandra & Toueg, "Unreliable Failure Detectors for Reliable Distributed Systems" (1996)

Transfers To¶

Distributed databases, cluster coordination, blockchain, distributed configuration, service discovery

Consensus is difficult not because of complexity but because of fundamental impossibility results. Any consensus protocol must balance three properties: agreement (nodes decide same value), validity (decided value was proposed), termination (decision eventually happens). FLP proves you cannot guarantee all three.