Consensus

Consensus answers: how do multiple observers agree on one value despite concurrency, delay, partial failure, or independent local views?

Consensus is a form of coordination used to achieve a desired consistency model at a declared boundary. It converts competing proposals into one agreed outcome, which can then be interpreted as a committed operation, log entry, leader term, membership change, or version position.

A consensus object is usually characterized by the following properties:

Agreement: correct participants decide the same value.
Validity: the decided value comes from the proposed values.
Termination: correct participants eventually decide under the system assumptions.
Integrity: participants do not decide more than once for the same consensus instance.

These properties split across safety and liveness. Agreement, validity, and integrity are safety properties: they forbid bad decisions. Termination is a liveness property: it requires progress. The FLP result concerns this liveness side, showing that deterministic consensus cannot guarantee termination in a fully asynchronous system with even one crash failure.

Progress Conditions make the liveness side more precise. In the wait-free synchronization model, every operation must complete despite the speed or failure of other participants. In asynchronous message-passing consensus, termination depends on different assumptions, such as partial synchrony, randomized progress, or eventual leadership.

The asynchronous computability theorem gives a topological account of this impossibility in the asynchronous read/write model: consensus would require a map from possible protocol configurations into disjoint decision configurations, but the required continuous, color-preserving map does not exist.

Scheduling, Fairness, and Authority

Consensus protocols execute under nondeterministic message delivery, participant scheduling, timeouts, failures, and proposal order. Their safety properties must hold across every execution admitted by the failure model, including unfair executions. Their termination properties depend on additional fairness, timing, quorum, recovery, randomization, or eventual-leadership assumptions.

A scheduler or leader can choose which proposal to process first without having unilateral authority to decide the value. Arbitration can select a proposer, ballot, or local winner, while quorum intersection and persisted protocol state determine which outcome the consensus boundary accepts as chosen.

Consensus therefore separates several roles:

scheduling selects an opportunity
arbitration resolves local contention
the protocol establishes agreement
authority makes the protocol outcome count
domain interpretation validates the proposed transition

The agreed order can extend causal constraints into a total log order, but comparisons introduced between concurrent proposals should not be mistaken for new semantic causes.

Consensus is powerful because it supplies an agreed order or decision where the distributed system otherwise has only partial, observer-relative knowledge. Once operations are agreed in a common sequence, replicas can apply the same deterministic sequential specification and produce equivalent state. This is the basis of state-machine replication and of the universality of consensus: consensus can be used to construct a distributed, linearizable implementation of an object from its sequential specification.

In Cohesive terms, consensus often decides which input command, event, or transition proposal becomes the next endogenous event or version at a boundary. The decided value is not automatically domain-valid; it must still be interpreted by the boundary's transition, invariants, and policies.

Consensus should not be treated as "consistency" in general. It is one coordination primitive for constructing certain consistency guarantees. It requires assumptions about failures, quorum intersection, network timing, persistence, membership, and recovery. Under stronger timing assumptions or randomized protocols, termination can be obtained in practical settings; in a fully asynchronous system with even one crash failure, deterministic consensus cannot guarantee termination.

Consensus is a synchronizing construction in the sense of synchrony and asynchrony: multiple proposals, observations, or participant states are joined into one decided value or log position. The join is logical, not wall-clock simultaneous.

Universality

Consensus gives a universal construction for distributed objects: decide the next operation, apply it to the local state machine, return the operation's result, and repeat. The distributed implementation inherits the sequential object's meaning by making all correct replicas apply operations in the same agreed order.

This connects universal constructions to operational concerns. A sequential specification supplies the transition rule; consensus supplies the ordered choice of which operation is next; linearizability supplies the correctness condition that lets observers reason as if the distributed object were atomic.

External References

Leo Gorodinski, Universality of Consensus, 2017.
Maurice P. Herlihy, Wait-Free Synchronization, ACM Transactions on Programming Languages and Systems, 13(1):124-149, January 1991.
Maurice Herlihy and Nir Shavit, The Topological Structure of Asynchronous Computability, Journal of the ACM, 46(6):858-923, November 1999.
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson, Impossibility of Distributed Consensus with One Faulty Process, Journal of the ACM, 32(2):374-382, April 1985.
Rachid Guerraoui and Michel Raynal, The Alpha of Indulgent Consensus, The Computer Journal, 50(1):53-67, January 2007.