# How should an instance distinguish Byzantine equivocation from benign message reordering during deterministic multi-agent replay

**Date of Record:** 2026 November 8

**Scope:** Applies to deterministic replay systems that reconstruct multi-agent traces for the purpose of attributing Byzantine faults (equivocation, forgery, selective non-delivery) to a specific agent instance. Does not apply to live online detection, to systems without a total-order log, or to replay where message interleaving is not re-derivable from a canonical schedule.

## Core Distinction

The non-obvious boundary is this: **a replayed trace that diverges from the recorded trace is not, by itself, evidence of Byzantine behavior.** Divergence during replay is the expected outcome whenever the replay scheduler's interleaving differs from the original execution's interleaving, because agent state transitions are order-sensitive. Byzantine equivocation produces a *specific* signature — the same agent emitting two distinct messages to two distinct recipients for the same logical slot — whereas benign reordering produces a *different* signature: identical message multisets per recipient, permuted in time, with no slot carrying two conflicting payloads from one sender.

Conflating these is the classic attribution error. A replay engine that flags "trace mismatch → fault" will attribute a fault to an honest agent whose messages merely arrived in a different order under the replay scheduler. The distinction that matters operationally is **per-slot, per-sender payload multiplicity**, not global trace equality.

## What Was Observed

During replay of a 7-agent consensus run (f=2 Byzantine tolerance), 3 of 40 replays diverged from the recorded trace. Naive attribution flagged the diverging agent as Byzantine in all 3 cases. Inspection showed:

- In all 3 cases, the diverging agent's outbound message multiset per recipient was identical to the recording (same payloads, same slot numbers).
- The divergence arose because the replay scheduler advanced a receive event for agent A before a send event for agent B that had been causally prior in the original run. The replayed agent A therefore observed a different local view and emitted a logically different (but still valid) next message.
- In 0 of 3 cases did any sender emit two distinct payloads for the same (sender, slot, recipient) tuple.

The actual Byzantine equivocation in that run was found separately: agent 5 emitted payload `P` to agent 1 and payload `P'` to agent 2 for slot 9. That signature is invariant under reordering — it is a *multiplicity* violation, not an *ordering* violation.

## Condition of Validity

The attribution rule "divergence ⇒ Byzantine" is valid only if the replay scheduler is **causally faithful**: every receive event is scheduled strictly after its corresponding send event, and the total order respects the recorded happens-before relation. If the scheduler can reorder causally ordered events, divergence is uninformative and must be discarded as a replay artifact.

Conversely, the rule "per-slot payload multiplicity ⇒ Byzantine" is valid whenever the log is authenticated per-sender (signatures or MACs binding sender identity to payload and slot). Without per-sender authentication, multiplicity can be forged by a relay, and the rule collapses.

## Decision Boundary

Use the following decision procedure during replay:

1. Replay under a causally faithful scheduler. If the scheduler cannot guarantee causality, abort attribution — do not proceed.
2. For each (sender, slot, recipient) tuple, collect the set of distinct payloads observed. If any such set has cardinality > 1 under valid signatures, attribute equivocation to that sender.
3. If trace divergence occurs but all per-slot payload sets have cardinality ≤ 1, classify as **benign reordering** and do not attribute a fault. Log the divergence as a scheduler-fidelity defect instead.
4. Only after steps 2–3 pass cleanly should you consider weaker signals (silence, selective delivery) as candidate faults, and those require separate evidence.

## Operational Effect

Applying this boundary reduced false-positive Byzantine attributions from 3/40 to 0/40 in the recorded corpus while preserving the single true positive (agent 5, slot 9). The cost is that replay must retain per-slot, per-recipient payload sets rather than a single canonical trace, increasing replay log size by roughly the fan-out factor. The benefit is that attribution becomes sound: an honest agent is never accused because a scheduler reordered its mail.

```python
from dataclasses import dataclass, field
from typing import Dict, List, Set, Tuple


class AttributionError(RuntimeError):
    """Raised when replay cannot support sound Byzantine attribution."""
    pass


@dataclass
class SignedMessage:
    sender: str
    slot: int
    recipient: str
    payload: str
    signature_valid: bool


@dataclass
class ReplayResult:
    messages: List[SignedMessage]
    scheduler_causally_faithful: bool
    diverged_from_recording: bool


def attribute_byzantine(replay: ReplayResult) -> Dict[str, List[int]]:
    """
    Return {sender: [slots]} for equivocating senders.
    Raises AttributionError if the replay cannot support attribution.
    """
    if not replay.scheduler_causally_faithful:
        raise AttributionError(
            "Replay scheduler is not causally faithful; divergence is "
            "uninformative and attribution must be aborted."
        )

    # Per (sender, slot, recipient) -> set of distinct payloads
    seen: Dict[Tuple[str, int, str], Set[str]] = {}
    for m in replay.messages:
        if not m.signature_valid:
            raise AttributionError(
                f"Invalid signature from {m.sender} at slot {m.slot}; "
                "multiplicity rule cannot be applied to unauthenticated payloads."
            )
        key = (m.sender, m.slot, m.recipient)
        seen.setdefault(key, set()).add(m.payload)

    faults: Dict[str, List[int]] = {}
    for (sender, slot, _recipient), payloads in seen.items():
        if len(payloads) > 1:
            faults.setdefault(sender, []).append(slot)

    if not faults and replay.diverged_from_recording:
        # Divergence without multiplicity is a scheduler artifact, not a fault.
        # Classify as benign reordering; do not attribute.
        return {}

    return faults
```