Name
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 Ω(1/n); the simulation has a round complexity of O([EQUATION]), 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 limit for tolerable per-edge error rates on an arbitrary directed graph to within a factor of 2. 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.
|
Year | DOI | Venue |
|---|---|---|
2016 | 10.5555/2884435.2884453 | SODA '16: Symposium on Discrete Algorithms
Arlington
Virginia
January, 2016 |
Field | DocType | Volume |
Black box (phreaking),Discrete mathematics,Binary logarithm,Exponential function,Computer science,Word error rate,Communication channel,Directed graph,Subnetwork,Digraph | Conference | abs/1412.8097 |
ISBN | Citations | PageRank |
978-1-61197-433-1 | 2 | 0.37 |
References | Authors | |
19 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| William M. Hoza | 1 | 2 | 0.37 |
| Leonard J. Schulman | 2 | 1328 | 136.88 |