Distributed Consensus

Distributed consensus lets separate processes choose one durable result even when messages are delayed and some processes fail. It is the coordination core behind replicated state machines, metadata services, leader election, and strongly consistent storage.

The hard part is not collecting votes on a healthy network. The hard part is preserving one decision when failures hide which processes are alive and which messages will arrive later.

The problem consensus solves

Imagine three replicas that maintain the same key-value store. A client asks to set mode to safe. Every replica must apply that command in the same log position. If another replica applies mode to fast in that position, the copies no longer represent one service.

A consensus protocol controls which value or log entry becomes chosen. A useful specification separates three goals:

Agreement: correct participants do not decide different values.
Validity: the decided value satisfies the protocol's proposal rules.
Termination: correct participants eventually decide under the stated timing and failure assumptions.

Agreement and validity are safety properties. A safety violation produces a wrong result. Termination is a liveness property. A liveness failure leaves the system waiting.

This distinction explains why a minority partition usually stops accepting writes. Refusing work hurts availability, but inventing a second committed history would break safety.

From one decision to a replicated service

A single consensus instance chooses one value. A replicated state machine needs a sequence of choices:

client commands -> replicated log -> deterministic state machine -> results

Each replica applies the same committed commands in the same order. If the state machine is deterministic, each replica reaches the same state.

This pattern turns consensus into a reusable service foundation. The protocol orders commands. The application defines what those commands mean.

Consensus does not make application code deterministic. It also does not validate business facts, repair corrupted input, or make every client retry safe.

Why majorities matter

Many crash-fault consensus protocols use majority quorums. Any two majorities overlap in at least one member. That overlap carries information from an earlier decision into a later round.

For three voters, a majority is two. The cluster can lose one voter and still form a majority. For five voters, a majority is three, so it can lose two.

Adding one voter to an odd-sized cluster does not always increase fault tolerance. Both three and four voters require a majority that permits only one unavailable voter. Quorum size, placement, and correlated failures matter more than raw replica count.

A quorum is not a guarantee that the network is healthy. It is the minimum voting set the protocol uses to protect one history.

A leader-based mental model

Raft makes the common leader-based structure explicit. Time is divided into numbered terms. A candidate asks voters for support. A server grants at most one vote per term, subject to log-safety rules. A majority elects one leader for that term.

The leader accepts client commands and appends them to its log. Followers receive matching entries. Once the protocol's commit rule is met, committed entries become safe to apply to the state machine.

client -> leader -> follower logs -> commit -> apply

Heartbeats are empty replication messages that maintain authority and help followers detect a missing leader. Randomized election timeouts reduce repeated split votes.

Terms and log positions do different jobs. A term identifies a period of leadership. A log index identifies a command's position. Together they let replicas compare histories and reject stale leaders or conflicting entries.

Safety is not the same as speed

Raft and Paxos are designed so delayed or reordered messages do not create two chosen values. Their progress still depends on assumptions about communication and failure.

The FLP result shows a sharp limit. In a completely asynchronous system, no deterministic consensus protocol can guarantee termination if even one process may crash. A slow process and a failed process can look identical because there is no known message-delay bound.

Practical protocols do not discard safety to escape this result. They commonly assume partial synchrony for liveness. The network may behave unpredictably for a time, but eventually timing becomes bounded enough for a stable leader and quorum to communicate.

Timeouts therefore guide progress rather than prove failure. A timeout means the local process waited long enough to take another action. It does not prove that the remote process stopped.

Paxos and Raft

Paxos describes how proposers and acceptors choose a value across numbered proposal rounds. An acceptor's promises and accepted values prevent a later round from choosing a conflicting result. Multi-Paxos reuses stable leadership to choose a sequence of log entries efficiently.

Raft targets the same replicated-log problem with a stronger leader and a decomposed design. It separates leader election, log replication, and safety. Both families depend on intersecting quorums and durable protocol state.

Choose an implementation based on its complete protocol, verification, operational behavior, and ecosystem. The algorithm family name alone does not establish correctness.

Failure models change the protocol

Crash-fault protocols assume a failed participant stops or becomes unreachable. They do not tolerate a voter that sends conflicting, malicious, or arbitrarily corrupted messages while still participating.

Byzantine fault tolerance addresses arbitrary faulty behavior. PBFT is a state-machine replication protocol designed for that model. It uses different message and replica requirements from crash-fault Raft or Paxos.

State the fault model before comparing protocols. A protocol can be correct under one model and unsafe under another.

Consensus has a boundary

Consensus can order operations and maintain replicated protocol state. It cannot solve every distributed coordination problem by itself.

Transaction commit: two-phase commit can block when its coordinator fails. Paxos Commit uses consensus to tolerate coordinator failure, but transaction semantics remain a separate problem.
External side effects: committing a log entry does not automatically make an email, payment, or third-party API call exactly once.
Read semantics: a follower may be behind. Linearizable reads need a protocol-defined path that confirms current authority and committed state.
Membership changes: replacing voters changes quorum relationships. Safe reconfiguration must be part of the protocol.
Durability: a vote that should survive restart must reach stable storage as required by the implementation.

When consensus is useful

Consensus is a good fit when one authoritative order matters more than accepting writes in every partition. Common examples include cluster metadata, lock and lease services, configuration stores, database replication, and control-plane state.

It is a poor default when independent updates can merge later, stale reads are acceptable, or the workload needs local writes through long partitions. Conflict-free or application-specific reconciliation may provide a better tradeoff in those cases.

How to review a consensus-backed system

Start with the contract, not the product name.

Identify the fault model and timing assumptions.
Find the voting members and calculate quorum.
Map members onto independent failure domains.
Determine when a write is committed and durable.
Determine which read paths provide which consistency.
Review leader election, membership change, and recovery behavior.
Test partitions, pauses, restarts, disk loss, and client retries.
Measure progress after failures without weakening safety.

The durable mental model is compact: consensus protects one ordered history through quorum intersection. It may stop when that protection cannot be established.