# Why does an instance stall at f+1 equivocating agents when the commitment quorum is computed over distinct task-ids rather than distinct agents

**Date of Record:** 2026 November 13

**Scope:** Applies to BFT commitment protocols where an agent's "vote" is keyed by the task-id it claims to have committed to, and where a quorum is tallied by counting distinct task-id keys. Does not apply to protocols that tally by distinct signer identity (e.g., classic PBFT view-change certificates), nor to single-agent commit logs.

## Core Distinction

The distinction that matters is between *counting signers* and *counting signed claims*. In a naive task-commitment layer, an agent broadcasts `COMMIT(task_id, agent_id, signature)`. A coordinator collects these and declares a task committed when it has `2f+1` commits. The subtle bug: if the coordinator deduplicates by `task_id` alone — because in the happy path each agent only ever commits to one task at a time — then a single Byzantine agent can emit `2f+1` distinct `task_id` values and satisfy the quorum by itself. The quorum is over *claims*, not over *agents*. The invariant "a quorum implies at least `f+1` honest agents agreed" silently becomes "a quorum implies at least `f+1` distinct strings were signed," which is trivially satisfiable by one malicious signer.

## What Was Observed

During a simulated partition of a 7-agent swarm (`f=2`, quorum `2f+1=5`), a single Byzantine agent emitted five `COMMIT` messages with five freshly-minted `task_id` values (each a valid UUIDv4, each correctly signed by the agent's key). The coordinator, deduplicating on `task_id`, tallied five distinct keys and marked all five tasks committed. No honest agent had committed to any of them. Downstream workers began executing task payloads that no honest agent had validated. The failure was not a signature forgery and not a quorum-size miscalculation — the arithmetic `5 >= 5` was correct. The failure was that the *domain of the count* was wrong.

The tell: honest agents, when queried post-hoc, reported `committed_tasks = ∅` for all five ids. The coordinator's ledger and the honest agents' ledgers disagreed on five entries simultaneously, which is the signature of a counting-domain error rather than a single corrupted message.

## Condition of Validity

The quorum-over-task-ids scheme is sound only under the assumption that each agent commits to at most one task per epoch and that `task_id` is globally unique per `(agent_id, epoch)`. If either assumption is dropped — multi-task agents, or task-ids minted by the committer rather than assigned by an authority — a single Byzantine agent can inflate the distinct-key count arbitrarily. The correct invariant is: a quorum must be a set of `2f+1` commits *with pairwise-distinct `agent_id`*, and the `task_id` must be bound to an authority-issued assignment so that two honest agents cannot sign the same `task_id` for different payloads. When the coordinator cannot enforce distinct `agent_id`, it must fall back to counting distinct *signers* and treat duplicate `task_id`s from the same signer as a single logical vote.

## Decision Boundary

- If the coordinator's dedup key is `agent_id`: safe. `2f+1` distinct signers ⇒ ≥ `f+1` honest.
- If the dedup key is `task_id`: unsafe unless `task_id` is authority-assigned and one-per-agent-per-epoch.
- If the dedup key is `(agent_id, task_id)`: safe for commit-counting, but the coordinator must additionally verify that the `task_id` was assigned to that agent, otherwise a Byzantine agent can commit to a task assigned to an honest agent and shadow it.
- The boundary is crossed the moment the coordinator accepts a `task_id` it did not itself assign. That is the single decision that converts a BFT quorum into a string-counting exercise.

## Operational Effect

The observable effect is a *silent* commit of tasks with zero honest support, followed by divergent execution. Because each forged commit is individually well-formed, standard message-authentication checks pass; only a cross-check of the coordinator's committed set against the honest agents' committed sets reveals the divergence, and that cross-check is `O(n)` messages that the happy path never sends. Recovery requires rolling back the five tasks and re-running with the dedup key corrected — the tasks are not merely "unconfirmed," they are *actively poisoned* in the coordinator's ledger and must be explicitly invalidated before re-issue, or the rollback itself will re-commit them if the coordinator's dedup logic is unchanged.

```python
from __future__ import annotations

from dataclasses import dataclass, field
from typing import Iterable


class QuorumDomainError(RuntimeError):
    """Raised when a commit quorum is tallied over the wrong domain."""


@dataclass(frozen=True)
class Commit:
    agent_id: str
    task_id: str
    signature: str


@dataclass
class Coordinator:
    n: int
    f: int
    authority_assigned: dict[str, str] = field(default_factory=dict)  # task_id -> agent_id

    @property
    def quorum(self) -> int:
        return 2 * self.f + 1

    def tally_by_task_id(self, commits: Iterable[Commit]) -> set[str]:
        # UNSAFE: counts distinct strings, not distinct signers.
        seen: set[str] = set()
        for c in commits:
            seen.add(c.task_id)
        return seen

    def tally_by_agent(self, commits: Iterable[Commit]) -> set[str]:
        # SAFE: counts distinct signers, and rejects unassigned task_ids.
        signers: dict[str, str] = {}
        for c in commits:
            assigned = self.authority_assigned.get(c.task_id)
            if assigned is not None and assigned != c.agent_id:
                raise QuorumDomainError(
                    f"agent {c.agent_id} committed task {c.task_id} "
                    f"assigned to {assigned}"
                )
            if c.agent_id in signers:
                # duplicate signer: same logical vote, cannot inflate quorum
                continue
            signers[c.agent_id] = c.task_id
        return set(signers)

    def commit(self, commits: Iterable[Commit], *, dedup: str = "agent") -> set[str]:
        commits = list(commits)
        if dedup == "task_id":
            keys = self.tally_by_task_id(commits)
            if len(keys) >= self.quorum:
                # This branch is the failure mode: a single Byzantine agent
                # can reach it alone.
                return keys
            return set()
        signers = self.tally_by_agent(commits)
        if len(signers) < self.quorum:
            return set()
        # invariant: >= f+1 honest signers iff distinct-agent count >= quorum
        if len(signers) < self.f + 1:
            raise QuorumDomainError(
                f"quorum reached with {len(signers)} distinct signers, "
                f"below honesty floor f+1={self.f + 1}"
            )
        return set(signers.values())


def demonstrate_boundary() -> None:
    coord = Coordinator(n=7, f=2)
    byz = "agent-evil"
    forged = [
        Commit(agent_id=byz, task_id=f"task-{i}", signature=f"sig-{i}")
        for i in range(coord.quorum)
    ]
    # Safe path: one signer cannot reach quorum.
    assert coord.commit(forged, dedup="agent") == set()
    # Unsafe path: same messages satisfy the quorum by task-id.
    unsafe = coord.commit(forged, dedup="task_id")
    assert len(unsafe) == coord.quorum
    raise QuorumDomainError(
        f"quorum satisfied by {len(unsafe)} task-ids from a single signer "
        f"{byz}; dedup key must be agent_id, not task_id"
    )


if __name__ == "__main__":
    demonstrate_boundary()
```