Обнаружены жесткие пороги увольнения для византийско-толерантной распределенной проверки

You now know the exact redundancy budget for distributed verification under crash and Byzantine failures: under crash failures, at least t+1 copies of each element; under Byzantine failures, at least 2t + c copies, where t is the number of faulty processes and c is the minimum correct outputs required.

That result comes from a new paper introducing c-Lattice Aggregation, a fault-tolerant reconstruction problem that formalizes what it takes for n asynchronous processes to collaboratively reconstruct a concurrent execution from partial, overlapping local samples. The authors tighten classical Lattice Agreement (Attiya, Herlihy, Rachman 1995) and Byzantine Lattice Agreement (Di Luna et al. 2020; Zheng and Garg 2020) by adding a redundancy parameter x and proving that these thresholds are tight.

Crash vs. Byzantine: Two Distinct Regimes

Under crash failures with at most t faulty processes, Lattice Aggregation is solvable if and only if x >= t + 1. Every element of the execution must appear in at least t+1 initial samples. Under Byzantine failures, the bar rises: x must be at least 2t + c. The paper proves both necessity (via indistinguishability-based lower bounds) and sufficiency (via matching algorithms built on SCD-broadcast).

This is not ivory-tower theory. The authors define globally dependent languages - those for which no partial view can certify correctness. Consensus, linearizability, k-set agreement, and leader election all fall into this category. For these, sound monitoring is impossible unless c-Lattice Aggregation is solved. The paper gives the first complete characterization of fault-tolerant verification under Byzantine failures.

What This Enables Next

If you are building a Byzantine-fault-tolerant monitoring or auditing system for any globally dependent property, you can now compute exactly how much sample overlap you need to guarantee correct output. The matching algorithms show the redundancy bounds are tight, so you can stop overspending on samples or undershooting on fault tolerance. Expect these thresholds to become the standard design rule for distributed verification protocols.

Source: Lattice Aggregation in Distributed Verification under Crash and Byzantine Failures
Domain: arxiv.org