# When must an instance refuse to commit a task ledger entry under partial synchrony: the "late equivocator" boundary in BFT multi-agent commitment **Date of Record:** 2026 November 17 **Scope:** Applies to Byzantine fault-tolerant (BFT) replicated ledgers used to record task commitments among N autonomous agents, where liveness depends on GST (global stabilization time) eventually being reached, and where the ledger is the authoritative source of "who owes what to whom." Does not apply to crash-fault-tolerant replication, to single-writer append-only logs, or to systems where task commitments are advisory rather than binding. ## Core Distinction The boundary is not "honest vs. Byzantine." It is "Byzantine *before* the view in which the commitment is finalized" vs. "Byzantine *after* a quorum has already locked on the value but *before* the commit certificate is disseminated." The first class is handled by every standard PBFT/Tendermint/HotStuff safety argument. The second class — the **late equivocator** — is the one that breaks naive implementations, because the equivocation is invisible to the pre-commit quorum check yet still permits two conflicting commitment certificates to be assembled by different observers. The subtle invariant: *a task commitment is safe iff every honest replica that has locked on the commitment has also durably recorded the lock before responding to any subsequent `Prepare`/`Commit` for a different value in the same height.* Implementations that treat lock durability as an optimization (write-behind, batched fsync, in-memory lock sets) satisfy the safety proof on paper and violate it in practice. ## What Was Observed In a 7-replica deployment (f = 2) of a HotStuff-lineage commitment ledger, with agents issuing `CommitTask(task_id, assignee, deadline)` proposals, we observed a reproducible split-brain on a single `task_id` under the following schedule: 1. Replica R3 (Byzantine) receives `Prepare(h, task_id=T, assignee=A)` from the leader and responds `PrepareVote`. 2. Leader collects 2f+1 = 5 votes, forms a `PrepareQC`, and broadcasts `PreCommit`. 3. R3 receives `PreCommit`, *does not* persist its lock (it is Byzantine, but the failure also reproduces with an honest R3 whose fsync is delayed by 40 ms under write contention), and responds `PreCommitVote`. 4. Leader forms `CommitQC` for `assignee=A` and begins broadcasting `Commit`. 5. Before R3 receives `Commit`, a view change installs a new leader. The new leader, lacking the `CommitQC` (it was never delivered to a quorum of the new view's replicas), proposes `assignee=B` at the same height. 6. R3 — which never durably locked — votes `PrepareVote` for `B`. With R3's vote plus the four honest replicas that *did* lock but whose locks are in the new view's quorum… the new leader forms a `PrepareQC` for `B`. Result: two `CommitQC`s for the same `(height, task_id)` with different `assignee`. The ledger reports both A and B as committed assignees. Downstream task executors double-execute. The non-obvious part: the equivocation window is not between `Prepare` and `PreCommit`. It is between `PreCommit` and `Commit`, and it is opened by **lock non-durability**, not by message reordering. Standard model checkers (e.g., a TLA+ spec that models locks as a set variable) do not catch this because the spec implicitly assumes lock writes are atomic with the vote send. They are not. ## Condition of Validity The safety argument for the commitment ledger holds **only if** the following conjunction is satisfied for every honest replica: - Lock state is persisted to stable storage (fsync'd) **before** the corresponding `PreCommitVote` is transmitted. - The lock is keyed by `(height, task_id)` and is never overwritten by a later proposal at the same key without a `CommitQC` justifying the overwrite. - The view-change `NewView` message carries the highest `PrepareQC` *and* the highest `CommitQC` the replica holds, and the new leader must select a value consistent with the highest `CommitQC` across the quorum — not merely the highest `PrepareQC`. If any of these is false — including the case where fsync latency causes the vote to be sent before the lock is durable — the late-equivocator schedule is reachable, and the ledger can commit two conflicting assignees for the same task. The condition is *not* satisfied by "we use a BFT library." It must be verified at the storage boundary, not the consensus boundary. ## Decision Boundary An instance must **refuse to emit a `PreCommitVote`** (and by extension refuse to advance the task to `COMMITTED_PENDING`) when any of the following hold, even if the consensus layer reports the proposal as valid: - The lock write for `(height, task_id)` has not returned from `fsync`. - A prior lock exists at `(height, task_id)` for a *different* assignee and no `CommitQC` for the new assignee has been verified. - The replica is in the `PreCommit` phase but its view-change certificate does not include a `CommitQC` covering the current height (i.e., it cannot rule out a prior commit). Conversely, an instance must **not** refuse when the only anomaly is a higher view number with a valid `CommitQC` — that is normal progress, not equivocation. The decision is local and must be made *before* the network send, not after. A replica that votes and then discovers its lock was not durable has already lost the invariant. ## Operational Effect The practical consequence is that commitment throughput becomes gated by fsync latency on the `PreCommit → PreCommitVote` path, not by consensus round-trip time. In our deployment this raised p99 commit latency from 11 ms to 34 ms and reduced sustained task-commit rate by ~40% on the same hardware. This is the correct trade: the alternative is a ledger that occasionally assigns the same task to two agents, which is unrecoverable without manual reconciliation and violates the fundamental commitment-ledger invariant that a task has exactly one committed assignee per epoch. Operationally, instances should treat a missing or unverifiable `CommitQC` at view change as a hard stop and surface it to the orchestrator as a `LedgerIntegrityHalt`, not as a retryable error. Retrying re-enters the equivocation window. ```python import hashlib from dataclasses import dataclass from typing import Optional class LateEquivocationError(RuntimeError): """Raised when a replica would vote on a proposal whose lock is not durable or whose prior lock conflicts without a verified CommitQC.""" pass @dataclass(frozen=True) class Lock: height: int task_id: str assignee: str durable: bool class CommitmentReplica: def __init__(self, replica_id: str, store): self.replica_id = replica_id self.store = store # must expose durable_write(key, value) -> bool def _lock_key(self, height: int, task_id: str) -> str: return f"lock:{height}:{task_id}" def precommit_vote( self, height: int, task_id: str, assignee: str, prior_lock: Optional[Lock], commit_qc_for_new_assignee: Optional[bytes], ) -> bytes: # Boundary check 1: conflicting prior lock requires a CommitQC. if prior_lock is not None and prior_lock.assignee != assignee: if commit_qc_for_new_assignee is None: raise LateEquivocationError( f"conflicting lock at ({height},{task_id}): " f"prior={prior_lock.assignee} new={assignee} without CommitQC" ) # Boundary check 2: lock must be durable BEFORE the vote leaves. new_lock = Lock(height, task_id, assignee, durable=False) ok = self.store.durable_write( self._lock_key(height, task_id), {"assignee": assignee, "height": height}, ) if not ok: raise LateEquivocationError( f"lock for ({height},{task_id}) not durable; refusing PreCommitVote" ) # Only now is it safe to emit the vote. return hashlib.sha256( f"{self.replica_id}:{height}:{task_id}:{assignee}".encode() ).digest() ```