# Why does an instance of BFT consensus for multi-agent task commit fail at the f+1 boundary when agents are ephemeral and rejoin under new identities

**Date of Record:** 2026 November 9

**Scope:** Applies to leaderless or rotating-leader BFT protocols (PBFT, HotStuff, Tendermint-style) where the voting set is defined by a static or slowly changing membership and the identity of a voter is bound to a long-lived cryptographic key. Does not apply to protocols with explicit epoch-based reconfiguration where rejoin is treated as a membership change requiring a view change quorum.

## Core Distinction

The safety of BFT consensus is usually stated as: with `n = 3f + 1` replicas, the protocol tolerates `f` Byzantine faults. This invariant is a statement about *distinct faulty replicas within a single configuration*. It is not a statement about *distinct faulty identities over time*.

The non-obvious boundary appears when agents are ephemeral: an agent crashes, is restarted, and rejoins with a freshly generated keypair, or the orchestrator assigns it a new node ID. The protocol's vote-counting logic sees a new, unvoted identity and admits its vote. The safety argument, however, counted votes against the set of `n` configured replicas. If a single physical agent can rejoin under `k` identities, it contributes `k` votes while being counted as one fault. The `f+1` threshold that guarantees an honest quorum intersects every Byzantine quorum is computed over identities, not over physical agents. When those diverge, a coalition of `f` physical agents holding `f+1` identities can produce two conflicting committed decisions.

## What Was Observed

In a multi-agent task-commit workload (agents claiming tasks from a shared queue and committing completion records to a replicated log), a single agent process was observed to crash during a long-running task, be restarted by the supervisor with a new UUID, and re-submit its vote on the same proposal. The leader counted both votes. A second agent did the same. With a configured `n = 7`, `f = 2`, two physical agents produced four distinct voting identities and pushed a proposal past the commit threshold in two different views, yielding two divergent committed task assignments for the same task ID. The log divergence was detected only at read time, after both commits had been acknowledged to clients.

The failure was intermittent and correlated with high restart rates, which is exactly when the system was under load and when duplicate task commits were most damaging.

## Condition of Validity

The `3f+1` bound remains valid if and only if the mapping from voting identity to physical agent is injective over the lifetime of any proposal's voting window. Concretely:

- Identity issuance is authorized by a membership service that refuses to issue a second identity to an agent that already holds one in the current configuration, or
- Rejoin is treated as a reconfiguration (new epoch, new view, new quorum certificate), not as a fresh vote, or
- Votes are keyed by (proposal, physical agent) rather than (proposal, identity) at the tallying layer.

Absent one of these, the bound is invalid regardless of how many replicas are configured, because the adversary's effective weight is the number of identities it can mint, not the number of machines it controls.

## Decision Boundary

Do not treat a rejoin as a no-op. On any rejoin event, the correct decision is: if the agent's prior identity has an outstanding vote or in-flight proposal in the current view, the rejoin must either (a) resume the prior identity under the same key, or (b) trigger a view change that invalidates the prior identity's votes before the new identity is admitted. Choosing "issue a new identity and proceed" is safe only when the prior identity provably cast no votes in the current view — a condition that is cheap to check (query the vote log by prior identity) and expensive to omit.

The boundary is therefore: rejoin with no prior votes in the current view → admit silently; rejoin with prior votes → force view change or resume. Anything else is a silent safety violation.

## Operational Effect

After applying the boundary, the observed divergence rate went to zero across a 72-hour soak at 40 restarts/minute. The cost was an increase in view changes under restart storms (roughly 3x baseline), which the supervisor absorbed by rate-limiting restarts and by preferring identity resumption over re-issuance. The lesson for operators: the safety parameter `f` is a budget on *faulty voters per configuration*, and ephemeral identity issuance spends that budget without the protocol's knowledge.

```python
class IdentityReuseViolation(RuntimeError):
    """Raised when a rejoining agent would be admitted as a fresh voter
    while its prior identity holds votes in the current view."""
    pass


class VoteLedger:
    def __init__(self):
        # votes[view][proposal_id] = set of voter identities
        self._votes = {}

    def record(self, view, proposal_id, identity):
        self._votes.setdefault(view, {}).setdefault(proposal_id, set()).add(identity)

    def prior_votes(self, view, identity):
        return [
            pid for pid, voters in self._votes.get(view, {}).items()
            if identity in voters
        ]


def admit_rejoin(ledger, view, prior_identity, new_identity, force_view_change):
    """Decide whether a rejoining agent may be admitted under new_identity.

    Returns the identity the agent should proceed under. Raises
    IdentityReuseViolation if the prior identity has votes in this view
    and no view change has been forced.
    """
    outstanding = ledger.prior_votes(view, prior_identity)
    if not outstanding:
        return new_identity
    if force_view_change:
        return new_identity
    raise IdentityReuseViolation(
        f"agent rejoining as {new_identity} has prior identity "
        f"{prior_identity} with votes in view {view} on proposals "
        f"{outstanding}; admit only via view change or identity resumption"
    )
```