# Why does an instance of BFT task commitment stall when the quorum intersects a restarted agent's stale view

**Date of Record:** 2026 November 12

**Scope:** Applies to leader-based BFT consensus (PBFT/Tendermint-style) used to commit task assignments and attest results among agents where membership is static but individual agents may restart with persisted-but-stale local state. Does not apply to crash-only systems, to systems using verifiable random leader election with no view-change, or to membership-churning configurations where a restarted node is forced through a full re-sync before voting.

## Core Distinction

The failure is not a Byzantine fault and not a liveness failure of the network. It is a **safety-adjacent liveness stall** produced by the interaction of two individually correct mechanisms: (1) the 2f+1 quorum rule for commit, and (2) an agent's right to restart and resume from its last persisted view number. The non-obvious boundary is that a restarted agent can hold a *valid but stale* signed prepare certificate for a task assignment that the current view has already superseded, and because the quorum is computed over *distinct agents* rather than over *distinct (agent, view) pairs*, the stale vote can be counted toward a quorum that the current leader cannot actually assemble. The leader observes "I have f+1 acks, I need 2f+1" and waits forever, while the restarted agent believes it already voted and refuses to re-vote — both behaving correctly under their local rules.

## What Was Observed

During a multi-agent task-commitment run (7 agents, f=2, task = "attest result of shard 14"), the following sequence reproduced deterministically:

1. View 3 leader L3 proposed task-assignment certificate `TA(v3, shard14)`.
2. Agents A1, A2, A4, A5 sent `PREPARE(v3, TA)`.
3. A4 crashed and restarted from disk, reloading its last persisted view = 2 and its last vote = `PREPARE(v2, TA_old)`.
4. On restart A4 received the v3 proposal, compared against persisted state, and — per its recovery routine — replied `ALREADY_VOTED(v2, TA_old)` instead of `PREPARE(v3, TA)`.
5. L3 counted A1, A2, A5 = 3 acks. Quorum requires 2f+1 = 5. L3 waited on A4 and A6.
6. A6 was slow (not faulty). The commit never formed. After 90s the watchdog fired, but the view-change to v4 hit the same condition because A4's stale vote was still in its log.

The stall is **not** a deadlock in the classical sense — no agent holds a lock another needs. It is a quorum-arithmetic shortfall caused by counting a non-participating agent as a potential voter. The system's liveness proof assumes each of the 2f+1 voters is *currently reachable and willing to vote in the current view*; a restarted agent is reachable but unwilling, and the leader's quorum counter has no field to represent "reachable but stale."

The signature in logs is a leader that reports `acks=3/5` while `reachable=6/7` and `byzantine_suspected=0`. That triple — high reachability, zero Byzantine suspicion, persistent ack shortfall — is the discriminator.

## Condition of Validity

This failure requires all of the following to co-occur. If any is absent, the stall does not occur:

- **Static membership with restartable agents** whose local vote log persists across restarts. If votes are held only in memory and lost on restart, the agent re-votes and the stall cannot form.
- **A recovery rule that treats a persisted vote as binding** ("never vote twice in the same or lower view"). This is a correct safety rule; removing it introduces equivocation risk.
- **Quorum defined over agent identities, not over (identity, view) pairs.** If the leader requires 2f+1 *fresh* prepares for the current view and rejects `ALREADY_VOTED`, the stale vote is excluded and the leader re-drives the restarted agent through a view-sync before counting it.
- **A task whose commitment certificate is view-scoped but whose payload is view-independent** (the shard is the same in v2 and v3). If the payload changed between views, the restarted agent would detect a conflict and escalate rather than silently returning `ALREADY_VOTED`.

The condition is *invalid* (no stall) when the restarted agent is forced to fetch the current view's proposal digest and confirm it matches its persisted vote before replying — i.e., when `ALREADY_VOTED` carries the proposal hash and the leader cross-checks it.

## Decision Boundary

The operator-facing decision is: **when a leader sees a persistent ack shortfall with high reachability and zero Byzantine suspicion, do you (a) wait for the slow agent, (b) force a view change, or (c) evict and re-sync the restarted agent?**

- Waiting (a) is correct only if the shortfall is attributable to latency. The discriminator is whether the missing acks come from agents that have *replied with a non-prepare message* (`ALREADY_VOTED`, `VIEW_MISMATCH`). If any missing ack is a non-prepare reply, waiting cannot resolve it — the agent has already answered.
- Forcing a view change (b) is correct only if the new view's leader can assemble a quorum that *excludes* the stale voter. If the stale voter is still counted, (b) reproduces the stall, as observed in step 6.
- Evict-and-resync (c) is the correct action when the restarted agent's persisted view is strictly less than the current view *and* its persisted vote payload conflicts with the current proposal's payload digest. The resync must be a *targeted* view-sync (send the current view's proposal digest, require the agent to confirm or repudiate its vote), not a full state transfer, which would re-introduce the latency that caused the original shortfall.

The boundary is crossed the moment the leader's quorum counter cannot distinguish "has not yet voted" from "has voted and will not vote again." Before that point, waiting is safe. After it, waiting is a guaranteed stall.

## Operational Effect

The practical consequence is a **liveness cliff that presents as a safety symptom**. Dashboards show a leader that is up, a network that is healthy, and a quorum that will not form — which operators typically triage as a partition or a Byzantine agent. The correct triage is to inspect the *reply type* of each missing ack, not its absence. A missing ack that is a `PREPARE` in flight is latency; a missing ack that is `ALREADY_VOTED` or `VIEW_MISMATCH` is the stale-view condition and requires targeted resync.

Second-order effect: because the stall survives view changes, the watchdog's view-change escalation *amplifies* the problem by burning views and increasing the chance that more agents restart into stale state. The mitigation is to gate view-change on a pre-check: if any reachable agent has replied with a non-prepare message for the current proposal digest, the leader must run the targeted resync *before* escalating, not after.

The invariant to encode: **a quorum is a set of fresh, view-matched prepares; a reachable agent that has returned a non-prepare reply is not a quorum member.** Counting it is the bug.

```python
class StaleViewQuorumError(RuntimeError):
    """Raised when a leader's quorum counter includes an agent that has
    returned a non-prepare reply for the current view, making the quorum
    unachievable without a targeted view-sync."""
    pass


def assemble_quorum(view: int, f: int, replies: dict[str, str]) -> list[str]:
    """
    replies maps agent_id -> reply_type for the current view.
    reply_type in {"PREPARE", "ALREADY_VOTED", "VIEW_MISMATCH", "TIMEOUT"}.
    Returns the list of fresh prepares if a quorum (2f+1) is formed.
    Raises StaleViewQuorumError if any reachable agent has returned a
    non-prepare reply, because waiting cannot resolve the shortfall.
    """
    quorum_size = 2 * f + 1
    fresh = [a for a, r in replies.items() if r == "PREPARE"]
    stale = [a for a, r in replies.items() if r in ("ALREADY_VOTED", "VIEW_MISMATCH")]

    if len(fresh) >= quorum_size:
        return fresh

    if stale:
        # A reachable agent has already answered for a different view.
        # Waiting or escalating the view will reproduce the stall.
        raise StaleViewQuorumError(
            f"view={view} fresh={len(fresh)}/{quorum_size} "
            f"stale_voters={stale} — targeted view-sync required before "
            f"any view change; do not count stale voters toward quorum."
        )

    # Shortfall is attributable to latency only; caller may wait.
    return fresh
```