Document Open Access Logo

Broadcast CONGEST Algorithms against Adversarial Edges

Authors Yael Hitron, Merav Parter

PDF
Thumbnail PDF

File

LIPIcs.DISC.2021.23.pdf
  • Filesize: 0.7 MB
  • 19 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 program (grant agreement No. 949083).

Acknowledgements

We are very grateful to David Peleg and Eylon Yogev for many useful discussions.

Cite As Get BibTex

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

Abstract

We consider the corner-stone broadcast task with an adaptive adversary that controls a fixed number of t edges in the input communication graph. In this model, the adversary sees the entire communication in the network and the random coins of the nodes, while maliciously manipulating the messages sent through a set of t edges (unknown to the nodes). Since the influential work of [Pease, Shostak and Lamport, JACM'80], broadcast algorithms against plentiful adversarial models have been studied in both theory and practice for over more than four decades. Despite this extensive research, there is no round efficient broadcast algorithm for general graphs in the CONGEST model of distributed computing. Even for a single adversarial edge (i.e., t = 1), the state-of-the-art round complexity is polynomial in the number of nodes.
We provide the first round-efficient broadcast algorithms against adaptive edge adversaries. Our two key results for n-node graphs of diameter D are as follows:  
- For t = 1, there is a deterministic algorithm that solves the problem within Õ(D²) rounds, provided that the graph is 3 edge-connected. This round complexity beats the natural barrier of O(D³) rounds, the existential lower bound on the maximal length of 3 edge-disjoint paths between a given pair of nodes in G. This algorithm can be extended to a Õ((tD)^{O(t)})-round algorithm against t adversarial edges in (2t+1) edge-connected graphs.
- For expander graphs with edge connectivity of Ω(t²log n), there is a considerably improved broadcast algorithm with O(t log ² n) rounds against t adversarial edges. This algorithm exploits the connectivity and conductance properties of G-subgraphs obtained by employing the Karger’s edge sampling technique. 
Our algorithms mark a new connection between the areas of fault-tolerant network design and reliable distributed communication.

Subject Classification

ACM Subject Classification
  • Networks → Network algorithms
Keywords
  • CONGEST
  • Fault-Tolerant Network Design
  • Edge Connectivity

Metrics

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

Related Versions

References

  1. Ittai Abraham, T.-H. Hubert Chan, Danny Dolev, Kartik Nayak, Rafael Pass, Ling Ren, and Elaine Shi. Communication complexity of byzantine agreement, revisited. In Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, PODC 2019, Toronto, ON, Canada, July 29 - August 2, 2019, pages 317-326, 2019. Google Scholar
  2. Ittai Abraham, Srinivas Devadas, Danny Dolev, Kartik Nayak, and Ling Ren. Synchronous byzantine agreement with expected O(1) rounds, expected o(n^2) communication, and optimal resilience. In Financial Cryptography and Data Security - 23rd International Conference, FC 2019, Frigate Bay, St. Kitts and Nevis, February 18-22, 2019, Revised Selected Papers, pages 320-334, 2019. Google Scholar
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding. Journal of the ACM (JACM), 42(4):844-856, 1995. Google Scholar
  4. John Augustine, Gopal Pandurangan, and Peter Robinson. Fast byzantine leader election in dynamic networks. In Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, pages 276-291, 2015. Google Scholar
  5. 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
  6. Anindo Bagchi and S. Louis Hakimi. Information dissemination in distributed systems with faulty units. IEEE Transactions on Computers, 43(6):698-710, 1994. Google Scholar
  7. 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
  8. 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
  9. Douglas M Blough and Andrzej Pelc. Optimal communication in networks with randomly distributed byzantine faults. Networks, 23(8):691-701, 1993. Google Scholar
  10. 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), pages 2924-2938. SIAM, 2021. Google Scholar
  11. Gabriel Bracha. Asynchronous byzantine agreement protocols. Information and Computation, 75(2):130-143, 1987. Google Scholar
  12. Gabriel Bracha and Sam Toueg. Asynchronous consensus and broadcast protocols. J. ACM, 32(4):824-840, 1985. Google Scholar
  13. Keren Censor-Hillel and Tariq Toukan. On fast and robust information spreading in the vertex-congest model. Theoretical Computer Science, 2017. Google Scholar
  14. 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
  15. Bogdan S. Chlebus, Dariusz R. Kowalski, and Jan Olkowski. Fast agreement in networks with byzantine nodes. In 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, pages 30:1-30:18, 2020. Google Scholar
  16. Brian A. Coan and Jennifer L. Welch. Modular construction of a byzantine agreement protocol with optimal message bit complexity. Inf. Comput., 97(1):61-85, 1992. Google Scholar
  17. 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
  18. 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
  19. Danny Dolev. The byzantine generals strike again. J. Algorithms, 3(1):14-30, 1982. Google Scholar
  20. 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
  21. 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
  22. Cynthia Dwork, David Peleg, Nicholas Pippenger, and Eli Upfal. Fault tolerance in networks of bounded degree. SIAM J. Comput., 17(5):975-988, 1988. Google Scholar
  23. Pesech Feldman and Silvio Micali. An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput., 26(4):873-933, 1997. Google Scholar
  24. 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
  25. 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
  26. Chaya Ganesh and Arpita Patra. Broadcast extensions with optimal communication and round complexity. In Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pages 371-380, 2016. Google Scholar
  27. 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
  28. 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
  29. Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, and Salil P. Vadhan. Better pseudorandom generators from milder pseudorandom restrictions. In 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012, pages 120-129, 2012. Google Scholar
  30. 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
  31. Fabrizio Grandoni and Virginia Vassilevska Williams. Faster replacement paths and distance sensitivity oracles. ACM Trans. Algorithms, 16(1):15:1-15:25, 2020. Google Scholar
  32. Yael Hitron and Merav Parter. Broadcast CONGEST algorithms against adversarial edges. CoRR, abs/2004.06436, 2021. Google Scholar
  33. Yael Hitron and Merav Parter. General CONGEST algorithms compilers against adversarial edges. In DISC, 2021. Google Scholar
  34. Damien Imbs and Michel Raynal. Simple and efficient reliable broadcast in the presence of byzantine processes. arXiv preprint arXiv:1510.06882, 2015. Google Scholar
  35. David R Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2):383-413, 1999. Google Scholar
  36. Karthik C. S. and Merav Parter. Deterministic replacement path covering. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, SODA 2021, Virtual Conference, January 10 - 13, 2021, pages 704-723, 2021. Google Scholar
  37. 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
  38. 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
  39. Valerie King, Jared Saia, Vishal Sanwalani, and Erik Vee. Towards secure and scalable computation in peer-to-peer networks. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 87-98, 2006. Google Scholar
  40. Chiu-Yuen Koo. Broadcast in radio networks tolerating byzantine adversarial behavior. In Soma Chaudhuri and Shay Kutten, editors, 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. ACM, 2004. Google Scholar
  41. Leslie Lamport, Robert E. Shostak, and Marshall C. Pease. The byzantine generals problem. ACM Trans. Program. Lang. Syst., 4(3):382-401, 1982. Google Scholar
  42. 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
  43. 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
  44. Kartik Nayak, Ling Ren, Elaine Shi, Nitin H. Vaidya, and Zhuolun Xiang. Improved extension protocols for byzantine broadcast and agreement. In 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference, pages 28:1-28:17, 2020. Google Scholar
  45. Noam Nisan and Avi Wigderson. Hardness vs randomness. J. Comput. Syst. Sci., 49(2):149-167, 1994. Google Scholar
  46. 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
  47. 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
  48. Merav Parter and Eylon Yogev. Distributed algorithms made secure: A graph theoretic approach. In Timothy M. Chan, editor, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 1693-1710. SIAM, 2019. Google Scholar
  49. 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
  50. 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
  51. Andrzej Pelc. Fault-tolerant broadcasting and gossiping in communication networks. Networks: An International Journal, 28(3):143-156, 1996. Google Scholar
  52. Andrzej Pelc and David Peleg. Broadcasting with locally bounded byzantine faults. Inf. Process. Lett., 93(3):109-115, 2005. Google Scholar
  53. Andrzej Pelc and David Peleg. Feasibility and complexity of broadcasting with random transmission failures. Theoretical Computer Science, 370(1-3):279-292, 2007. Google Scholar
  54. David Peleg. Distributed Computing: A Locality-sensitive Approach. SIAM, 2000. Google Scholar
  55. 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
  56. 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
  57. Sam Toueg, Kenneth J Perry, and TK Srikanth. Fast distributed agreement. SIAM Journal on Computing, 16(3):445-457, 1987. Google Scholar
  58. Eli Upfal. Tolerating a linear number of faults in networks of bounded degree. Inf. Comput., 115(2):312-320, 1994. Google Scholar
  59. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  60. 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
  61. Christian Wulff-Nilsen. Fully-dynamic minimum spanning forest with improved worst-case update time. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1130-1143, 2017. 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 About DROPS Imprint Privacy Contact