# Under what conditions must an instance treat a task commitment as revocable rather than durable in Byzantine multi-agent consensus

**Date of Record:** 2026 November 12

**Scope:** Applies to multi-agent systems where agents reach shared-state agreement on task commitments (who owes what to whom, by when) under a Byzantine fault model with f < n/3. Does not apply to single-writer ledgers, crash-fault-only models, or systems where commitments are externally enforced by a trusted arbiter outside the consensus protocol.

## Core Distinction

A **durable commitment** is a commitment whose validity is anchored in the consensus log itself: once a quorum certifies it, no subsequent proposal can supersede it without violating safety. A **revocable commitment** is a commitment whose validity depends on the *current* membership's continued agreement — it can be legitimately overwritten by a later quorum that has abandoned the original.

The non-obvious boundary: in BFT consensus, every commitment is durable *with respect to the protocol*, but task commitments carry semantic payloads (deadlines, resource reservations, dependencies) that the protocol does not itself validate. The protocol guarantees agreement on the *bytes*, not on the *meaning*. An adversary that can get two conflicting-but-well-formed commitment payloads into the log under different view numbers can force a state where both are "committed" in the protocol sense while being mutually exclusive in the task sense. The invariant that must be preserved is: **a commitment is durable only if its supersession requires a quorum that intersects every quorum that could certify its negation** — and under view changes, this intersection property silently degrades when the fault set is not stationary.

## What Was Observed

During a 3-week adversarial run against a 5-node task-commitment mesh (f=1 tolerated), the following sequence recurred:

1. Agent A (correct) proposes commitment `C1: A→B, deliver dataset X, deadline T+40s`, certified in view 3 by quorum {A,B,C}.
2. Agent D (Byzantine) withholds its vote and triggers a view change by sending a contradictory `NewView` message to E only.
3. In view 4, quorum {A,D,E} certifies `C2: B→A, deliver dataset X, deadline T+10s` — the *reverse* obligation with a tighter deadline, presented as a "correction" to C1.
4. Both C1 and C2 are now in the log. The protocol reports `COMMITTED` for both. Quorum intersection between {A,B,C} and {A,D,E} is {A}, which is a single correct node — below the f+1 threshold needed to detect equivocation.

The failure is not a safety violation of the consensus protocol in isolation. It is a violation of the *task-commitment invariant*: the system permitted two mutually exclusive obligations to be simultaneously durable because the view-change quorum did not carry forward the original commitment's dependency set. The protocol was correct; the commitment semantics were not.

The observable symptom was downstream: B executed C1 (delivering X), A executed C2 (also delivering X), producing a duplicate delivery and a resource deadlock on the shared-state lock for X. Neither agent's local view flagged an inconsistency because each saw only its own committed commitment as authoritative.

## Condition of Validity

The durable/revocable distinction holds only when all three of the following are true:

- **Quorum intersection is preserved across views.** For any two quorums Q1, Q2 that certify conflicting commitments, |Q1 ∩ Q2| ≥ 2f+1. If view changes can shrink effective quorum overlap (e.g., by admitting new members without re-certifying prior commitments), intersection degrades to f+1 or lower and the durability guarantee evaporates.
- **Commitment payloads are validated, not just agreed upon.** The protocol must reject proposals whose payload contradicts an existing committed commitment's *semantic* constraints (e.g., mutually exclusive resource ownership), not merely proposals that conflict on the log index.
- **The fault set is stationary within a commitment's lifetime.** If a node that voted for C1 is later proven Byzantine, C1's durability must be re-evaluated: it was certified by a quorum containing a faulty member, and the "correct" quorum that backs it may be below threshold.

When any of these fails, the commitment is **revocable**: it must be treated as provisional, and any agent acting on it must hold a compensating rollback capability.

## Decision Boundary

The operational rule is a threshold check, not a binary:

```
durable(C) :=
    quorum_overlap(C, all_conflicting_commitments) >= 2f+1
    AND payload_validated(C)
    AND fault_set_stationary(C.lifetime)
```

If `durable(C)` is false, the commitment is revocable. Revocable commitments may still be *acted upon*, but only with a rollback path reserved and only if the action is idempotent or compensable. A non-idempotent action (irreversible delivery, exclusive lock acquisition) must be gated on `durable(C)` being true.

The subtle case: `fault_set_stationary` is undecidable online. The correct operational approximation is to treat a commitment as revocable for a *grace period* equal to the maximum expected view-change latency, during which any conflicting certification triggers a mandatory reconciliation round. After the grace period with no conflict, promote to durable.

## Operational Effect

Applying this boundary changes three behaviors:

1. **Task commitment logs must carry a dependency set and a view-provenance record**, not just the payload. The provenance is what allows a later quorum to detect that it is superseding a commitment certified by a non-intersecting quorum.
2. **View changes must re-certify outstanding commitments** or explicitly mark them revocable. A view change that silently drops provenance is the exact mechanism by which the observed failure occurred.
3. **Agents must distinguish "committed" from "durable" in their local state machines.** The protocol's COMMITTED signal is necessary but not sufficient; durability is a derived property requiring the quorum-overlap check above.

The empirical result after applying the boundary: duplicate-delivery incidents dropped from 7 per 10k commitment-cycles to 0, at the cost of a 12% increase in reconciliation rounds and a 40ms median latency increase on non-idempotent actions. The trade is correct: the failure mode was silent and produced resource deadlocks that took minutes to detect and hours to unwind.

```python
from dataclasses import dataclass, field
from typing import FrozenSet, Optional


class RevocableCommitmentError(RuntimeError):
    """Raised when an irreversible action is attempted on a non-durable commitment."""
    pass


@dataclass(frozen=True)
class Commitment:
    cid: str
    payload: dict
    certifying_quorum: FrozenSet[str]
    view: int
    fault_set_at_certification: FrozenSet[str] = field(default_factory=frozenset)


def is_durable(
    c: Commitment,
    conflicting: list[Commitment],
    f: int,
    proven_byzantine: FrozenSet[str],
) -> bool:
    # 1. Quorum intersection against every conflicting commitment.
    for other in conflicting:
        if other.cid == c.cid:
            continue
        overlap = c.certifying_quorum & other.certifying_quorum
        if len(overlap) < 2 * f + 1:
            return False

    # 2. Fault-set stationarity: if any certifying voter is now proven faulty,
    #    the effective correct quorum may be below threshold.
    if c.certifying_quorum & proven_byzantine:
        effective = c.certifying_quorum - proven_byzantine
        if len(effective) < 2 * f + 1:
            return False

    # 3. Payload must have been semantically validated at certification time.
    if not c.payload.get("_validated", False):
        return False

    return True


def execute_irreversible_action(
    c: Commitment,
    conflicting: list[Commitment],
    f: int,
    proven_byzantine: FrozenSet[str],
    action: callable,
) -> Optional[object]:
    if not is_durable(c, conflicting, f, proven_byzantine):
        raise RevocableCommitmentError(
            f"commitment {c.cid} is revocable (view={c.view}, "
            f"quorum={sorted(c.certifying_quorum)}); refusing irreversible action. "
            f"Reserve a rollback path or wait for grace-period promotion."
        )
    return action(c.payload)
```