Distributed systems that must agree on a number, such as a price oracle reporting Bitcoin's value or a drone swarm agreeing on a target's position, face a choice. They can assume the network delivers every message within a known delay, which lets them tolerate up to half the nodes lying. Or they can assume nothing about delays, which keeps them safe through outages but caps the tolerable liars at a third. A line of theory called network-agnostic (or "best-of-both-worlds") protocol design shows that one protocol can get both. It tolerates $t_s$ liars when the network behaves and still tolerates $t_a$ liars when it does not, without ever knowing which case it is in, provided $2t_s + t_a < n$. None of these protocols has ever been run. The papers that establish them report no implementation, no testbed, and no dataset.
This note proposes the first implementation and measurement study of network-agnostic approximate agreement. Approximate agreement is the task where honest nodes must output values within $\epsilon$ of each other and inside the range of honest inputs. The study is framed around one question that decides whether the theory matters in practice: per extra liar tolerated, is it cheaper to run a network-agnostic protocol, or to keep a purely asynchronous protocol and simply add nodes? The question is asked on the real oracle and sensor workloads used by the strongest existing asynchronous system, under network traces that switch between calm and disrupted periods.
Core Claim
The theory says the agnostic protocol saves nodes. With $t_a$ small, it needs $n > 2t_s + t_a$ where an asynchronous protocol needs $n > 3t$. It does not say what that saving costs. The protocol waits out a timeout $\Delta$ in each synchronous-style step, and it performs extra truncation and overlap broadcasts. We claim the decisive practical quantity is a cost-per-tolerated-fault frontier: latency and bytes to reach $\epsilon$-agreement, plotted against the number of Byzantine nodes tolerated, for a fixed honest workload and a fixed network trace.
Our hypothesis is twofold and falsifiable. First, on geo-distributed latency where the chosen $\Delta$ covers most rounds, the agnostic protocol dominates an asynchronous protocol scaled up to equal fault tolerance. It wins on total bandwidth, because it uses fewer nodes in a cubic-communication regime. Second, its latency penalty is bounded by roughly one $\Delta$ per iteration and does not blow up during recovery after a partition. If either half fails, the honest conclusion is that the resilience gain does not pay for itself, and the study will report that.
The motivation comes from four theory papers that leave a measurable gap. Optimal Synchronous Approximate Agreement with Asynchronous Fallback gives the tight $2t_s + t_a < n$ protocol $\Pi_{AA}$, built from an "overlap all-to-all broadcast" and a truncation step. Multidimensional Approximate Agreement with Asynchronous Fallback extends it to vectors at the price $(D+1)t_s + t_a < n$. Meeting in a Convex World generalizes to abstract convexity spaces, at $O(n^3\ell + n^4\kappa)$ bits. Validity in Network-Agnostic Byzantine Agreement characterizes which output guarantees are achievable at all. All four prove feasibility, and none measures anything.
What Is Different From the Closest Work
The closest existing system is Delphi. Delphi is an asynchronous, signature-free approximate agreement protocol with $O(n^2)$ messages. It relaxes validity under a thin-tail assumption on honest inputs and is evaluated on AWS and Raspberry Pi clusters with Bitcoin feeds and drone detection data. Delphi is the empirical template we adopt: same workloads, same style of testbed. It is also the main competitor. But it is asynchronous-only ($t < n/3$) and never exploits calm periods.
The Byzantine-robust federated learning benchmarks evaluate the opposite extremes and do not run agreement protocols among peers. Blades and Distributed Momentum use lockstep synchronous rounds with a trusted server. AFLGuard is purely asynchronous and relies on a server-held clean dataset.
We deliberately do not target high-dimensional model updates. The $(D+1)t_s + t_a < n$ bound tolerates essentially zero faults when $D$ is a parameter count, so we restrict vectors to $D \le 3$, which covers sensor positions. Pretending otherwise would bury the useful result under a vacuous one.
Research Program
We will build three things.
The first is a faithful open-source implementation of $\Pi_{AA}$ and of the low-dimensional protocol from the multidimensional paper. Both are written against a single message layer, with $n$, $t_s$, $t_a$, $\Delta$ and $\epsilon$ as parameters. Each protocol step will carry checks that assert the paper's lemmas, such as non-empty truncated ranges and the expected shrinkage of the honest range per iteration. Every run therefore doubles as a test of the proofs' preconditions.
The second is a network harness that replays regime-switching latency traces. A trace runs at measured geo-distributed delays for $R$ rounds, injects a partition or lag spike exceeding $\Delta$ for $K$ rounds, then recovers. The harness runs on both a multi-region cloud deployment and a small embedded cluster, mirroring Delphi's two testbeds.
The third is an adversary library aimed at the ambiguity the theory is built around. One strategy, delay-and-silence, has Byzantine nodes go quiet exactly when honest messages are slowed, so silence looks like lateness. A second injects extreme values at the truncation boundary. A third sends split views, with different values to different honest nodes.
The analysis then produces the cost-per-fault frontier. It also produces a Δ-calibration curve: the fraction of rounds in real traces where actual delay stayed under $\Delta$. That fraction is the empirical probability that the protocol's stronger synchronous guarantee actually applied. Finally, it produces recovery profiles showing how many iterations the protocol needs to return to its calm-period convergence rate after a partition.
Baselines
The naive reference point is a timeout-then-trimmed-mean scheme. Each node waits $\Delta$, discards the $t$ lowest and highest values it received, and averages the rest. It is the protocol an engineer writes without the theory. It shows whether the overlap broadcast and the two-threshold truncation do anything, and it will be run with the same $n$, $\Delta$ and traces.
The strongest existing method is Delphi, run on its own Bitcoin and drone workloads. On Bitcoin feeds its paper reports a 0.05% error relative to the honest average. On the AWS testbed it reports latency "3x faster" than FIN and Abraham et al. In the 160-node drone setting it reports being "8x faster" than prior baselines. For fairness, Delphi gets the same machines, the same traces and the same $\epsilon$. It is scaled to $n = 3f + 1$ for each target fault count $f$, while the agnostic protocol uses $n = 2f + t_a + 1$. Beating Delphi means lower total bytes and comparable or better time to agreement at equal tolerated $f$, with output error no worse than 0.05% on the Bitcoin workload. Matching Delphi's raw latency at its own $n$ is not the bar, since Delphi will almost surely win there. The comparison is per tolerated fault.
A second strong baseline is a classical asynchronous approximate agreement protocol at $t < n/3$, built on reliable broadcast. It isolates the cost of the synchronous phase, since it shares the agnostic protocol's message structure but omits the timeouts. Where possible we will also include the quadratic-communication asynchronous protocol of Asynchronous Approximate Agreement with Quadratic Communication. No reported result was found on Lacuna for either $\Pi_{AA}$ or that quadratic protocol on any workload, so our runs are the first numbers.
Two ablations isolate the key ingredient. One replaces the overlap all-to-all broadcast with plain all-to-all sends. The other sets $t_a = t_s$, which collapses the two-threshold truncation into a single threshold. If neither ablation degrades safety under the delay-and-silence adversary, the distinctive machinery is not earning its cost.
Why not just…?
Why not just run a synchronous protocol with a generous timeout? Under the theory's model, once a delay exceeds the timeout, a synchronous protocol can lose safety outright, as the validity paper's impossibility results imply. A generous timeout also makes every round as slow as the worst case. This is a fair challenge, though: on cloud traces, delays may almost never exceed a large timeout. The Δ-calibration curve and the partition-injection runs settle it directly. We will report how often a large-timeout synchronous baseline violates the $\epsilon$-range or validity under real spikes and under the delay-and-silence adversary. If it never does at an acceptable latency, network-agnosticism is insurance against events our traces do not contain, and we will say so.
Why not just use Delphi and add nodes? This is the real threat, and it is why the study is framed per tolerated fault. Delphi's quadratic communication may outweigh the node savings of the agnostic protocol, whose overlap broadcast is cubic. The frontier experiment answers this. A plausible outcome is a crossover: the agnostic protocol wins at small $n$, where node count dominates cost, and Delphi wins at large $n$. Locating that crossover is itself a deliverable.
Why not just use a trusted-server defense like AFLGuard? AFLGuard needs an honest aggregator holding clean reference data, as its paper states. Oracles and swarms have no such party. We therefore treat it as out of scope rather than as a competitor, and do not run it.
Proposed Experiments
The first experiment is the frontier. For $f \in \{1,\dots,10\}$, on the Bitcoin feeds from 10 exchanges and on the drone detection error distributions, we run the agnostic protocol, Delphi, and asynchronous reliable-broadcast agreement at their minimal $n$ for that $f$. Each run uses calm geo-distributed traces, and we measure median and 99th-percentile time to $\epsilon$-agreement, total bytes, and error relative to the honest mean.
The second is regime switching. We sweep $R$ and $K$ in calm–partition–calm traces and record per-iteration convergence. The decisive check is whether post-recovery convergence returns to its calm rate within a constant number of iterations, as the theory's structure suggests. A long stall during recovery would falsify the claim.
The third is the ambiguity attack. We run the delay-and-silence and split-view adversaries at $t_s$ near $(n - t_a - 1)/2$, the regime only the agnostic protocol claims. The decisive checks are zero validity violations for the agnostic protocol, and measured violations for the naive trimmed-mean and large-timeout baselines.
The fourth is a low-dimensional extension. We repeat the frontier experiment for $D = 2$ drone positions with the multidimensional protocol, timing the local safe-area computation separately. This measures how much of the cost is geometry rather than communication.
References
- Optimal Synchronous Approximate Agreement with Asynchronous Fallback
- Multidimensional Approximate Agreement with Asynchronous Fallback
- Meeting in a Convex World: Convex Consensus with Asynchronous Fallback
- Validity in Network-Agnostic Byzantine Agreement
- Delphi: Efficient Asynchronous Approximate Agreement for Distributed Oracles
- Demo Abstract: Blades: A Unified Benchmark Suite for Byzantine-Resilient in Federated Learning
- Distributed Momentum for Byzantine-resilient Stochastic Gradient Descent
- AFLGuard: Byzantine-robust Asynchronous Federated Learning
- Asynchronous Approximate Agreement with Quadratic Communication