Search Results

Documents authored by Kastrati, Ard

Document
DOI: 10.4230/LIPIcs.OPODIS.2020.6
Multi-Threshold Asynchronous Reliable Broadcast and Consensus

Authors: Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties f is bounded by a single given threshold t. If f > t, these protocols are completely deemed insecure. We consider the relaxed notion of multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as f ≤ t_v, f ≤ t_c and f ≤ t_t respectively. For consensus, we consider both variants of (1-ε)-consensus and almost-surely terminating consensus, where termination is guaranteed with probability (1-ε) and 1, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures: - Multi-threshold reliable broadcast is possible if and only if max{t_c,t_v} + 2t_t < n. - Multi-threshold almost-surely consensus is possible if max{t_c, t_v} + 2t_t < n, 2t_v + t_t < n and t_t < n/3. Assuming a global coin, it is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n. - Multi-threshold (1-ε)-consensus is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n.
Cite as

Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang. Multi-Threshold Asynchronous Reliable Broadcast and Consensus. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 6:1-6:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{hirt_et_al:LIPIcs.OPODIS.2020.6,
  author =	{Hirt, Martin and Kastrati, Ard and Liu-Zhang, Chen-Da},
  title =	{{Multi-Threshold Asynchronous Reliable Broadcast and Consensus}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{6:1--6:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.6},
  URN =		{urn:nbn:de:0030-drops-134917},
  doi =		{10.4230/LIPIcs.OPODIS.2020.6},
  annote =	{Keywords: broadcast, byzantine agreement, multi-threshold}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2020.48
Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus

Authors: Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties f is bounded by a single given threshold t. If f > t, these protocols are completely deemed insecure. We consider the relaxed notion of multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as f ≤ t_v, f ≤ t_c and f ≤ t_t respectively. For consensus, we consider both variants of (1-ε)-consensus and almost-surely terminating consensus, where termination is guaranteed with probability (1-ε) and 1, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures: - Multi-threshold reliable broadcast is possible if and only if max{t_c,t_v} + 2t_t < n. - Multi-threshold almost-surely consensus is possible if max{t_c, t_v} + 2t_t < n, 2t_v + t_t < n and t_t < n/3. Assuming a global coin, it is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n. - Multi-threshold (1-ε)-consensus is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n.
Cite as

Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang. Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 48:1-48:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{hirt_et_al:LIPIcs.DISC.2020.48,
  author =	{Hirt, Martin and Kastrati, Ard and Liu-Zhang, Chen-Da},
  title =	{{Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{48:1--48:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.48},
  URN =		{urn:nbn:de:0030-drops-131267},
  doi =		{10.4230/LIPIcs.DISC.2020.48},
  annote =	{Keywords: broadcast, byzantine agreement, multi-threshold}
}
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