Distributed Consensus Algorithms are the fundamental protocols that enable multiple nodes in a distributed system to agree on a single value (or sequence of values) despite node failures, network partitions, and message delays — providing the consistency guarantees that underpin replicated databases, distributed lock services, leader election, and configuration management in every production distributed system from Google Spanner to etcd to Apache ZooKeeper.

The Consensus Problem

N nodes must agree on a value. Requirements:

• Agreement: All non-faulty nodes decide the same value.
• Validity: The decided value was proposed by some node (no invented values).
• Termination: All non-faulty nodes eventually decide (liveness).
• Fault Tolerance: Correct operation despite up to f failed nodes (crash or Byzantine). For crash failures: requires 2f+1 nodes to tolerate f failures.

Paxos (Lamport, 1989)

The foundational consensus protocol:

• Prepare Phase: Proposer sends Prepare(n) with proposal number n to all acceptors. Acceptors promise not to accept proposals with numbers < n and return any previously accepted value.
• Accept Phase: If a majority of acceptors respond, proposer sends Accept(n, v) where v is the previously accepted value with highest number (or the proposer's own value if none). Acceptors accept if they haven't promised a higher number.
• Consensus Reached: When a majority of acceptors accept the same (n, v), value v is chosen.

Multi-Paxos extends single-decree Paxos to a log of decisions: a stable leader drives consensus for each log entry without repeating the Prepare phase, achieving one round-trip per decision in the common case.

Raft (Ongaro & Ousterhout, 2014)

Designed for understandability (Paxos is notoriously difficult to implement correctly):

• Leader Election: Nodes are followers by default. If no heartbeat from leader within election timeout, a follower becomes candidate and requests votes. Wins with majority.
• Log Replication: Leader appends client commands to its log, replicates entries to followers. Entry is committed when replicated to a majority. Committed entries are applied to state machine.
• Safety: Only candidates with the most up-to-date log can win election — guarantees no committed entry is lost.

Raft is used in: etcd (Kubernetes backing store), CockroachDB, TiKV, Consul, and dozens of production systems.

Performance Characteristics

Byzantine Fault Tolerance (BFT)

Paxos and Raft assume crash failures (nodes stop but don't lie). BFT protocols (PBFT, HotStuff, Tendermint) tolerate Byzantine failures (nodes may send arbitrary/malicious messages). Require 3f+1 nodes for f Byzantine failures. Used in blockchain consensus, military/aerospace systems.

Distributed Consensus is the theoretical and practical foundation of reliable distributed systems — the algorithmic guarantee that a collection of unreliable machines can provide the illusion of a single, consistent, fault-tolerant service that never loses acknowledged data.