1 Search Results for "Mendes, Hammurabi"

Document
DOI: 10.4230/LIPIcs.DISC.2017.35
Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems

Authors: Hammurabi Mendes and Maurice Herlihy

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{mendes_et_al:LIPIcs.DISC.2017.35,
  author =	{Mendes, Hammurabi and Herlihy, Maurice},
  title =	{{Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.35},
  URN =		{urn:nbn:de:0030-drops-79930},
  doi =		{10.4230/LIPIcs.DISC.2017.35},
  annote =	{Keywords: Byzantine, synchronous, k-set agreement, topology, connectivity}
}
  • Refine by Author
  • 1 Herlihy, Maurice
  • 1 Mendes, Hammurabi

  • Refine by Classification

  • Refine by Keyword
  • 1 Byzantine
  • 1 connectivity
  • 1 k-set agreement
  • 1 synchronous
  • 1 topology

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

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