Document Open Access Logo

Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems

Authors Hammurabi Mendes, Maurice Herlihy

PDF
Thumbnail PDF

File

LIPIcs.DISC.2017.35.pdf
  • Filesize: 0.49 MB
  • 16 pages

Document Identifiers

Author Details

Hammurabi Mendes
Maurice Herlihy

Cite As Get BibTex

Hammurabi Mendes and Maurice Herlihy. Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.DISC.2017.35

Abstract

In this paper, we show that the protocol complex of a Byzantine synchronous system can remain (k-1)-connected for up to ceil(t/k) rounds, where t is the maximum number of Byzantine processes, and t >= k >= 1. This topological property implies that ceil(t/k) + 1 rounds are necessary to solve k-set agreement in Byzantine synchronous systems, compared to floor(t/k) + 1 rounds in synchronous crash-failure systems. We also show that our connectivity bound is tight as we indicate solutions to Byzantine k-set agreement in exactly ceil(t/k) + 1 synchronous rounds, at least when n is suitably large compared to t. In conclusion, we see how Byzantine failures can potentially require one extra round to solve k-set agreement, and, for n suitably large compared to t, at most that.

Subject Classification

Keywords
  • Byzantine
  • synchronous
  • k-set agreement
  • topology
  • connectivity

Metrics

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

References

  1. Hagit Attiya and Jennifer Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. John Wiley Interscience, 2nd edition, March 2004. Google Scholar
  2. Rida A. Bazzi and Gil Neiger. Simplifying fault-tolerance: Providing the abstraction of crash failures. Journal of the ACM, 48(3):499-554, May 2001. URL: http://dx.doi.org/10.1145/382780.382784.
  3. A. Björner. Topological methods. In R. L. Graham, M. Grötschel, and L. Lovász, editors, Handbook of Combinatorics, volume 2, pages 1819-1872. MIT Press, Cambridge, MA, USA, December 1995. URL: http://dl.acm.org/citation.cfm?id=233228.233246.
  4. G. Bracha. Asynchronous Byzantine agreement protocols. Information and Computation, 75(2):130-143, November 1987. Google Scholar
  5. Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. Introduction to Reliable and Secure Distributed Programming. Springer, 2 edition, February 2011. Google Scholar
  6. Armando Castañeda, Yannai A. Gonczarowski, and Yoram Moses. Brief announcement: Pareto optimal solutions to consensus and set consensus. In Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, PODC'13, pages 113-115, New York, NY, USA, 2013. ACM. URL: http://dx.doi.org/10.1145/2484239.2484280.
  7. Soma Chaudhuri. More choices allow more faults: set consensus problems in totally asynchronous systems. Information and Computation, 105(1):132-158, July 1993. Google Scholar
  8. Soma Chaudhuri, Maurice Herlihy, Nancy A. Lynch, and Mark R. Tuttle. Tight bounds for k-set agreement. Journal of the ACM, 47(5):912-943, September 2000. URL: http://dx.doi.org/10.1145/355483.355489.
  9. Roberto de Prisco, Dahlia Malkhi, and Michael Reiter. On k-set consensus problems in asynchronous systems. IEEE Transactions on Parallel and Distributed Systems, 12(1):7-21, January 2001. URL: http://dx.doi.org/10.1109/71.899936.
  10. Eli Gafni, Petr Kuznetsov, and Ciprian Manolescu. A generalized asynchronous computability theorem. In Proceedings of the 2014 ACM Symposium on Principles of Distributed Computing, PODC'14, pages 222-231, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2611462.2611477.
  11. Maurice Herlihy, Dmitry Kozlov, and Sergio Rajsbaum. Distributed Computing Through Combinatorial Topology. Morgan Kaufmann, December 2013. Google Scholar
  12. Maurice Herlihy and Sergio Rajsbaum. Concurrent computing and shellable complexes. In Nancy Lynch and Alexander Shvartsman, editors, Distributed Computing, volume 6343 of Lecture Notes in Computer Science, pages 109-123. Springer Berlin / Heidelberg, 2010. URL: http://dx.doi.org/10.1007/978-3-642-15763-9_10.
  13. Maurice Herlihy, Sergio Rajsbaum, and Mark Tuttle. An axiomatic approach to computing the connectivity of synchronous and asynchronous systems. Electronic Notes in Theoretical Computer Science, 230(0):79-102, March 2009. URL: http://dx.doi.org/10.1016/j.entcs.2009.02.018.
  14. Maurice Herlihy, Sergio Rajsbaum, and Mark R. Tuttle. Unifying synchronous and asynchronous message-passing models. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC'98, pages 133-142, New York, NY, USA, 1998. ACM. URL: http://dx.doi.org/10.1145/277697.277722.
  15. Maurice Herlihy and Nir Shavit. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC'93, pages 111-120, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167125.
  16. Maurice Herlihy and Nir Shavit. The topological structure of asynchronous computability. Journal of the ACM, 46(6):858-923, November 1999. Google Scholar
  17. Dimitry N. Kozlov. Combinatorial Algebraic Topology, volume 21 of Algorithms and Computation in Mathematics. Springer, 1st edition, October 2007. URL: http://dx.doi.org/10.1007/978-3-540-71962-5.
  18. Leslie Lamport, Robert Shostak, and Marshall Pease. The Byzantine generals problem. ACM Transaction on Programming Languages and Systems, 4(3):382-401, July 1982. URL: http://dx.doi.org/10.1145/357172.357176.
  19. Hammurabi Mendes, Christine Tasson, and Maurice Herlihy. Distributed computability in Byzantine asynchronous systems. In Proceedings of the 46th Annual ACM Symposium on Theory of Computing, STOC'14, pages 704-713, New York, NY, USA, 2014. ACM. URL: http://dx.doi.org/10.1145/2591796.2591853.
  20. James Munkres. Elements of Algebraic Topology. Prentice Hall, 2nd edition, January 1984. URL: http://www.worldcat.org/isbn/0131816292.
  21. James Munkres. Topology. Pearson, 2nd edition, January 2000. Google Scholar
  22. Gil Neiger. Distributed consensus revisited. Information Processing Letters, 49(4):195-201, February 1994. URL: http://dx.doi.org/10.1016/0020-0190(94)90011-6.
  23. Gil Neiger and Sam Toueg. Automatically increasing the fault-tolerance of distributed algorithms. Journal of Algorithms, 11(3):374-419, 1990. URL: http://dx.doi.org/10.1016/0196-6774(90)90019-B.
  24. Michael Saks and Fotios Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the Twenty-fifth Annual ACM Symposium on Theory of Computing, STOC'93, pages 101-110, New York, NY, USA, 1993. ACM. URL: http://dx.doi.org/10.1145/167088.167122.
  25. T. Srikanth and S. Toueg. Simulating authenticated broadcasts to derive simple fault-tolerant algorithms. Distributed Computing, 2(2):80-94, June 1987. 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