Assumption Bounded Distributed Agreement

Make distributed agreement achievable by declaring the fault, timing, membership, and validity model, preserving safety when progress is uncertain, and using only decision evidence that is valid under those assumptions.

Essence

Make distributed agreement achievable by declaring the fault, timing, membership, and validity model, preserving safety when progress is uncertain, and using only decision evidence that is valid under those assumptions.

Consensus failures usually come from hidden assumptions, not from a missing vote. A timeout cannot tell whether a node is dead or merely delayed, and a local majority can be unsafe if another membership view can form a conflicting majority. The intervention works by turning assumptions into explicit design inputs and making every advancement carry enough evidence to preserve a monotone safety invariant. Progress is then conditional and honest: the system moves when its liveness assumptions hold, and it remains visibly undecided when they do not.

The decisive move is not “take a vote.” It is to make the assumptions behind any vote explicit, then require evidence that remains safe across delay, crash, recovery, leader change, and membership change. When the evidence cannot be assembled, the correct output may be undecided rather than a guessed winner.

Compression statement

When independent agents must decide one value but messages may be delayed, lost, reordered, partitioned, or adversarial and participants may crash, recover, or equivocate, do not promise unconditional agreement, validity, and termination. Define the decision and membership epoch; state the fault and communication model; choose a safety–liveness contract; derive intersecting quorums and protocol rules; make tentative, locked, certified, and committed states distinct; require durable decision evidence; expose stalls rather than fabricating finality; and recover or reconfigure without erasing prior commitments.

Canonical formula: Given participants P in membership epoch e, admissible values V, fault budget F, communication model C, safety properties S, and liveness conditions L: choose protocol Π and certificate rule Q such that under F and C, no two correct participants decide different v ∈ V (agreement), every decided v satisfies the validity rule, and termination is claimed only when L holds. If Q cannot be obtained, preserve S and expose nontermination rather than inventing a decision.

When this pattern is needed

• Two or more independently failing participants must agree on one value, leader, order, configuration, lock owner, or state transition.
• A conflicting pair of decisions would be materially worse than temporary unavailability or delay.
• Messages can be delayed, lost, duplicated, reordered, or partitioned, so silence is ambiguous.
• Participants may crash, restart, lose volatile state, or, in stronger threat models, equivocate or collude.
• No single permanently trusted participant can safely decide every instance without becoming an unacceptable failure or capture point.
• The system needs a checkable notion of finality that recovering or lagging participants can verify.
• Membership or leadership can change over time and stale authorities must be prevented from continuing to decide.
• The application can define an admissible value domain and a validity predicate before agreement is attempted.
• The system can state a finite fault budget or trust assumption rather than treating all failures as unbounded.
• Operators need to distinguish a safe stall from a safety violation, and need recovery procedures for both.

Structural problem

Several independently controlled participants must expose one authoritative decision or ordered state even though they do not share instantaneous knowledge and some participants or communication paths may fail, recover, delay, partition, or behave adversarially. Each participant can see only a local and potentially stale slice of the system, so an apparently sufficient set of responses may coexist with a conflicting set elsewhere unless membership, fault bounds, rounds, and decision evidence are designed to intersect safely.

The root tension is: Agreement requires enough overlap and persistence that conflicting evidence cannot both become valid, while termination requires enough timely communication and available correct participants to collect that evidence. Under full asynchrony with faults, delay is indistinguishable from failure, so a deterministic protocol cannot guarantee both unbroken progress and safety without adding timing, randomness, failure-detector, trust, or availability assumptions.

Intervention logic

1. Define the decision instance, admissible values, proposal authority, and externally meaningful finality boundary.
2. Freeze or version the participant set and identity model for the instance; define how membership changes can become valid.
3. State the participant and channel fault model, including correlated failure domains and the maximum tolerated fault budget.
4. State the communication and timing model, distinguishing full asynchrony, partial synchrony, bounded delay, and clock or lease assumptions.
5. Write a safety–liveness contract that names agreement, integrity, validity, durability, termination, and availability separately.
6. Choose which guarantees are non-negotiable when partitions or uncertainty prevent all of them from holding simultaneously.
7. Select a protocol family and derive quorum thresholds, intersection, locking, and certificate rules from the model rather than convention.
8. Use monotone rounds, terms, views, or epochs so stale leaders and messages cannot acquire current authority.
9. Persist votes, promises, locks, accepted values, and commit evidence before acknowledging actions that depend on them.
10. Require a verifiable decision certificate before reporting commitment or triggering irreversible side effects.
11. Treat failure detection as suspicion; route timeouts into safe retries, leader/view changes, pause, or reconfiguration rather than contradictory decisions.
12. Expose no-quorum and undecided states explicitly, with bounded read-only or degraded behavior if that behavior preserves the declared invariants.
13. Recover and reconfigure through overlapping membership or proof-carrying transfer so prior commitments remain visible.
14. Test safety and liveness separately under message reordering, partitions, crash/recovery, disk loss, stale leadership, and adversarial behavior inside the declared model.
15. Review assumptions and fault-domain independence after incidents, topology changes, software changes, and key rotation.

This sequence deliberately separates safety from liveness. Safety asks whether contradictory decisions can occur. Liveness asks whether a decision will eventually occur. A healthy design may preserve safety while temporarily losing liveness; it must never describe that safe stall as a completed decision.

Key components

Component	Description
Agreement Value Contract ↗	Defines the exact decision instance, admissible value domain, proposal provenance, and meaning of one committed value. Consensus cannot repair an undefined question. The contract must distinguish one decision instance from another, reject malformed or out-of-scope proposals, and state whether a no-op, abort, or null value is admissible.
Participant and Membership Model ↗	Defines which agents may propose, vote, observe, or certify a decision and which membership epoch each action belongs to. Membership is part of the safety proof, not administrative metadata. Join, leave, replacement, key rotation, and identity duplication must not create two independently valid electorates.
Fault Model ↗	States which participant and channel failures the design intends to tolerate, including the maximum simultaneous or correlated fault budget. Reuse the indexed component. Distinguish crash-stop, crash-recovery, omission, delay, partition, equivocation, Byzantine behavior, data corruption, and compromised identity. A protocol is safe only inside the model it was designed for.
Failure, Timeout, and Partition Model ↗	Declares what message delay, loss, reordering, duplication, partition, and clock assumptions are available for making progress judgments. Reuse the indexed component from distributed transaction coordination. A timeout is evidence of delay or unreachability, not proof that a participant has failed. Fully asynchronous, partially synchronous, and bounded-delay environments support different liveness claims.
Safety–Liveness Contract ↗	Separates what must never happen from what must eventually happen and names the assumptions under which each guarantee holds. Agreement and integrity are usually safety properties; termination and availability are liveness properties. The contract should state which property wins when partitions or uncertainty make all desired guarantees jointly unattainable.
Validity Rule ↗	Specifies which values are eligible to be decided and how correct participants verify that a proposal satisfies domain constraints. A system may agree perfectly on an invalid value. Validity can require prior proposal, authorization, signature, state precondition, non-conflict, or application-specific proof.
Coordination Protocol Selection Rule ↗	Selects a protocol family whose safety proof, liveness assumptions, fault threshold, and operating cost match the declared model. Reuse the indexed component. Do not select Paxos, Raft, PBFT, a quorum rule, or a blockchain by name alone; compare the actual fault, membership, timing, durability, authentication, and finality requirements.
Quorum or Voting Rule ↗	Defines which set of independently controlled votes is sufficient to advance, lock, certify, or commit a value. Reuse the indexed component. Quorums must intersect in a way that preserves the chosen safety invariant under the declared fault budget. Counting replicas without examining shared fault domains or duplicated identities creates false independence.
Round, Epoch, and Leadership State ↗	Orders proposals and votes across retries, leader changes, and membership epochs so stale activity cannot create a second valid decision. Terms, views, ballots, rounds, and epochs are different names for the monotone context in which authority is interpreted. Participants must reject stale contexts and persist enough state to avoid voting inconsistently after recovery.
State Consistency Guard ↗	Prevents a correct participant from accepting, voting for, or exposing state that conflicts with a value already locked or committed for the same instance. Reuse the indexed component. The guard may be a highest-ballot promise, lock rule, log-matching condition, monotonic version check, or proof-carrying state transition.
Decision Certificate ↗	Carries verifiable evidence that the required quorum, epoch, validity, and protocol conditions for commitment were satisfied. A certificate may be a set of durable votes, signatures, a replicated log index, or another proof object. It should let recovering or lagging participants distinguish committed state from a plausible but unfinalized proposal.
Failure Detector ↗	Produces bounded suspicion signals about unresponsive participants or paths so the protocol can attempt leader change, retransmission, or reconfiguration. Reuse the indexed component. Failure detectors are imperfect under asynchrony; their output must trigger safe protocol transitions rather than authorizing contradictory decisions.
Stall and Partition Policy ↗	Defines the safe response when the required quorum cannot be reached or progress assumptions no longer hold. The policy may pause writes, serve only certified reads, degrade to a bounded local mode, expose undecided status, wait, retry with backoff, or escalate. It must not manufacture finality to preserve superficial availability.
Recovery Policy ↗	Defines how restarted, replaced, or reconnected participants recover durable consensus state without erasing prior promises, locks, votes, or decisions. Reuse the indexed component. Recovery must establish a safe state before participation resumes and must specify how snapshots, logs, certificates, and application side effects are reconciled.
Observability and Audit Trace ↗	Records proposals, terms, votes, certificates, membership changes, stalls, recoveries, and externally visible finality so safety and liveness can be diagnosed separately. Reuse the indexed component. Logs should reveal why progress stopped without exposing credentials or making sensitive vote material broadly available.
Termination Condition ↗	Specifies when a participant may report a decision as final, when a round ends without decision, and when the protocol must remain explicitly undecided. Reuse the indexed component. A client timeout, leader announcement, local majority, or absence of objections is not necessarily a valid termination condition.
Identity or Credential Signal ↗	Binds proposals and votes to authorized, non-duplicated participants and supports equivocation evidence where adversarial behavior is in scope. Reuse the indexed component. Authentication does not make an actor honest, but it prevents anonymous vote multiplication and allows conflicting signed statements to be attributed.
Redundancy Pool ↗	Provides enough independently failing participants to preserve the required quorum after the tolerated number of faults. Reuse the indexed component. Nominal replica count is not sufficient when replicas share power, network, administrator, software, region, or credential roots.
Assumption Register ↗	Makes synchrony, fault, identity, durability, membership, and trust assumptions visible to operators, reviewers, and dependent systems. Reuse the indexed component. Each assumption should have evidence, an owner, a test, and an explicit consequence when violated.
Event Log ↗	Preserves a durable ordered record of protocol events used for replay, diagnosis, and decision reconstruction. Reuse the indexed component. The event log may be local per participant or itself replicated; it must not be mistaken for a commitment certificate unless the protocol establishes that relation.
Decision Authority Boundary ↗	Separates protocol authority from external operational, legal, or human authority and states who may interpret, override, or invalidate a technical decision. Reuse the indexed component. A manual override must not create two concurrent sources of finality; it should enter through a governed epoch or recovery transition.
Operator Override Protocol ↗	Defines a tightly scoped, auditable path for human intervention when the protocol is stalled, unsafe, or operating outside its assumptions. Reuse the indexed component. Override should default to stopping, reconfiguring, or repairing the decision system rather than declaring an unsupported value committed.
Post-Agreement Review ↗	Reviews whether the decided value remained valid, the protocol assumptions held, and the observed fault and latency profile still matches the design. Reuse the indexed component. Review is especially important after emergency reconfiguration, suspected Byzantine behavior, or repeated liveness incidents.
Commitment Boundary ↗	Separates tentative proposals, accepted or locked state, certified commitment, and irreversible external side effects. Reuse the indexed component. External actions should not outrun the protocol state that justifies them, particularly when compensation is impossible.

Common mechanisms

Paxos-Style Quorum Protocol

Uses numbered ballots, durable promises, and intersecting acceptor quorums so a later proposer carries forward any value that may already have been chosen.

Raft-Style Replicated-Log Protocol

Uses terms, leader election, log matching, majority replication, and commit rules to apply one ordered sequence of commands across replicas under a crash-fault model.

Byzantine Fault-Tolerant Quorum Protocol

Uses authenticated messages, larger intersecting quorums, locked proposals, and view changes to preserve agreement despite a bounded number of equivocating or malicious participants.

Quorum or Consensus Commit

Commits a value or transaction decision only after collecting the protocol-defined quorum evidence required for finality.

Signed Quorum Certificate

Aggregates attributable votes or signatures into a compact proof that a proposal satisfied the required quorum in a particular epoch or round.

Term/Epoch Leader Election

Selects a temporary proposer or coordinator under a monotone term so stale leaders can be rejected and leadership can change without changing the safety rule.

View-Change Protocol

Transfers progress to a new leader or round while carrying forward the strongest locked or certified state that could already constrain future proposals.

Heartbeat and Suspicion Detector

Uses periodic evidence, adaptive timeouts, and path health to suspect stalled participants without treating absence as definitive proof of failure.

Randomized Common-Coin Protocol

Introduces shared or verifiable randomness so an asynchronous protocol can make probabilistic progress without depending on a deterministic scheduling guarantee.

Joint-Consensus Membership Change

Moves between old and new membership through an overlapping transition in which decisions satisfy both configurations before the new configuration stands alone.

Write-Ahead Vote Log

Persists promises, votes, locks, terms, and committed indices before acknowledging them so a crash and restart cannot erase safety-relevant state.

Timeout Policy

Defines adaptive waiting, retransmission, leader-change, and escalation timing without turning elapsed time into unsupported proof of failure or finality.

Consensus Fault-Injection Test

Exercises message loss, reordering, duplication, delay, partitions, crash/recovery, stale leaders, disk loss, and equivocation while checking safety and liveness oracles.

Named consensus protocols should be selected as coherent stacks. Their quorum thresholds, lock rules, leader changes, certificates, persistence, and membership transitions are interdependent. Borrowing one convenient rule from several protocols without reconstructing the proof can create a system that looks familiar but has no valid safety argument.

Parameter dimensions

• Decision shape: One isolated value, recurring leader/lock decisions, or a repeated ordered log.
• Membership: Static, slowly changing, jointly reconfigured, weighted, permissioned, or federated.
• Fault type: Crash-stop, crash-recovery, omission, partition, corruption, equivocation, collusion, or credential compromise.
• Fault budget: Maximum tolerated faults and the independence assumptions behind that count.
• Communication model: Fully asynchronous, eventually synchronous, bounded-delay, broadcast, point-to-point, authenticated, or lossy.
• Quorum geometry: Majority, weighted quorum, Byzantine threshold, flexible quorum, or federated trust slices.
• Leadership mode: Stable leader, rotating leader, leaderless rounds, or randomized proposer selection.
• Finality semantics: Immediate certificate finality, probabilistic finality, committed-prefix finality, or external settlement delay.
• Validity strength: Proposal-origin validity, authorization, application-state predicates, cryptographic proof, or multi-stage validation.
• Persistence model: Volatile state, synchronous durable vote log, replicated log, snapshot, or secure hardware state.
• Reconfiguration cadence: Rare manual changes, automated replacement, elastic membership, or emergency key rotation.
• Availability posture: Stop on loss of quorum, certified-read-only mode, bounded local operation, or weaker consistency fallback.
• Latency topology: Local cluster, cross-region, intermittent links, mobile participants, or high-latency peer network.
• External side effects: Pure internal state, idempotent effects, compensable effects, or irreversible physical/legal action.
• Observability: Per-node trace, certificate audit, safety oracle, liveness metrics, fault-domain map, and client-visible finality status.

Invariants to preserve

• Agreement: no two correct participants commit different values for the same decision instance and membership lineage.
• Integrity: each correct participant decides at most once per instance and does not acknowledge mutually inconsistent safety-relevant states.
• Validity: every committed value satisfies the declared admissibility, provenance, authorization, and application constraints.
• Quorum intersection: any two sets capable of producing conflicting progress evidence intersect in enough correct or accountable participants to prevent both certificates.
• Round monotonicity: authority, promises, locks, and accepted state move only forward across ballots, terms, views, or epochs.
• Durable memory: crash and recovery cannot erase a vote, promise, lock, or commitment needed by the safety proof.
• Membership coherence: a decision certificate identifies the membership epoch and cannot be replayed as authority in an incompatible configuration.
• Certificate verifiability: lagging, recovering, or external verifiers can distinguish committed state from tentative state.
• Explicit nontermination: absence of sufficient evidence remains undecided rather than being coerced into finality.
• Fault-budget honesty: guarantees are claimed only while the number and correlation of faults remain within the declared model.
• Side-effect ordering: irreversible application effects do not precede the protocol state that authorizes them.
• Liveness conditionality: progress claims state the timing, randomness, failure-detector, availability, and correct-participant conditions they require.

Target outcomes

• One auditable committed value or ordered log despite the tolerated participant and communication faults.
• Reduced split-brain, double-ownership, conflicting-leader, and contradictory-configuration risk.
• A clean distinction between safe unavailability and actual safety violation.
• Recovery and membership change without forgetting prior commitments.
• Protocol selection aligned to real fault, trust, latency, and durability conditions.
• Transparent finality evidence for clients and dependent systems.
• Faster diagnosis of liveness stalls because timing assumptions and failure detectors are observable.
• Fewer false guarantees caused by majority folklore, timeout assumptions, or protocol-name cargo culting.
• Controlled trade-offs among latency, availability, fault tolerance, geographic diversity, and verification cost.
• A testable safety case that can be revalidated as topology, software, membership, and threat models change.

Applicability and weak conditions

This archetype works best when one coherent state is genuinely necessary and a safe stall is preferable to conflicting finality. It is weak when participants cannot be bounded, faults are effectively unbounded, application validity is undefined, or the business requirement insists on both write availability in every partition and immediate one-value finality.

Variants

Crash-Fault Majority Agreement

Preserves one decided value when a bounded number of participants stop, restart, or omit work but do not deliberately equivocate.

Its distinctive feature is the fault model excludes arbitrary conflicting messages, allowing smaller quorums and simpler evidence than Byzantine protocols.

A majority is meaningful only with one identity per participant and durable round state.

Byzantine Fault-Tolerant Agreement

Preserves agreement and validity when a bounded number of participants may lie, equivocate, collude, or send inconsistent messages.

Its distinctive feature is safety is designed against arbitrary participant behavior rather than only omission or crash.

Do not use “Byzantine” as a label for ordinary human disagreement; it is a technical adversarial fault model.

Eventual-Synchrony Leader-Based Agreement

Preserves safety during arbitrary delay but guarantees progress only after communication and processing become timely enough for one leader or view to remain effective.

Its distinctive feature is liveness is conditional on eventual timing stability while safety remains independent of timeout accuracy.

This is a standard way to respond to FLP-style nontermination without weakening safety.

Randomized Asynchronous Agreement

Uses randomness to obtain probabilistic termination in an asynchronous environment while preserving deterministic safety conditions.

Its distinctive feature is progress comes from unpredictable shared choices rather than a deterministic timing bound.

Probabilistic termination must be communicated quantitatively rather than translated into a false deterministic guarantee.

Replicated-Log Consensus

Repeats the agreement instance to create one durable ordered log of state transitions rather than deciding only one isolated value.

Its distinctive feature is agreement is extended across indexed log positions with prefix and ordering invariants.

State-machine replication may eventually warrant its own archetype if cross-domain examples and distinct components justify promotion.

These variants are dimensions that may combine. A repeated log may use a crash-fault, eventual-synchrony protocol; a Byzantine system may also use randomized progress; and a membership transition may temporarily impose a stricter quorum geometry than steady-state operation.

Tradeoffs

• Safety versus availability: preserving one value during partition often requires refusing writes on subsets that cannot form the required certificate.
• Fault tolerance versus latency and communication: larger or more diverse quorums survive more faults but take longer and consume more bandwidth.
• Crash-fault simplicity versus Byzantine robustness: stronger adversary models require authentication, more participants, more messages, and more complex recovery.
• Stable-leader efficiency versus failover responsiveness: long leader tenures reduce coordination overhead, while aggressive leader change can thrash under variable latency.
• Deterministic operation versus randomized progress: randomness can restore probabilistic liveness under asynchronous scheduling but adds entropy, verification, and communication assumptions.
• Membership flexibility versus safety proof simplicity: frequent joins, removals, and key changes increase the risk of non-overlapping electorates.
• Geographic diversity versus quorum latency: spreading replicas reduces common-mode risk but makes timely quorum formation harder.
• Durable vote state versus throughput: synchronous persistence protects safety after crash but increases write latency and storage burden.
• Compact certificates versus audit richness: aggregated signatures reduce size but may complicate attribution, debugging, and key recovery.
• Automatic recovery versus operator control: automation reduces downtime but can propagate a flawed fault diagnosis; manual control adds delay and dual-authority risk.
• Strong validity checks versus proposal throughput: application proof and authorization prevent bad values but can dominate consensus cost.
• Protocol observability versus attack surface and privacy: rich traces improve diagnosis but may expose identities, topology, timing, or sensitive proposals.

Failure modes

Unstated synchrony assumption

Cause: The protocol’s liveness depends on bounded delay or eventual stability, but documentation and clients treat termination as unconditional.

Mitigation: Declare the timing model, monitor its preconditions, and expose safe undecided states when they fail.

Timeout treated as proof

Cause: A delayed participant is declared dead and a second authority is created.

Mitigation: Treat timeouts as suspicion inputs to terms, views, or pause rules; require quorum evidence for authority.

Non-intersecting quorums

Cause: Membership, threshold, weighting, or reconfiguration allows two disjoint sets to certify conflicting values.

Mitigation: Prove quorum intersection for every membership transition and test split-brain scenarios.

Recovered amnesia

Cause: A participant loses a prior promise, vote, lock, or committed prefix after crash.

Mitigation: Persist safety-relevant state before acknowledgement and require safe state transfer before rejoining.

Stale epoch authority

Cause: Old leaders, keys, or membership views continue to produce apparently valid messages.

Mitigation: Bind every vote and certificate to monotone epochs and reject stale authority at all boundaries.

Fault budget exceeded silently

Cause: More faults, shared fault domains, or compromised identities exist than the model allows.

Mitigation: Instrument fault-domain correlation, stop claims outside the envelope, and reconfigure or degrade explicitly.

Equivocation without evidence

Cause: The system assumes crash faults while participants can send conflicting messages or duplicate identities.

Mitigation: Strengthen identity, authentication, and certificate rules or narrow the deployment trust boundary.

Unsafe leader or view change

Cause: A new proposer does not carry forward the strongest accepted or locked value.

Mitigation: Use proof-carrying view change and test every state transition across leader failure.

Validity collapse

Cause: Participants agree on a malformed, unauthorized, stale, or application-invalid value.

Mitigation: Make validity locally checkable or attach verifiable proof before voting.

External effect before finality

Cause: A tentative leader or replica triggers an irreversible action before commitment is certified.

Mitigation: Place an explicit commitment boundary before side effects and use idempotent or compensable actions where possible.

Unsafe membership change

Cause: Old and new configurations can each form a quorum without sufficient overlap.

Mitigation: Use joint consensus, staged epoch transition, or another proven overlap mechanism.

Leader thrash

Cause: Timeouts are shorter than real tail latency, so participants repeatedly abandon viable leaders.

Mitigation: Use adaptive timing, backoff, pre-vote or equivalent safeguards, and separate path health from leader health.

Two-phase commit mistaken for consensus

Cause: Coordinator-controlled prepare/commit is assumed to remain live and safe under the same fault model as replicated consensus.

Mitigation: Keep transaction atomicity and consensus guarantees distinct; replicate or replace the coordinator decision when required.

Manual override creates dual finality

Cause: Operators force a value while the protocol can still later commit another value.

Mitigation: Stop or fence the old protocol, create a new governed epoch, and record one authoritative recovery decision.

Nondeterministic state-machine application

Cause: Replicas agree on the command but apply it differently due to time, randomness, locale, or hidden state.

Mitigation: Make application deterministic or include all nondeterministic inputs in the agreed value.

Safety and liveness metrics conflated

Cause: High throughput or leader uptime is reported as evidence that conflicting decisions cannot occur.

Mitigation: Maintain separate safety oracles, certificate audits, and liveness service objectives.

Neighbor distinctions

Consensus Convergence

Consensus Convergence is a deliberative and sensemaking pattern for sufficient human or organizational agreement. Assumption-Bounded Distributed Agreement is a protocol-level pattern for one certified value under communication and participant faults.

Fault-Tolerant Operation

Fault-Tolerant Operation preserves critical function by detection, isolation, redundancy, bypass, or degradation. The new archetype specifically requires one-value agreement, validity, quorum intersection, finality evidence, and explicit liveness assumptions.

Nested and Distributed Transaction Coordination

Distributed transaction coordination governs atomicity, participant states, compensation, and closure across one transaction. Consensus may be a commit mechanism inside it, but the parent here owns the more general problem of agreement under faults.

Transactional Atomicity

Transactional Atomicity bundles operations into commit or abort. It does not itself solve agreement among faulty replicas about which outcome is committed.

Concurrency Control

Concurrency Control prevents simultaneous correct processes from corrupting shared state. Consensus additionally addresses incomplete knowledge, message uncertainty, participant failure, and finality across independent replicas.

Failover

Failover switches to an alternate path or component. Without an agreement protocol, two sides may both believe they are primary after a partition.

Source-of-Truth Assignment

Source-of-Truth Assignment selects an authoritative representation or system. Consensus is one possible way to maintain that authority across replicas, but authority can also be centralized or administratively assigned.

Reconciliation After Drift

Reconciliation repairs divergent states after the fact. The new archetype prevents two conflicting values from both becoming final in the first place.

Branching and Merging

Branching and Merging permits controlled divergence and later recombination. Consensus forbids conflicting final decisions for the same instance.

False Convergence Prevention

False Convergence Prevention tests whether apparent epistemic agreement is genuine. Distributed agreement tests protocol evidence and fault assumptions, not shared belief quality.

Deadlock Prevention

Deadlock Prevention avoids circular waiting among resource holders. Consensus can remain safely undecided without a resource cycle because asynchronous delay prevents a progress guarantee.

Order-Independent Processing

Order-Independent Processing removes the need for coordination by making outcomes insensitive to order. It is often preferable when feasible; consensus is for cases where one shared order or value remains necessary.

Examples

Example 1

A five-replica configuration service tolerates two crash failures by committing an update only after three replicas durably record the same term and log position.

Example 2

Seven independently governed validators tolerate two Byzantine faults by requiring a five-signature certificate and carrying locked proposals across view changes.

Example 3

A distributed lock service fences stale leaders with monotonically increasing terms and refuses new locks when no majority is reachable.

Example 4

Redundant industrial controllers certify one operating-mode transition before enabling mutually exclusive actuators.

Example 5

A metadata service changes cluster membership through an overlapping joint configuration so old and new majorities cannot decide independently.

Example 6

An asynchronous validator network uses verifiable shared randomness to obtain probabilistic progress while preserving deterministic agreement.

Extended example

A five-node regional medication-order control plane must expose one authoritative policy version to hospital systems. The design declares a crash-recovery fault model with at most two unavailable nodes, eventual synchrony for liveness, authenticated fixed membership per epoch, and safety as non-negotiable. A leader proposes policy version 42 in term 18; each follower validates the schema and authorization, writes its vote and log entry durably, and responds. The leader reports commitment only after a three-node certificate and only then releases the policy to downstream systems. A partition leaves two nodes in one region and three in another. The two-node side remains read-only and reports “no write quorum”; it does not elect a leader that can commit. When one server is replaced, the cluster enters a joint old-plus-new membership epoch, transfers the committed prefix, and retires the old member only after overlapping certification. Fault-injection tests verify that delayed messages, disk restart, stale term traffic, and repeated leader changes never produce two committed policies. The design sacrifices minority-side write availability to preserve one authoritative medication policy and makes that trade-off visible to operators and clients.

Non-examples

• A facilitated workshop that resolves stakeholder disagreement without a participant fault or message model.
• A last-writer-wins replicated cache that permits temporary conflicting values and merges later.
• A database transaction that uses one coordinator and two-phase commit without replicated agreement on coordinator state.
• A simple poll in which the option with the most responses wins even though membership and duplicate identities are uncontrolled.
• A hot-standby service that switches on health-check failure without fencing the old primary.
• A leader-election heartbeat that names a coordinator but does not certify an application decision.
• A blockchain label attached to one centrally controlled database.
• A theorem summary of FLP impossibility with no intervention, assumptions register, or operational design.

Review note

This candidate fills a real gap between broad fault tolerance, human consensus convergence, and transaction coordination. Human review should pay particular attention to the ontology treatment of consensus_problem versus consensus, the queue’s conflation of Byzantine Generals and FLP as aliases, and the boundary between the parent archetype and repeated-log or federated-quorum variants.

Common Mechanisms

• Byzantine Fault-Tolerant Quorum Protocol — Reaches a quorum decision that stays safe even when up to f participants lie, forge, or equivocate — by authenticating every message and requiring a super-quorum no set of liars can fake.
• Consensus Fault-Injection Test — Deliberately injects the faults a consensus protocol claims to tolerate — crashes, delays, partitions, reordering — to check that agreement stays safe inside its assumption budget and degrades to a visible stall outside it.
• Heartbeat and Suspicion Detector — Continuously pings participants and maintains a per-node suspicion level, turning the raw stream of present-and-absent signals into the graded, revisable failure judgment that leader election and reconfiguration consume.
• Joint-Consensus Membership Change — Changes the set of participants without ever letting the old and new memberships form two independent majorities — by routing the switch through a transitional joint configuration that requires agreement from both.
• Paxos-Style Quorum Protocol — Guarantees that competing proposers choose exactly one value and never un-choose it — by ordering proposals with monotonic ballot numbers and forcing each new ballot to re-adopt any value that might already have been chosen.
• Quorum or Consensus Commit — Turns a proposed value into an authoritative, irreversible decision the instant an intersecting quorum has acknowledged it — and treats anything short of that as still undecided.
• Raft-Style Replicated-Log Protocol — Keeps a fleet of replicas byte-for-byte identical by funnelling every command through one elected leader into a single append-only log, and treating an entry as decided only once a majority has stored it.
• Randomized Common-Coin Protocol — Guarantees agreement will actually terminate under full asynchrony — where deterministic protocols provably cannot — by having undecided participants fall back on a shared, unpredictable coin instead of a timeout they can never trust.
• Signed Quorum Certificate — Bundles a quorum's authenticated votes for one value into a single self-verifying proof that the decision was legitimately reached — so anyone can check it later without replaying the protocol or trusting the reporter.
• Term/Epoch Leader Election — Chooses at most one leader per monotonically increasing term, so a stale leader from an older term can always be recognized and out-ranked — turning 'who is in charge?' into a question with a single, ordered answer.
• Timeout Policy — Bounds how long a participant will wait for an expected message, and converts the resulting silence into a safe action — abort, retry, step down, stall — never into a claim about who has failed.
• View-Change Protocol — Hands leadership from a suspected-faulty leader to a fresh one without ever losing or contradicting a decision the old leader may already have committed — trading a brief, visible pause for an unbroken safety guarantee.
• Write-Ahead Vote Log — Forces every vote, promise, and term change onto durable storage before the node acts on it, so a crash-and-restart can never make a participant contradict something it already promised.

Related Abstractions

Abstractions this archetype builds on — directly (a source ingredient) or as a related pattern. Links follow the typed catalog namespace.

Built directly on (5)

• Consensus: Producing a single shared decided state from many participants with disagreeing or adversarial views, under a fault model, satisfying agreement, validity, and termination together.
• Consensus: Producing a single shared decided state from many participants with disagreeing or adversarial views, under a fault model, satisfying agreement, validity, and termination together.
• Coordination: Aligning independently controlled actors so their separate actions combine into a coherent collective outcome despite distributed decision-making and incomplete shared information.
• Fault Tolerance: Continue operating under failure.
• Message Passing: Autonomous holders of private state interact only through discrete addressed messages over intermediating channels.

Also references 26 related abstractions

• Algorithm: Step-by-step problem-solving procedure.
• Authentication: Binding an asserted identity or origin to admissible evidence through a procedure that yields a verdict, before trust, access, or weight is granted.
• Boundedness: Values remain within limits.
• Closure: Ensures operations remain within a set.
• Concurrency: Manage simultaneous processes.
• Consistency: A set of commitments cannot jointly derive a contradiction.
• Consistency Model: An explicit contract over which observations of shared state are legal when updates are concurrent.
• Constraint: Limits possibilities to guide outcomes.
• Decision: Committing to one alternative from a set under uncertainty and trade-off, collapsing open deliberation into a chosen path and foreclosing the others.
• Eventual Consistency: Distributed copies of shared state are allowed to diverge under local updates, with a deterministic merge guaranteeing they reconverge once updates stop.

▸ Show 16 more

Variants

Narrower or domain-specific specializations that share this archetype's core structure. Recognized variants are established; candidate variants are provisional.

Crash-Fault Majority Agreement · risk or failure variant · recognized

Preserves one decided value when a bounded number of participants stop, restart, or omit work but do not deliberately equivocate.

• Distinct from parent: The parent is fault-model neutral; this variant narrows the design to crash-stop or crash-recovery behavior.
• Use when: Participant identities are controlled and malicious equivocation is outside the primary threat model; A majority or equivalent intersecting quorum remains reachable after the tolerated crash budget; Safety-relevant promises and votes can be durably recovered.
• Typical domains: replicated configuration, metadata services, distributed locking, industrial control
• Common mechanisms: paxos style quorum protocol, raft style replicated log protocol, write ahead vote log

Byzantine Fault-Tolerant Agreement · risk or failure variant · recognized

Preserves agreement and validity when a bounded number of participants may lie, equivocate, collude, or send inconsistent messages.

• Distinct from parent: This variant strengthens the fault model and therefore changes quorum thresholds, evidence, locking, view-change, and key-governance requirements.
• Use when: Participants span trust or administrative boundaries or compromise is plausible; Votes can be authenticated and conflicting statements can be attributed; The system can afford the larger participant, communication, and verification burden required by the threat model.
• Typical domains: consortium ledgers, cross organization control, critical command validation, distributed key governance
• Common mechanisms: byzantine fault tolerant quorum protocol, signed quorum certificate, view change protocol

Eventual-Synchrony Leader-Based Agreement · temporal variant · recognized

Preserves safety during arbitrary delay but guarantees progress only after communication and processing become timely enough for one leader or view to remain effective.

• Distinct from parent: The parent permits several progress assumptions; this variant selects eventual synchrony and leader/view change.
• Use when: The system may be asynchronous for long periods but is expected eventually to enter a sufficiently stable timing regime; Stable-leader operation is materially cheaper than fully leaderless coordination; Timeouts can adapt without being used as proof of safety.
• Typical domains: regional service clusters, replicated metadata, control planes
• Common mechanisms: raft style replicated log protocol, term epoch leader election, view change protocol, timeout policy

Randomized Asynchronous Agreement · implementation variant · recognized

Uses randomness to obtain probabilistic termination in an asynchronous environment while preserving deterministic safety conditions.

• Distinct from parent: The parent is neutral about the liveness mechanism; this variant explicitly accepts probabilistic termination.
• Use when: A deterministic scheduler could indefinitely prevent progress; Randomness can be generated or verified without one faulty actor controlling the outcome; Probabilistic liveness is acceptable and can be monitored.
• Typical domains: asynchronous validator networks, adversarial scheduling research, high latency peer networks
• Common mechanisms: randomized common coin protocol, signed quorum certificate

Replicated-Log Consensus · scale variant · recognized

Repeats the agreement instance to create one durable ordered log of state transitions rather than deciding only one isolated value.

• Distinct from parent: The parent covers one-value agreement generally; this variant adds repeated decisions, log matching, replay, compaction, and state-machine application.
• Use when: A service must agree on a continuing sequence of commands or records; The order of committed operations affects state; Snapshots, compaction, lag recovery, and application determinism can be governed.
• Typical domains: replicated databases, configuration services, distributed lock services, control planes
• Common mechanisms: raft style replicated log protocol, write ahead vote log, consensus fault injection test

Near names: Consensus Problem, Distributed Consensus Design, Fault-Tolerant Distributed Agreement, Consensus Under Partial Failure, Safety–Liveness Consensus Design, Byzantine Generals Problem, FLP Impossibility.