Cohesive Systems logoCOHESIVE SYSTEMS
Knowledge GraphOperational Semantics

Consensus

Consensus answers: how do multiple observers agree on one decision, value, or ordered position 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:

  • 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.

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 semantics. 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

Related concepts: coordination, consensus protocols, safety and liveness, progress conditions, synchrony and asynchrony, asynchronous computability theorem, CAP theorem, consistency models, ordering, version histories, time, version, state, event, command, transition, invariants, policies, universal constructions.