DROPS

Document

DOI: 10.4230/LIPIcs.DISC.2021.3

Frugal Byzantine Computing

Authors: Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract

Traditional techniques for handling Byzantine failures are expensive: digital signatures are too costly, while using 3f+1 replicas is uneconomical (f denotes the maximum number of Byzantine processes). We seek algorithms that reduce the number of replicas to 2f+1 and minimize the number of signatures. While the first goal can be achieved in the message-and-memory model, accomplishing the second goal simultaneously is challenging. We first address this challenge for the problem of broadcasting messages reliably. We study two variants of this problem, Consistent Broadcast and Reliable Broadcast, typically considered very close. Perhaps surprisingly, we establish a separation between them in terms of signatures required. In particular, we show that Consistent Broadcast requires at least 1 signature in some execution, while Reliable Broadcast requires O(n) signatures in some execution. We present matching upper bounds for both primitives within constant factors. We then turn to the problem of consensus and argue that this separation matters for solving consensus with Byzantine failures: we present a practical consensus algorithm that uses Consistent Broadcast as its main communication primitive. This algorithm works for n = 2f+1 and avoids signatures in the common case - properties that have not been simultaneously achieved previously. Overall, our work approaches Byzantine computing in a frugal manner and motivates the use of Consistent Broadcast - rather than Reliable Broadcast - as a key primitive for reaching agreement.

Cite as

Marcos K. Aguilera, Naama Ben-David, Rachid Guerraoui, Dalia Papuc, Athanasios Xygkis, and Igor Zablotchi. Frugal Byzantine Computing. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{aguilera_et_al:LIPIcs.DISC.2021.3,
  author =	{Aguilera, Marcos K. and Ben-David, Naama and Guerraoui, Rachid and Papuc, Dalia and Xygkis, Athanasios and Zablotchi, Igor},
  title =	{{Frugal Byzantine Computing}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{3:1--3:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.3},
  URN =		{urn:nbn:de:0030-drops-148051},
  doi =		{10.4230/LIPIcs.DISC.2021.3},
  annote =	{Keywords: Reliable Broadcast, Consistent Broadcast, Consensus, Byzantine Failure, Message-and-memory}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2017.45

Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures

Authors: Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan, and Marcos K. Aguilera

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

Abstract

Recent work introduced a method to automatically produce concurrent data structures for NUMA architectures. We present a summary of that work.

Cite as

Irina Calciu, Siddhartha Sen, Mahesh Balakrishnan, and Marcos K. Aguilera. Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 45:1-45:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{calciu_et_al:LIPIcs.DISC.2017.45,
  author =	{Calciu, Irina and Sen, Siddhartha and Balakrishnan, Mahesh and Aguilera, Marcos K.},
  title =	{{Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{45:1--45:3},
  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.45},
  URN =		{urn:nbn:de:0030-drops-80122},
  doi =		{10.4230/LIPIcs.DISC.2017.45},
  annote =	{Keywords: concurrent data structures, log, NUMA architecture, replication}
}

Search Results

Documents authored by Aguilera, Marcos K.

Frugal Byzantine Computing

Abstract

Cite as

Brief Announcement: Black-Box Concurrent Data Structures for NUMA Architectures

Abstract

Cite as

Thanks for your feedback!

Could not send message