The adversarial noise threshold for distributed protocols
- Creators
- Hoza, William M.
- Schulman, Leonard J.
Abstract
We consider the problem of implementing distributed protocols, despite adversarial channel errors, on synchronous-messaging networks with arbitrary topology. In our first result we show that any n-party T-round protocol on an undirected communication network G can be compiled into a robust simulation protocol on a sparse (O(n) edges) subnetwork so that the simulation tolerates an adversarial error rate of Ω(1n); the simulation has a round complexity of O(m log n/nT), where m is the number of edges in G. (So the simulation is work-preserving up to a log factor.) The adversary's error rate is within a constant factor of optimal. Given the error rate, the round complexity blowup is within a factor of O(k log n) of optimal, where k is the edge connectivity of G. We also determine that the maximum tolerable error rate on directed communication networks is Θ(1/s) where s is the number of edges in a minimum equivalent digraph. Next we investigate adversarial per-edge error rates, where the adversary is given an error budget on each edge of the network. We determine the exact limit for tolerable per-edge error rates on an arbitrary directed graph. However, the construction that approaches this limit has exponential round complexity, so we give another compiler, which transforms T-round protocols into O(mT)-round simulations, and prove that for polynomial-query black box compilers, the per-edge error rate tolerated by this last compiler is within a constant factor of optimal.
Additional Information
© 2016 SIAM. Supported by a Nellie Bergen and Adrian Foster Tillotson Summer Undergraduate Research Fellowship from the California Institute of Technology, as well as by the ARCS Los Angeles Founder Chapter. Supported in part by NSF Award 1319745. We thank anonymous reviewers for numerous suggestions, including the observation that Theorems 6 and 7 extend to large alphabets.Attached Files
Published - p240-hoza.pdf
Submitted - 1412.8097v2.pdf
Files
Name | Size | Download all |
---|---|---|
md5:19a059330590eb916419737944f68f03
|
378.5 kB | Preview Download |
md5:bee1dc5358f4b3fe01e5fbb79ed6c416
|
904.8 kB | Preview Download |
Additional details
- Eprint ID
- 65380
- Resolver ID
- CaltechAUTHORS:20160316-071949447
- Caltech Summer Undergraduate Research Fellowship (SURF)
- ARCS Los Angeles Founder Chapter
- 1319745
- NSF
- Created
-
2016-03-16Created from EPrint's datestamp field
- Updated
-
2023-06-02Created from EPrint's last_modified field