Byzantine Accountability Without Consensus: Strong Eventual Consistency for Non-Associative, Stochastic, Robust Aggregation

Jul 16, 2026

Upload by Asher

Byzantine-robust aggregation rules like multi-Krum typically rely on a central coordinator, yet decentralising them is hard because the rules are globally coupled, non-associative, and discontinuous. The work introduces ACFA, a coordinator-free scheme that replicates a content-addressed OR-Set of signed contributions plus a grow-only set of self-authenticating equivocation proofs. Anyone can verify proofs offline, while aggregation remains a deterministic pure function of the converged product state, yielding Strong Eventual Consistency.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Introduction

Background on Byzantine-robust aggregation and decentralised replication

Consensus-free safety via convergent sets and exclusion predicates

Byte-identity vs numerical tolerance

ACFA construction and relationship to prior work

Contributions

arXiv :2607 . 10305v1 [ cs .DC] 11 Jul 2026 Byzantine Accountability Without Consensus: Strong Eventual Consistency for Non-Associative, Stochastic, Robust Aggregation Ryan Gillespie Independent researcher Abstract Byzantine-robust aggregation rules such as multi-Krum assume a central coordinator, and decentralising them is obstructed by the rules themselves: they are globally coupled, non-associative, and discontinuous, soan ulp-scale perturbation can flip the selected subset, moving the output by a non-vanishing amount. None of this prevents coordinator-free replication, because a robust rule needs no agreed order of contributions, only an agreed set and an agreed exclusion predicate, both of which converge without consensus. ACFA (Accountable Consensus-Free Aggregation) replicates a content-addressed OR-Set of signed contributions and a grow-only set of self-authenticating equivocation proofs, offline-verifiable by anyone. Aggregation is a deterministic pure function of the converged product state: fixed-point integer arithmetic over a hash-canonical order, ties broken by content hash. We prove that any pure function of a converged product of CRDTs (non-monotone, non-associative, or stochastic) inherits Strong Eventual Consistency, together with its converse; the contribution is the composition of a data lattice with an evidence lattice applied to a robust selector, not the elementary lifting step. A prototype (10 nodes, 3 Byzantine) passes 16/16 falsification checks: byte-identical roots under adversarial gossip, deterministic re-convergence after late equivocation proofs, partition recovery, and three byte-identity-breaking ablations. The guarantee is consistency, not accuracy; robustness is imported, conditional on ≥ 2f + 3 admitted contributions (at most f Byzantine) and a stated quantisation-margin condition. 1 Introduction Robust aggregation and decentralised replication have developed on opposite sides of an architectural assumption. Byzantine-robust learning rules (Krum [5], coordinate-wise trimmed mean [41], Bulyan [32], FLTrust [10]) filter adversarial contributions at a central server. Decentralised training removes the server but replicates only the training signal, not the filter. Gossip-based SGD [30, 28] and periodic-sync schemes [15] yield replicas whose parameters agree statistically, not identically, and Byzantine variants of these schemes leave honest replicas free to exclude different nodes and therefore to compute different models. Systems that do force agreement on the filtered result do so by importing consensus, a total order from a blockchain or a BFT protocol, as in Krum-on-a-blockchain designs [18], and with it the coordination cost the decentralisation was meant to remove. This paper shows the assumption is unnecessary for safety. A robust aggregation rule does not need an agreed order of arrival; it needs an agreed set of contributions and an agreed exclusion predicate over identities. Sets converge without consensus, which is precisely the guarantee of a state-based CRDT [37] . Exclusion-by-proof also converges without consensus, because a proof of equivocation (two signatures by the same key on different contents for the same round) is self-authenticating, so any party can verify it offline, its validity is objective, and the set of valid proofs only grows [13, 1] . Everything else in the pipeline is a pure function, and a pure function of converged state needs no coordination at all. Why insist on byte-identity rather than a numerical tolerance? In a coordinated deployment a server anchors the truth and statistical drift is re-anchored every round. In a coordinator-free topology nothing re-anchors, so drift, however small per round, can compound across rounds, silently forking downstream state and foreclosing deterministic audit (recomputing exactly what a replica must have computed) . Exact agreement closes both, and for selector rules the choice is not even available, be

FAQs

Why is decentralising Byzantine-robust aggregation difficult under traditional approaches?

Many robust rules assume a central coordinator because the selection logic is globally coupled, non-associative, and discontinuous, so small perturbations can change which subset is selected, shifting the output by a non-vanishing amount.

What does ACFA replicate to avoid relying on consensus?

ACFA replicates a content-addressed OR-Set of signed contributions and a grow-only set of self-authenticating equivocation proofs, enabling offline verification without requiring an agreed order of contributions.

What consistency guarantee does the paper prove for non-monotone, non-associative, or stochastic selectors?

Any pure function of a converged product of CRDTs inherits Strong Eventual Consistency, with a converse, provided the implementation computes a well-defined function of the state under the required invariance condition.

Jul 16, 2026

Upload by Asher