The adversarial noise threshold for distributed protocols

DOI10.1137/1.9781611974331.CH18zbMATH Open1410.68050arXiv1412.8097OpenAlexW1894162430MaRDI QIDQ4575595FDOQ4575595

Authors: William M. Hoza, Leonard J. Schulman 

Publication date: 16 July 2018

Published in: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

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 ($mathcalO(n)$ edges) subnetwork so that the simulation tolerates an adversarial error rate of $Omegaleft(frac1night)$; the simulation has a round complexity of $mathcalOleft(fracmlognnTight)$, 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 $mathcalO(klogn)$ of optimal, where $k$ is the edge connectivity of $G$. We also determine that the maximum tolerable error rate on directed communication networks is $Theta(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 $mathcalO(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.

Full work available at URL: https://arxiv.org/abs/1412.8097

Recommendations

• Fast interactive coding against adversarial noise
• Making Asynchronous Distributed Computations Robust to Channel Noise
• Making asynchronous distributed computations robust to noise
• A coding theorem for distributed computation
• Reliable communication over highly connected noisy networks

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Distributed systems (68M14) Network protocols (68M12)

Cited In (10)

• The Bussard-Bagga and Other Distance-Bounding Protocols under Attacks
• Noisy beeping networks
• Making asynchronous distributed computations robust to noise
• Reliable communication over highly connected noisy networks
• On tradeoff between network connectivity, phase complexity and communication complexity of reliable communication tolerating mixed adversary
• Optimizing Threshold Protocols in Adversarial Structures
• Distributed CONGEST Algorithms against Mobile Adversaries
• Title not available (Why is that?)
• Making Asynchronous Distributed Computations Robust to Channel Noise
• Distributed computations in fully-defective networks

This page was built for publication: The adversarial noise threshold for distributed protocols

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575595)