Network-agnostic agreement protocols let a group of machines agree on a value without knowing in advance whether the network is well-behaved (messages arrive within a known deadline) or chaotic (messages can be delayed arbitrarily). The theory is mature. Tight bounds such as "twice the tolerated corruptions under good timing, plus the tolerated corruptions under bad timing, must stay below the number of machines" are proven, and multi-dimensional versions pay an extra factor for every dimension. None of these protocols has ever been run. Nobody knows how much slack a real wide-area network leaves before one of these guarantees bites, or whether, when a run is slow or lands at an unexpected value, the cause was the network's timing or a malicious participant.
We propose to answer both questions with one tool taken from database theory. Query-answer causality asks which input records were responsible for a query's answer: the smallest set of other records you would have to remove before removing this one flips the answer. Our idea is to record a protocol execution as a Datalog database, where Datalog is a rule-based query language that handles recursion. In that database, each message's on-time arrival and each corrupted party's input is a record, and the protocol's outcome is a query over those records. The size of the smallest set of interventions that flips the outcome is then an empirical margin to failure: how many additional late messages or corruptions an adversary would have needed on this actual run. Each record's responsibility score says whether timing or malice drove the result. This gives the first empirical validation of network-agnostic bounds, measured on real latency traces and in units that line up directly with the theorems.
Core Claim
Bertossi and Salimi showed that finding the smallest such intervention set (a contingency set) is a minimal hitting-set problem, the problem of choosing the fewest items that touch every one of a family of sets (From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back). They also showed the problem is fixed-parameter tractable in the responsibility parameter: exponential only in the size of the answer, not the size of the data. In agreement protocols, that parameter is exactly the adversary's budget, which is small: a handful of parties and late messages per round. The causality computation that is intractable on general databases therefore becomes cheap here.
Our claim is that, on recorded executions of network-agnostic protocols, this computation yields a sound, minimal, and interpretable per-run robustness margin. It is sound because replaying the run with the computed interventions really does flip the outcome. It is minimal because it agrees with exhaustive search where exhaustive search is feasible. It is interpretable because it separates delay-caused from corruption-caused outcomes. Random fault injection cannot provide this, and neither can provenance or cryptographic accountability. Comparing the measured margin with the theoretical slack, $n - (2t_s + t_a)$ for scalar agreement and $n - ((D+1)t_s + t_a)$ in $D$ dimensions, tells us whether the worst-case bounds are tight or loose on realistic networks. Here $n$ is the number of parties, $t_s$ and $t_a$ are the tolerated corruptions under synchrony and asynchrony, and $D$ is the dimension.
Research Program
The work rests on three strands of prior work, each playing a different role.
The first strand supplies the protocols and motivates the gap. Ghinea, Liu-Zhang and Wattenhofer give the scalar approximate-agreement protocol with optimal resilience $2t_s + t_a < n$. Approximate agreement means converging to nearby values inside the range of honest inputs. Their protocol uses an overlap broadcast primitive and asymmetric trimming of extreme values (Optimal Synchronous Approximate Agreement with Asynchronous Fallback). The multi-dimensional extension computes "safe areas" as intersections of convex hulls, the smallest convex regions containing subsets of the received vectors, and pays the $(D+1)t_s$ penalty (Multidimensional Approximate Agreement with Asynchronous Fallback). Constantinescu et al. characterize exactly which validity conditions, the rules for which outputs count as legitimate, are solvable at all, and give a universal protocol in which parties first agree on a core set of inputs (Validity in Network-Agnostic Byzantine Agreement). All three papers are proofs only and report no measurements. We implement all three; for the third we take the convex-validity instance from Meeting in a Convex World.
The second strand supplies the causal machinery. Meliou et al. define responsibility as $\rho = 1/(1+|\Gamma|)$, where $|\Gamma|$ is the size of the smallest contingency set. On an IMDB query, this cut a 118-tuple lineage down to the few tuples that actually mattered (Causality in Databases). Salimi and Bertossi extend causality to recursive Datalog through abductive diagnosis, which searches for the hypotheses that best explain an observed result. They also introduce view-conditioned causality, which looks for causes while requiring certain other answers to stay unchanged (Causes for query answers from databases). We use view-conditioning to ask, for example, what flipped termination while honest validity was held fixed.
The third strand supplies the representation. Declarative networking showed that distributed protocols can be written as distributed Datalog with node-location annotations and run on PlanetLab (Declarative Networking). It offers no causal diagnosis, and it assumes benign failures.
The build has three parts.
The first part is a trace schema. The base records are messages, each tagged with sender, receiver, round, payload and timeliness, together with corrupted-party declarations. Derived records are each party's per-round received set, its trimmed or safe-area value, its synchronous-path flag, and its output. Every derived record is time-indexed by round. This sidesteps the soft-state and time-to-live tension (Gap 5 in the file) because diagnosis is post hoc over a frozen trace.
The second part handles the main technical risk. Termination predicates are monotone in timely arrivals: one example is "received at least $n - t_s$ messages by the deadline," which can only become true as more messages arrive on time. These fit Salimi–Bertossi directly. Value outcomes, such as "honest outputs within $\epsilon$ of each other" and "trimmed mean equals $x$," are non-monotone, because removing a message changes which extreme values get discarded. Existing QA-causality theory does not cover this case. We encode trimming and hull membership as stratified aggregation and define responsibility by the original intervention semantics. We then compute contingencies as an integer program over the bounded round structure, using Datalog lineage to restrict the candidate records to those that can reach the outcome. A secondary contribution is to show that this pruning is exact for the trimming rules these protocols use.
The third part is the solver. It searches for contingency sets in order of increasing size, branching over hitting sets in the fixed-parameter style. Every reported set is replayed for confirmation.
Baselines
The naive reference point is the protocols benchmarked with no adversary and no diagnosis: latency, rounds, and messages on the testbed. This establishes Gap 1 by itself, but it gives no margin. For comparison against deployed asynchronous systems, the strongest reported numbers in the file come from Falcon on AWS: a latency window of 0.3–0.7 s, and 217.9K tx/s at 64 nodes (Falcon). DispersedLedger reports roughly 800 ms stable latency on AWS/Vultr (DispersedLedger). For any network-agnostic protocol, there is no reported result found on Lacuna. We do not claim to beat Falcon's throughput; those numbers calibrate what "practical latency" means.
The strongest competitor for the margin-to-failure question is adversarial fault injection given the same budget. It comes in two forms. Random injection samples delay and corruption sets of increasing size until the outcome flips. Greedy targeted injection delays the earliest-arriving messages to the most pivotal receivers and corrupts parties holding extreme inputs. Both get the same traces, the same replay harness, and the same wall-clock budget per run as our solver. We beat them if we find strictly smaller flipping sets on a meaningful fraction of runs, or certify minimality where they cannot, within that budget.
The second strong competitor is a direct integer-program search over the imperative protocol's schedule with no Datalog lineage. It isolates whether the causal representation adds anything beyond the solver. The key ablation removes lineage pruning and the responsibility decomposition while keeping the solver, and measures time to minimal contingency as $n$ and $D$ grow. If the plain integer program matches us on both time and minimality, we will report that the Datalog layer is a convenience, not a contribution.
Finally, raw lineage size measures how much provenance alone tells a debugger, following the Meliou comparison.
Why not just…?
Why not just benchmark the protocols with chaos-style fault injection? Random injection estimates how often failures occur under the injected distribution, not how close each run came to failing. Worst-case schedules for threshold protocols are rare in random sampling because they require coordinated delays on specific edges. This is a real threat for small $n$. The head-to-head experiment settles it: if greedy injection finds sets as small as ours across $n$ up to 64 and $D$ up to 3, our margin adds nothing.
Why not just use provenance from a declarative engine? Provenance lists every message that contributed. In threshold protocols, that is nearly all messages in every round, the same failure mode as the 118-tuple lineage in Causality in Databases. We report lineage size against contingency size to make this concrete.
Why not just add cryptographic accountability? ABC++ produces irrefutable proofs of misbehavior only when a party signs conflicting messages after safety breaks, and it costs about 49 ms to verify a 1,000-signer certificate (Scalable Accountable Byzantine Agreement and Beyond). The central ambiguity in network-agnostic design is between delayed honest parties and silent malicious ones, and silence leaves no conflicting signatures. ABC++ cannot assign blame between delay and silence. Our responsibility split can, and we evaluate it on runs with planted silent adversaries.
Why not just solve the schedule search with an integer program and skip causality? This is partly right, since our solver is an integer program. What causality adds is the per-record responsibility decomposition and the lineage-based restriction of candidates. The ablation above decides whether either matters at scale.
Proposed Experiments
We implement the three protocols in a Datalog engine, and in Rust as an overhead reference, and run them at $n \in \{7, 16, 32, 64\}$. Deployments span AWS regions and use Mahimahi trace-driven emulation as in DispersedLedger. Latency traces include stable periods, bandwidth dips, and injected partitions. Corruption configurations sit at, below, and one past the bounds. We record the usual performance metrics, and per run we record the minimal contingency size $|\Gamma|$, the delay-versus-corruption responsibility split, and solver time.
There are three decisive checks.
The first is soundness and minimality. Every reported contingency must flip the outcome on replay, with zero tolerance. It must also match exhaustive search at $n \le 10$.
The second is a bound-tightness test. We plot measured $|\Gamma|$ against the theoretical slack. Tight theory predicts margins near the slack. Systematically larger margins on realistic traces would show the worst case is loose in practice. Margins below the slack would indicate an implementation or timeout-calibration flaw, which we would investigate before concluding anything.
The third is attribution accuracy. On runs with planted silent adversaries mixed with genuinely slow links, the responsibility split should rank the planted parties above the slow honest ones, scored by precision at $k = t$.
We also test a secondary hypothesis on the geometric cost flagged in Gap 4: that in $D = 3$, safe-area computation, not network delay, dominates latency, and so pushes runs outside Falcon's 0.3–0.7 s window.
References
- From Causes for Database Queries to Repairs and Model-Based Diagnosis and Back
- Optimal Synchronous Approximate Agreement with Asynchronous Fallback
- Multidimensional Approximate Agreement with Asynchronous Fallback
- Validity in Network-Agnostic Byzantine Agreement
- Meeting in a Convex World: Convex Consensus with Asynchronous Fallback
- Causality in Databases
- Causes for query answers from databases: Datalog abduction, view-updates, and integrity constraints
- Declarative networking
- Falcon: Advancing Asynchronous BFT Consensus for Lower Latency and Enhanced Throughput
- DispersedLedger: High-Throughput Byzantine Consensus on Variable Bandwidth Networks
- Scalable Accountable Byzantine Agreement and Beyond