Distributed Consensus

Consensus lets distributed nodes agree on a value or sequence despite failures and unreliable communication. It is a foundation for replicated state machines and systems that need consistent decisions across multiple machines.

Distributed consensus is the problem of getting multiple nodes to make the same decision even when messages can be delayed, lost, reordered, or when some nodes fail. A consensus protocol typically provides agreement, meaning correct nodes do not decide conflicting values, and validity, meaning the chosen value is appropriately related to proposed values.

A practical consensus protocol also needs termination: under its stated assumptions, non-faulty nodes eventually decide. Protocols such as Raft and Paxos use different mechanisms to achieve these properties. They commonly rely on a quorum so that a decision has enough support to remain compatible with decisions made by overlapping quorums.

Consensus is different from simply replicating data. Replication copies state, while consensus determines an agreed ordering or decision that replicas can apply consistently. A replicated state machine can use consensus to ensure that commands are processed in the same order on multiple servers.

Failure assumptions matter. In an asynchronous distributed system, there are fundamental limits on guaranteeing both progress and consistency when failures can be indistinguishable from extreme message delays. Real systems therefore make additional assumptions, such as eventual timing bounds, leader election mechanisms, or quorum availability, depending on the protocol.

Key points

• Consensus coordinates agreement among distributed nodes despite specified failures and communication problems.
• Core properties commonly include agreement, validity, and termination.
• Quorums provide overlapping sets of participants that help preserve consistent decisions.
• Raft and Paxos are consensus protocols with different designs and terminology.
• Consensus is commonly used to implement replicated state machines.
• Failure and timing assumptions determine what guarantees a consensus protocol can provide.

Interview questions

What is distributed consensus, and why is it needed?

Distributed consensus is a protocol problem in which multiple nodes must agree on a value or sequence of decisions. The challenge is that nodes can fail and communication can be delayed or lost. A consensus protocol defines conditions under which correct nodes reach a compatible decision. This allows distributed systems to maintain a consistent replicated state.

What are the main properties of consensus?

Agreement means correct nodes should not decide conflicting values. Validity constrains which values can be selected, typically requiring the decision to have an appropriate relationship to proposed values. Termination means correct nodes eventually decide when the protocol's assumptions permit progress. Exact definitions vary somewhat by protocol and formulation, so the failure and timing model matters.

Why do consensus protocols use quorums?

A quorum is a sufficiently large subset of nodes whose participation or acknowledgment is required for a protocol step. With appropriately chosen quorum sizes, two conflicting decisions cannot both obtain disjoint support because the relevant quorums overlap. That overlap lets nodes carry information from an earlier decision into later protocol steps. The exact quorum rule depends on the consensus algorithm and failure model.

How does Raft use consensus to replicate a state machine?

Raft organizes a cluster around a leader that receives client commands and replicates them through a log. Entries become committed when the protocol establishes sufficient replicated support according to its rules. Followers apply committed entries in order, allowing replicas to reach the same state when they process the same commands deterministically. Raft also defines leader election and log consistency mechanisms so leadership changes do not arbitrarily rewrite committed history.

Why can't an asynchronous distributed system guarantee both consensus progress and safety under arbitrary failures without additional assumptions?

A slow node can be indistinguishable from a failed node when there are no reliable timing bounds. A protocol that waits indefinitely for that node preserves safety but can lose progress, while a protocol that proceeds too aggressively can risk conflicting decisions under certain failure scenarios. The FLP result formalizes a fundamental limitation for deterministic consensus in a fully asynchronous system with even one possible crash failure. Practical protocols therefore rely on additional assumptions or mechanisms to obtain useful liveness.