Distributed Consensus

The problem of getting multiple independent processes to agree on a single value (or sequence of values) when they can only communicate by sending messages, and when messages can be delayed or processes can fail.

Why it's hard

In a single-process system, "deciding" is trivial — one process picks a value and that's it. With multiple processes, you need three properties:

• Agreement — all non-faulty processes decide on the same value
• Validity — the decided value was actually proposed by some process (no making things up)
• Termination — every non-faulty process eventually decides

The difficulty comes from uncertainty. If you send a message and get no reply, you can't tell whether the other process crashed or is just slow. This ambiguity is what makes consensus fundamentally hard in asynchronous systems — see flp-impossibility.

Where it shows up

Consensus is the core primitive underneath many systems people use without thinking about it:

• Databases: replicated databases (Postgres with streaming replication, CockroachDB, Spanner) use consensus to keep replicas in sync. When you write a row, the replicas need to agree it happened and in what order. The algorithms on the replication side of that — primary-backup, state-machine replication, atomic broadcast — are surveyed chapter by chapter in replication-theory-and-practice.
• Distributed locks: services like etcd and ZooKeeper provide locks and leader election, which are consensus problems in disguise.
• Blockchains: the entire point of a blockchain is getting untrusted nodes to agree on a transaction ledger. Bitcoin uses proof-of-work as a probabilistic consensus mechanism.
• Multi-agent LLM systems: when parallel LLM agents must produce compatible code from the same prompt, they face a consensus problem — see log-distributed-llms.

Classic algorithms

Paxos (Lamport, 1989) — the first correct consensus algorithm for asynchronous systems with crash failures. Notoriously hard to understand and implement. Most real systems use derivatives. The original papers, with commentary from people who had to implement them, are collected in concurrency-works-of-leslie-lamport — worth reading once the second-hand summaries stop answering your questions.

Raft (Ongaro & Ousterhout, 2014) — designed to be understandable. Separates consensus into leader election, log replication, and safety. Used in etcd, Consul, and many Kubernetes-adjacent tools.

PBFT (Castro & Liskov, 1999) — Practical Byzantine Fault Tolerance. Works when up to 1/3 of nodes are Byzantine. Much more expensive than crash-only algorithms because every node must communicate with every other node.

The tradeoff space

The flp-impossibility result proves you can't have all three of safety, liveness, and fault tolerance in an asynchronous system. Real systems cope by weakening one:

• Weaken liveness: Paxos/Raft can stall during network partitions but never decide wrong (most databases choose this)
• Weaken safety: some systems allow temporary inconsistency and reconcile later (eventual consistency, CRDTs)
• Add synchrony assumptions: use timeouts to detect failures, accepting that the system breaks if timing assumptions are wrong