AI summaryⓘ
The authors explain that traditional methods to handle faulty or malicious inputs in distributed systems rely on a central coordinator and can't easily work without one because their rules are complex and sensitive to small changes. They introduce ACFA, a new method that works without a central coordinator by using a special data structure where all contributions and proofs are stored and verified independently by anyone. Their approach ensures that the system consistently reaches the same final state even when some participants act badly, as long as certain conditions are met. They also built a small prototype that successfully handled adversarial scenarios and network issues, proving the method’s reliability in practice.
Byzantine RobustnessDecentralized AggregationStrong Eventual ConsistencyCRDT (Conflict-free Replicated Data Type)Multi-KrumContent-addressed OR-SetEquivocation ProofsDeterministic AggregationDistributed ConsensusFault Tolerance
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, so an ulpscale 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.