DROPS

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.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}
}

Search Results

Documents authored by Mendes, Hammurabi

Tight Bounds for Connectivity and Set Agreement in Byzantine Synchronous Systems

Abstract

Cite as

Thanks for your feedback!

Could not send message