A coding theorem for distributed computation

DOI10.1145/195058.195462zbMath1344.68035OpenAlexW2077242989MaRDI QIDQ2817675

Leonard J. Schulman, Sridhar Rajagopalan

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/195058.195462

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Distributed systems (68M14) Network protocols (68M12) Coding theorems (Shannon theory) (94A24)

Related Items

An improvement of the tree code construction ⋮ The Cost of Fault Tolerance in Multi-Party Communication Complexity ⋮ Interactive non-malleable codes ⋮ Distributed computations in fully-defective networks ⋮ Unnamed Item ⋮ Distributed CONGEST Algorithms against Mobile Adversaries ⋮ Making Asynchronous Distributed Computations Robust to Channel Noise ⋮ Authenticated adversarial routing ⋮ Making asynchronous distributed computations robust to noise ⋮ Reliable communication over highly connected noisy networks ⋮ Computing in fault tolerant broadcast networks and noisy decision trees ⋮ Unnamed Item ⋮ Capacity of Interactive Communication over Erasure Channels and Channels with Feedback ⋮ Palette-alternating tree codes ⋮ Unnamed Item ⋮ Noisy beeping networks