Document Open Access Logo

General CONGEST Compilers against Adversarial Edges

Authors Yael Hitron, Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.24.pdf
  • Filesize: 0.7 MB
  • 18 pages

Document Identifiers

Author Details

Yael Hitron
  • Weizmann Institute of Science, Rehovot, Israel
Merav Parter
  • Weizmann Institute of Science, Rehovot, Israel

Funding

  • Parter, Merav: This project is funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No. 949083).

Acknowledgements

We are very grateful to Dan Mikulincer, David Peleg and Eylon Yogev for many useful discussions. More specifically, we thank Eylon Yogev for suggesting the high-level framework for the 1-FT cycle cover. We also thank the unanimous referee for the useful comments on the proof of Lemma 21.

Cite AsGet BibTex

Yael Hitron and Merav Parter. General CONGEST Compilers against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.DISC.2021.24

Abstract

We consider the adversarial CONGEST model of distributed computing in which a fixed number of edges (or nodes) in the graph are controlled by a computationally unbounded adversary that corrupts the computation by sending malicious messages over these (a-priori unknown) controlled edges. As in the standard CONGEST model, communication is synchronous, where per round each processor can send O(log n) bits to each of its neighbors. This paper is concerned with distributed algorithms that are both time efficient (in terms of the number of rounds), as well as, robust against a fixed number of adversarial edges. Unfortunately, the existing algorithms in this setting usually assume that the communication graph is complete (n-clique), and very little is known for graphs with arbitrary topologies. We fill in this gap by extending the methodology of [Parter and Yogev, SODA 2019] and provide a compiler that simulates any CONGEST algorithm 𝒜 (in the reliable setting) into an equivalent algorithm 𝒜' in the adversarial CONGEST model. Specifically, we show the following for every (2f+1) edge-connected graph of diameter D: - For f = 1, there is a general compiler against a single adversarial edge with a compilation overhead of Ô(D³) rounds. This improves upon the Ô(D⁵) round overhead of [Parter and Yogev, SODA 2019] and omits their assumption regarding a fault-free preprocessing phase. - For any constant f, there is a general compiler against f adversarial edges with a compilation overhead of Ô(D^{O(f)}) rounds. The prior compilers of [Parter and Yogev, SODA 2019] were limited to a single adversarial edge. Our compilers are based on a new notion of fault-tolerant cycle covers. The computation of these cycles in the adversarial CONGEST model constitutes the key technical contribution of the paper.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
Keywords
  • CONGEST
  • Cycle Covers
  • Byzantine Adversaries

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  2. Baruch Awerbuch, Bonnie Berger, Lenore Cowen, and David Peleg. Fast distributed network decompositions and covers. J. Parallel Distributed Comput., 39(2):105-114, 1996. Google Scholar
  3. Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. A trade-off between information and communication in broadcast protocols. J. ACM, 37(2):238-256, 1990. Google Scholar
  4. Piotr Berman, Krzysztof Diks, and Andrzej Pelc. Reliable broadcasting in logarithmic time with byzantine link failures. Journal of Algorithms, 22(2):199-211, 1997. Google Scholar
  5. Piotr Berman and Juan A. Garay. Cloture votes: n/4-resilient distributed consensus in t+1 rounds. Math. Syst. Theory, 26(1):3-19, 1993. Google Scholar
  6. Piotr Berman, Juan A. Garay, and Kenneth J. Perry. Towards optimal distributed consensus (extended abstract). In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989, pages 410-415. IEEE Computer Society, 1989. Google Scholar
  7. Greg Bodwin, Michael Dinitz, and Caleb Robelle. Optimal vertex fault-tolerant spanners in polynomial time. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 2924-2938, 2021. Google Scholar
  8. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. J. ACM, 32(4):824-840, 1985. Google Scholar
  9. Diptarka Chakraborty and Keerti Choudhary. New extremal bounds for reachability and strong-connectivity preservers under failures. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), pages 25:1-25:20, 2020. Google Scholar
  10. Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, and Alex Samorodnitsky. On the round complexity of randomized byzantine agreement. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14-18, 2019, Budapest, Hungary, pages 12:1-12:17, 2019. Google Scholar
  11. Michael Dinitz and Robert Krauthgamer. Fault-tolerant spanners: better and simpler. In Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on Principles of distributed computing, pages 169-178. ACM, 2011. Google Scholar
  12. Danny Dolev. The byzantine generals strike again. J. Algorithms, 3(1):14-30, 1982. Google Scholar
  13. Danny Dolev, Michael J. Fischer, Robert J. Fowler, Nancy A. Lynch, and H. Raymond Strong. An efficient algorithm for byzantine agreement without authentication. Information and Control, 52(3):257-274, 1982. Google Scholar
  14. Danny Dolev and Ezra N. Hoch. Constant-space localized byzantine consensus. In Distributed Computing, 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings, pages 167-181, 2008. Google Scholar
  15. Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput., 26(4):873-933, 1997. Google Scholar
  16. Michael J Fischer. The consensus problem in unreliable distributed systems (a brief survey). In International Conference on Fundamentals of Computation Theory, pages 127-140. Springer, 1983. Google Scholar
  17. Mattias Fitzi and Ueli Maurer. From partial consistency to global broadcast. In Proceedings of the thirty-second annual ACM symposium on Theory of computing, pages 494-503, 2000. Google Scholar
  18. Juan A. Garay and Yoram Moses. Fully polynomial byzantine agreement for n > 3t processors in t + 1 rounds. SIAM J. Comput., 27(1):247-290, 1998. Google Scholar
  19. Mohsen Ghaffari. Near-optimal scheduling of distributed algorithms. In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing, PODC 2015, Donostia-San Sebastián, Spain, July 21-23, 2015, pages 3-12, 2015. Google Scholar
  20. Fabrizio Grandoni and Virginia Vassilevska Williams. Faster replacement paths and distance sensitivity oracles. ACM Transactions on Algorithms (TALG), 16(1):1-25, 2019. Google Scholar
  21. Yael Hitron and Merav Parter. Broadcast CONGEST algorithms against adversarial edges. In Distributed Computing - 29th International Symposium, DISC 2021, 2021. Google Scholar
  22. Yael Hitron and Merav Parter. Broadcast CONGEST algorithms against adversarial edges. CoRR, abs/2004.06436, 2021. URL: http://arxiv.org/abs/2004.06436.
  23. Damien Imbs and Michel Raynal. Simple and efficient reliable broadcast in the presence of byzantine processes. arXiv preprint, 2015. URL: http://arxiv.org/abs/1510.06882.
  24. Karthik C. S. and Merav Parter. Deterministic replacement path covering. In Dániel Marx, editor, Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10-13, 2021, pages 704-723. SIAM, 2021. Google Scholar
  25. Jonathan Katz and Chiu-Yuen Koo. On expected constant-round protocols for byzantine agreement. In Annual International Cryptology Conference, pages 445-462. Springer, 2006. Google Scholar
  26. Muhammad Samir Khan, Syed Shalan Naqvi, and Nitin H. Vaidya. Exact byzantine consensus on undirected graphs under local broadcast model. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 327-336, 2019. Google Scholar
  27. Chiu-Yuen Koo. Broadcast in radio networks tolerating byzantine adversarial behavior. In Proceedings of the Twenty-Third Annual ACM Symposium on Principles of Distributed Computing, PODC 2004, St. John’s, Newfoundland, Canada, July 25-28, 2004, pages 275-282, 2004. Google Scholar
  28. Frank Thomson Leighton, Bruce M Maggs, and Satish B Rao. Packet routing and job-shop scheduling ino (congestion+ dilation) steps. Combinatorica, 14(2):167-186, 1994. Google Scholar
  29. Alexandre Maurer and Sébastien Tixeuil. On byzantine broadcast in loosely connected networks. In Distributed Computing - 26th International Symposium, DISC 2012, Salvador, Brazil, October 16-18, 2012. Proceedings, pages 253-266, 2012. Google Scholar
  30. Merav Parter. Small cuts and connectivity certificates: A fault tolerant approach. In 33rd International Symposium on Distributed Computing (DISC 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2019. Google Scholar
  31. Merav Parter and Eylon Yogev. Congested clique algorithms for graph spanners. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  32. Merav Parter and Eylon Yogev. Distributed algorithms made secure: A graph theoretic approach. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1693-1710, 2019. Google Scholar
  33. Merav Parter and Eylon Yogev. Low congestion cycle covers and their applications. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1673-1692, 2019. Google Scholar
  34. Merav Parter and Eylon Yogev. Optimal short cycle decomposition in almost linear time. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, pages 89:1-89:14, 2019. Google Scholar
  35. Merav Parter and Eylon Yogev. Optimal short cycle decomposition in almost linear time. http://www.weizmann.ac.il/math/parter/sites/math.parter/files/uploads/main-icalp-cycles-full.pdf, 2019.
  36. Merav Parter and Eylon Yogev. Secure distributed computing made (nearly) optimal. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 107-116, 2019. Google Scholar
  37. Marshall Pease, Robert Shostak, and Leslie Lamport. Reaching agreement in the presence of faults. Journal of the ACM (JACM), 27(2):228-234, 1980. Google Scholar
  38. Andrzej Pelc and David Peleg. Broadcasting with locally bounded byzantine faults. Inf. Process. Lett., 93(3):109-115, 2005. Google Scholar
  39. David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, 2000. Google Scholar
  40. Václav Rozhon and Mohsen Ghaffari. Polylogarithmic-time deterministic network decomposition and distributed derandomization. In Konstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, and Julia Chuzhoy, editors, Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020, pages 350-363. ACM, 2020. Google Scholar
  41. Nicola Santoro and Peter Widmayer. Time is not a healer. In Annual Symposium on Theoretical Aspects of Computer Science, pages 304-313. Springer, 1989. Google Scholar
  42. Nicola Santoro and Peter Widmayer. Distributed function evaluation in the presence of transmission faults. In Algorithms, International Symposium SIGAL '90, Tokyo, Japan, August 16-18, 1990, Proceedings, pages 358-367, 1990. Google Scholar
  43. Sam Toueg, Kenneth J Perry, and TK Srikanth. Fast distributed agreement. SIAM Journal on Computing, 16(3):445-457, 1987. Google Scholar
  44. Oren Weimann and Raphael Yuster. Replacement paths and distance sensitivity oracles via fast matrix multiplication. ACM Transactions on Algorithms (TALG), 9(2):1-13, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact