Cited By
View all- Censor-Hillel KCohen SGelles RSela G(2023)Distributed computations in fully-defective networksDistributed Computing10.1007/s00446-023-00452-236:4(501-528)Online publication date: 19-Jun-2023
Distributed Computations in Fully-Defective Networks
Pages 141 - 150
Abstract
We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting is too harsh for any reliable communication, we show how to simulate any algorithm for a noiseless setting over any fully-defective setting, given that the network is 2-edge connected. We prove that if the network is not 2-edge connected, no non-trivial computation in the fully-defective setting is possible.
The key structural property of 2-edge-connected graphs that we leverage is the existence of an oriented (non-simple) cycle that goes through all nodes [Robbins, 1939]. The core of our technical contribution is presenting a construction of such a Robbins cycle in fully-defective networks, and showing how to communicate over it despite total message corruption. These are obtained in a content-oblivious manner, since nodes must ignore the content of received messages.
Supplementary Material
video presentation
- Download
- 753.68 MB
References
[1]
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and Jared Saia. 2018. Sending a Message with Unknown Noise. In ICDCN. Article 8, 10 pages.
[2]
Abhinav Aggarwal, Varsha Dani, Thomas P. Hayes, and Jared Saia. 2020. A Scalable Algorithm for Multiparty Interactive Communication with Private Channels. In ICDCN. Article 8, 15 pages.
[3]
Noga Alon, Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. 2019. Reliable communication over highly connected noisy networks. Distributed Computing, Vol. 32, 6 (2019), 505--515.
[4]
Michael Barborak, Anton Dahbura, and Miroslaw Malek. 1993. The consensus problem in fault-tolerant computing. ACM Computing Surveys (CSur), Vol. 25, 2 (1993), 171--220.
[5]
Martin Biely. 2003. An optimal Byzantine agreement algorithm with arbitrary node and link failures. In Fifteenth IASTED International Conference on Parallel and Distributed Computing and Systems, Vol. 1. 146--151.
[6]
Mark Braverman, Klim Efremenko, Ran Gelles, and Bernhard Haeupler. 2017. Constant-Rate Coding for Multiparty Interactive Communication Is Impossible. J. ACM, Vol. 65, 1, Article 4 (2017), 41 pages.
[7]
Keren Censor-Hillel, Shir Cohen, Ran Gelles, and Gal Sela. 2022. Distributed Computations in Fully-Defective Networks. arxiv: 2205.11148
[8]
Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. 2019. Making asynchronous distributed computations robust to noise. Distributed Computing, Vol. 32, 5 (2019), 405--421.
[9]
Varsha Dani, Mahnush Movahedi, Jared Saia, and Maxwell Young. 2015. Interactive Communication with Unknown Noise Rate. In ICALP. 575--587.
[10]
Pallab Dasgupta. 1998. Agreement under faulty interfaces. Inform. Process. Lett., Vol. 65, 3 (1998), 125--129.
[11]
Danny Dolev. 1982. The Byzantine generals strike again. Journal of Algorithms, Vol. 3, 1 (1982), 14--30.
[12]
Elena Dubrova. 2013. Fault-Tolerant Design. Springer.
[13]
Klim Efremenko, Elad Haramaty, and Yael Tauman Kalai. 2020. Interactive Coding with Constant Round and Communication Blowup. In ITCS. 7:1--7:34.
[14]
Michael J. Fischer, Nancy A. Lynch, and Michael S. Paterson. 1985. Impossibility of Distributed Consensus with One Faulty Process. J. ACM, Vol. 32, 2 (1985), 374--382.
[15]
Ran Gelles. 2017. Coding for Interactive Communication: A Survey. Foundations and Trends® in Theoretical Computer Science, Vol. 13, 1--2 (2017), 1--157.
[16]
Ran Gelles and Siddharth Iyer. 2020. Interactive Coding Resilient to an Unknown Number of Erasures. In OPODIS. 13:1--13:16.
[17]
Ran Gelles and Yael T. Kalai. 2019. Constant-Rate Interactive Coding Is Impossible, Even in Constant-Degree Networks. IEEE Transactions on Information Theory, Vol. 65, 6 (2019), 3812--3829.
[18]
Ran Gelles, Yael Tauman Kalai, and Govind Ramnarayan. 2019. Efficient Multiparty Interactive Coding for Insertions, Deletions, and Substitutions. In PODC. 137--146.
[19]
Ran Gelles, Ankur Moitra, and Amit Sahai. 2014. Efficient Coding for Interactive Communication. IEEE Transactions on Information Theory, Vol. 60, 3 (2014), 1899--1913.
[20]
Li Gong, Patrick Lincoln, and John Rushby. 1995. Byzantine agreement with authentication: Observations and applications in tolerating hybrid and link faults. In Dependable Computing and Fault Tolerant Systems, Vol. 10. IEEE Computer Society, 139--158.
[21]
J.N. Gray. 1978. Notes on data base operating systems. In Operating Systems. Lecture Notes in Computer Science, Vol. 60. Springer, Berlin, Heidelberg.
[22]
Yael Hitron and Merav Parter. 2021 a. Broadcast CONGEST Algorithms against Adversarial Edges. In DISC. 23:1--23:19.
[23]
Yael Hitron and Merav Parter. 2021 b. General CONGEST Compilers against Adversarial Edges. In DISC. 24:1--24:18.
[24]
William M. Hoza and Leonard J. Schulman. 2016. The Adversarial Noise Threshold for Distributed Protocols. In SODA. 240--258.
[25]
Abhishek Jain, Yael Tauman Kalai, and Allison Lewko. 2015. Interactive Coding for Multiparty Protocols. In ITCS. 1--10.
[26]
Israel Koren and C. Mani Krishna (Eds.). 2020. Fault-Tolerant Systems second edition ed.). Morgan Kaufmann, San Francisco (CA).
[27]
Allison Lewko and Ellen Vitercik. 2015. Balancing Communication for Multi-party Interactive Coding. arxiv: 1503.06381
[28]
Merav Parter and Eylon Yogev. 2019 a. Low Congestion Cycle Covers and Their Applications. In SODA. 1673--1692.
[29]
Merav Parter and Eylon Yogev. 2019 b. Optimal Short Cycle Decomposition in Almost Linear Time. In ICALP. 89:1--89:14.
[30]
Andrzej Pelc. 1992. Reliable communication in networks with Byzantine link failures. Networks, Vol. 22, 5 (1992), 441--459.
[31]
Kenneth J. Perry and Sam Toueg. 1986. Distributed agreement in the presence of processor and communication faults. IEEE Transactions on Software Engineering, Vol. SE-12, 3 (1986), 477--482.
[32]
Sridhar Rajagopalan and Leonard Schulman. 1994. A coding theorem for distributed computation. In STOC. 790--799.
[33]
Michel Raynal. 2018. Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach. Springer, Cham. 459 pages.
[34]
Herbert Ellis Robbins. 1939. A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly (1939).
[35]
Nicola Santoro and Peter Widmayer. 1990. Distributed function evaluation in the presence of transmission faults. In International Symposium on Algorithms. Springer, 358--367.
[36]
Hasan M. Sayeed, Marwan Abu-Amara, and Hosame Abu-Amara. 1995. Optimal Asynchronous Agreement and Leader Election Algorithm for Complete Networks with Byzantine Faulty Links. Distributed Computing, Vol. 9, 3 (1995), 147--156.
[37]
Ulrich Schmid, Bettina Weiss, and Idit Keidar. 2009. Impossibility Results and Lower Bounds for Consensus under Link Failures. SIAM J. Comput., Vol. 38, 5 (2009), 1912--1951.
[38]
Leonard J. Schulman. 1992. Communication on noisy channels: a coding theorem for computation. In FOCS. 724--733.
[39]
Leonard J. Schulman. 1993. Deterministic coding for interactive communication. In STOC (San Diego, California, United States). 747--756.
[40]
Hin-Sing Siu, Yeh-Hao Chin, and Wei-Pang sm. 1998. Byzantine agreement in the presence of mixed faults on processors and links. IEEE Transactions on Parallel and Distributed Systems, Vol. 9, 4 (1998), 335--345.
[41]
Hassler Whitney. 1932. Non-Separable and Planar Graphs. Trans. Amer. Math. Soc., Vol. 34, 2 (1932), 339--362.
Index Terms
- Distributed Computations in Fully-Defective Networks
Recommendations
Distributed computations in fully-defective networks
AbstractWe address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting ...
Some Defective Parameters in Graphs
Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with a maximum degree of at most k. Many parameters in graph theory are defined in terms of independent sets. Accordingly, their definitions can be expanded ...
Equitable defective coloring of sparse planar graphs
A graph has an equitable, defective k-coloring (an ED-k-coloring) if there is a k-coloring of V(G) that is defective (every vertex shares the same color with at most one neighbor) and equitable (the sizes of all color classes differ by at most one). A ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2022
509 pages
Copyright © 2022 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 21 July 2022
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- United States-Israel Binational Science Foundation (BSF)
- Israel Science Foundation (ISF)
- European Union?s Horizon 2020
Conference
Acceptance Rates
Overall Acceptance Rate 740 of 2,477 submissions, 30%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 113Total Downloads
- Downloads (Last 12 months)28
- Downloads (Last 6 weeks)2
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
Cited By
View all- Censor-Hillel KCohen SGelles RSela G(2023)Distributed computations in fully-defective networksDistributed Computing10.1007/s00446-023-00452-236:4(501-528)Online publication date: 19-Jun-2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in