Consensus in Distributed Systems

Consensus enables distributed nodes to agree on values or ordered decisions despite specified failures and unreliable communication. Its guarantees distinguish safety from liveness, and practical protocols often rely on quorums to preserve consistency while limiting progress during partitions.

Consensus is a distributed systems problem: a set of nodes must decide on the same value or sequence of decisions, even though messages can be delayed or lost and some nodes can fail. It matters in systems that need coordinated state changes, such as replicated databases and distributed metadata services.

A consensus protocol is commonly described through safety and liveness. Safety means nodes do not decide conflicting values, and a decided value follows the protocol's validity rules. Liveness means the system can eventually make progress under stated conditions, such as a sufficiently stable network and enough available nodes.

Consensus is not a promise to work through every failure. In crash-fault-tolerant protocols, nodes may stop or become unreachable, but are assumed not to behave maliciously. For common majority-based protocols, a cluster of 2f+1 nodes can tolerate up to f unavailable nodes while retaining a quorum; without a quorum, safe progress may stop.

Protocols such as Paxos and Raft address consensus with different designs. Raft organizes decisions around an elected leader and a replicated log; a log entry is committed when the required majority has accepted it, subject to protocol rules. A leader does not make consensus unnecessary: replicas still need protocol-governed agreement about which entries are committed.

Real deployments also need to reason about timeouts, retries, and partitions. A timeout cannot prove a node has failed; it only indicates that a response has not arrived in time. Systems typically trade availability for safety during some partitions, and applications should distinguish an accepted write from one that is durably committed.

Key points

• Consensus coordinates agreement on values or ordered decisions among distributed nodes.
• Safety prevents conflicting decisions; liveness is the ability to make progress.
• A majority quorum can tolerate some unavailable nodes while preserving overlapping decision groups.
• Timeouts indicate suspicion, not certainty that a node has failed.
• During a partition, a system may reject operations on the side that cannot form a quorum.

Interview questions

What problem does consensus solve?

Consensus is the problem of getting distributed nodes to agree on a value or sequence of decisions despite failures and unreliable communication. A protocol aims to preserve safety, so nodes do not decide conflicting outcomes, while also providing liveness under appropriate conditions. The guarantees depend on the protocol's assumptions about failures and the network.

How do safety and liveness differ in consensus?

Safety says that the protocol never allows conflicting decisions, even when the system is delayed or nodes fail within the assumed model. Liveness says that nodes can eventually decide and continue processing work when the required operating conditions hold. A protocol can preserve safety while temporarily losing liveness, for example when a quorum cannot communicate.

Why do many consensus protocols require a majority quorum?

A quorum is the minimum set of participants required for a protocol action, often a majority in crash-fault-tolerant protocols. With 2f+1 voters, any two majorities overlap, and a majority remains if at most f voters are unavailable. That intersection helps prevent separate groups from independently committing conflicting decisions, provided the protocol's rules are followed.

What does a network partition mean for a consensus-based service?

A timeout is a local judgment that a response did not arrive within a chosen interval; it cannot distinguish a crashed node from a slow node or a delayed network. If two sides of a partition both accept writes independently, they can produce conflicting histories. A majority-based consensus system normally lets the side with a quorum continue while the side without one refuses operations that require consensus, preserving safety at the cost of availability for that side.

How does Raft use consensus to replicate a log?

In Raft, a leader coordinates proposals, but followers also participate by storing log entries and responding to protocol messages. An entry is considered committed only when the protocol's commit conditions are met, including replication to a majority and Raft's rules about log terms. This lets a later leader preserve committed history rather than treating the previous leader's local state as authoritative.