Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2016 | Published + Submitted
Book Section - Chapter Open

The adversarial noise threshold for distributed protocols


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 (1.3 MB)
Name Size Download all
378.5 kB Preview Download
904.8 kB Preview Download

Additional details

August 20, 2023
October 18, 2023