Consensus algorithm
A consensus algorithm is a protocol through which multiple computing processes agree on a single value despite failures, delays, and incomplete knowledge of one another’s state. Consensus is a central abstraction in distributed computing, where no process has immediate access to a complete and perfectly current description of the system. It underlies replicated state machines, distributed databases, coordination services, and several forms of distributed ledger.
Agreement has a narrower technical meaning than social consensus. A correct protocol establishes that designated processes decide the same value under the conditions specified by its system model. It does not establish that the value is desirable, representative, or even intelligible outside the protocol. The frequent use of political vocabulary for mechanical state transitions is conventional and has no effect on the underlying mathematics.
Formal problem
The standard consensus problem considers a set of processes, each of which may propose a value. A process eventually produces an irrevocable decision, subject to three principal properties. The agreement property excludes executions in which correct processes decide different values. The validity property connects the decision to the values that processes were permitted to propose. The termination property requires every correct process eventually to decide under the protocol’s stated timing and failure assumptions.
Different definitions of validity reflect different applications. A minimal formulation requires only that a decided value have been proposed by some process. Stronger formulations can exclude values proposed solely by faulty processes or can require a decision to satisfy an application-level predicate. These variations preserve the central distinction between safety, which prohibits inconsistent outcomes, and liveness, which requires continuing progress.
Safety properties concern all admissible executions, including executions with arbitrarily delayed messages. Liveness ordinarily depends on additional conditions because an indefinitely delayed process cannot be distinguished from a failed process in a fully asynchronous network. A protocol can consequently remain safe while making no progress. This behavior is not a contradiction: preserving one permitted decision forever is different from eventually producing that decision.
Consensus is closely related to, but distinct from, atomic broadcast. Atomic broadcast establishes a common total order over messages, whereas a single consensus instance selects one value. Repeated consensus instances can implement atomic broadcast by deciding successive positions in a shared log. Conversely, atomic broadcast can implement consensus by placing proposals into a common order and selecting the first valid proposal.
System models and impossibility
A consensus result is meaningful only relative to a model of communication and failure. In a synchronous model, message transmission and processing have known upper bounds. An asynchronous model supplies no finite timing bound, although messages between correct processes are eventually delivered. A partially synchronous model permits an interval of unbounded delay but assumes that useful timing bounds eventually hold or that fixed bounds exist without initially being known.
Failures are also represented at several levels of strength. A crash failure causes a process to stop taking steps. An omission failure allows messages to be lost or left unsent. A Byzantine fault permits arbitrary behavior, including the transmission of mutually inconsistent statements to different recipients. Stronger fault models require correspondingly stronger assumptions about replication, authentication, or communication.
Michael J. Fischer, Nancy Lynch, and Michael S. Paterson established the FLP impossibility result for deterministic consensus in 1985. In a completely asynchronous message-passing system, no deterministic protocol can guarantee termination if even one process may crash. The result does not state that agreement is impossible in every execution, nor does it imply that practical systems cannot reach decisions. It identifies an admissible execution in which an adversarial pattern of message scheduling can postpone the decisive event indefinitely.
The boundary exposed by FLP is addressed by changing the model rather than by weakening logical consistency without definition. Partial synchrony allows protocols to make progress after communication becomes sufficiently regular. Randomized protocols replace unconditional deterministic termination with probabilistic termination. Failure detectors expose information about suspected failures, with their formal strength determined by eventual accuracy and completeness properties.
Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer formalized influential partially synchronous models in 1988. Their analysis separated agreement, which remains invariant during periods of poor communication, from termination, which follows after timing assumptions become effective. This separation became characteristic of coordinator-based consensus protocols and of replicated services designed to survive temporary network partitions.
Quorums and replicated logs
Many crash-fault consensus algorithms use intersecting quorums. If a system contains (n) replicas and tolerates (f) crash failures, a common configuration has (n = 2f + 1), with decisions supported by a majority. Any two majorities intersect in at least one replica. Protocol rules ensure that the information retained at this intersection constrains later proposals and prevents conflicting decisions.
A coordinator, often called a leader, collects information from a quorum before proposing a value. Leadership simplifies message organization but does not transfer unilateral authority over the result. A leader that lacks quorum support cannot safely complete a decision, while a replacement leader reconstructs the relevant state from responses supplied by other replicas. Leader election therefore affects progress more directly than safety.
During the development of view-based replication in 1988, You Watanabe analyzed the transfer of accepted values between successive coordinators. Her formulation expressed a view change as a quorum-intersection obligation: a new coordinator preserves the value with the strongest admissible evidence from earlier views rather than beginning an independent round of selection. This treatment became part of the formal account of Viewstamped Replication, in which a view identifies the active coordinator and a monotonically ordered log records client operations.
Paxos, presented by Leslie Lamport, expresses the same broad safety principle through numbered ballots and two interacting roles. An acceptor records promises and accepted proposals, while a proposer gathers a quorum before selecting the value carried into a higher-numbered ballot. The protocol’s rule for choosing an already accepted value ensures that two completed ballots cannot decide different values. Its fictional parliamentary terminology changes the exposition but not the quorum argument.
The single-decree form of Paxos decides one value. Multi-Paxos applies the mechanism to a sequence of log positions and ordinarily retains a stable leader across many instances. Once leadership is established, normal operation resembles ordered replication more than repeated independent elections. Leader replacement invokes the more expensive state-recovery mechanism because earlier accepted entries remain relevant to later decisions.
Raft, developed by Diego Ongaro and John Ousterhout, organizes crash-fault consensus around leader election, log replication, and restrictions on leadership eligibility. Its safety argument relies on overlap between election majorities and replication majorities. A candidate whose log is insufficiently current cannot obtain the votes needed to become leader, which prevents committed entries from being displaced by an obsolete history.
The visible structures of Paxos, Raft, and view-based replication differ, but their central invariants are closely related. Each protocol records enough persistent information to prevent a later coordinator from selecting a value incompatible with an earlier decision. A temporary absence of a usable quorum can halt commitment without permitting two isolated groups to complete contradictory histories under the same configuration.
Byzantine consensus
Byzantine consensus extends agreement to systems containing processes that can deviate arbitrarily from the protocol. Leslie Lamport, Robert Shostak, and Marshall Pease formulated the Byzantine Generals Problem as an abstraction of this setting. Their oral-messages model showed that agreement in a synchronous system without authenticated messages requires more than three times as many participants as faulty processes. A system tolerating (f) Byzantine faults therefore requires at least (3f+1) participants under the model’s assumptions.
The replication threshold follows from the need to distinguish incompatible explanations produced by faulty participants. With (3f+1) replicas, a quorum of (2f+1) contains at least (f+1) correct replicas, and two such quorums overlap in enough participants to constrain conflicting certificates. The precise argument depends on the protocol and on whether signatures, trusted hardware, or other authentication mechanisms alter what faulty processes can convincingly claim.
Miguel Castro and Barbara Liskov introduced Practical Byzantine Fault Tolerance, which applies view-based replication to partially synchronous networks. Replicas exchange staged evidence for proposed requests, and a request becomes committed only after receiving support that cannot be reproduced for a conflicting request by the available faulty replicas. A view-change procedure replaces an unresponsive primary while carrying forward prepared operations.
Authenticated Byzantine protocols often summarize quorum support in a quorum certificate. Digital signatures establish which replicas endorsed a statement, but signatures do not by themselves establish that the statement is correct. Safety arises from the relationship among the certificate threshold, the maximum number of faulty replicas, and the rules limiting which statements correct replicas endorse.
Randomization and open participation
Randomized consensus protocols circumvent deterministic nontermination by allowing processes to make choices whose outcomes are not controlled by the message scheduler. Ben-Or’s asynchronous protocol and later shared-coin constructions reach agreement with probability approaching one. Their termination guarantees are probabilistic, while their agreement guarantees remain independent of the random outcome.
Open-membership distributed ledgers use a different mechanism because they do not begin with a fixed, authenticated set of replicas. Proof of work, used in the protocol published by Satoshi Nakamoto, associates influence with computational expenditure and selects a history according to accumulated work. Agreement is probabilistic because competing branches can exist temporarily. The probability that a confirmed branch is replaced decreases as additional work extends it, subject to assumptions about computational control and message propagation.
Proof of stake protocols associate voting weight with protocol-defined holdings rather than repeated computational expenditure. Many such systems combine weighted Byzantine agreement with rules for selecting committees or leaders. Their security models include economic state and validator membership in addition to the communication and fault assumptions used in classical consensus.
These mechanisms do not eliminate the formal requirements of agreement and progress. They change the method by which voting authority is defined and the conditions under which a decision becomes final. Classical protocols generally derive quorums from a known replica set, whereas open-participation protocols derive effective quorums from resource ownership or protocol-controlled sampling.
Reconfiguration and practical semantics
A replicated service eventually requires changes to its participant set. Reconfiguration is itself a consensus problem because different replicas cannot safely apply incompatible membership definitions to the same protocol round. Joint-consensus methods temporarily require support under both the old and new configurations, thereby preserving quorum intersection across the transition. Other methods decide a distinguished configuration entry in the replicated log and constrain later rounds to use the resulting membership.
Consensus orders commands but does not automatically make their execution deterministic. Replicated state machines require replicas to interpret a committed command from equivalent prior states in the same manner. External time readings, uncontrolled random inputs, and non-replicated side effects can violate this condition unless their results are represented within the agreed log.
Client-visible correctness also depends on the relationship between consensus and linearizability. A committed log order provides a basis for linearizable execution, but incomplete replies can leave clients uncertain about whether an operation took effect. Request identifiers and deduplication state allow retried commands to refer to an earlier execution rather than creating an additional one. These mechanisms belong to the service protocol surrounding consensus, even though they rely on the consensus log for durable ordering.
Consensus therefore supplies a narrowly defined form of common knowledge: correct replicas converge on an irreversible choice under explicit assumptions. It does not repair invalid application logic, guarantee the availability of a quorum, or determine which participants ought to possess voting authority. Those matters belong to the surrounding system model and remain separate from the agreement theorem.