Search Results

Documents authored by Yandamuri, Sravya

Document
DOI: 10.4230/LIPIcs.OPODIS.2023.29
On the Round Complexity of Asynchronous Crusader Agreement

Authors: Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)

Abstract
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Cite as

Ittai Abraham, Naama Ben-David, Gilad Stern, and Sravya Yandamuri. On the Round Complexity of Asynchronous Crusader Agreement. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 29:1-29:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2023.29,
  author =	{Abraham, Ittai and Ben-David, Naama and Stern, Gilad and Yandamuri, Sravya},
  title =	{{On the Round Complexity of Asynchronous Crusader Agreement}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{29:1--29:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.29},
  URN =		{urn:nbn:de:0030-drops-195195},
  doi =		{10.4230/LIPIcs.OPODIS.2023.29},
  annote =	{Keywords: lower bounds, asynchronous protocols, round complexity}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2022.24
Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter

Published in: LIPIcs, Volume 253, 26th International Conference on Principles of Distributed Systems (OPODIS 2022)

Abstract
Agreement protocols for partially synchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the network that is less than one-half. In particular, we show a version of HotStuff that retains linear communication complexity in each view, leveraging trusted hardware to tolerate a minority of corruptions. Our result uses expander graph techniques to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael K. Reiter. Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 24:1-24:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.OPODIS.2022.24,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael K.},
  title =	{{Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{24:1--24:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-265-5},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{253},
  editor =	{Hillel, Eshcar and Palmieri, Roberto and Rivi\`{e}re, Etienne},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2022.24},
  URN =		{urn:nbn:de:0030-drops-176448},
  doi =		{10.4230/LIPIcs.OPODIS.2022.24},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2021.62
Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption

Authors: Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael Reiter

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

Abstract
Small trusted hardware primitives can improve fault tolerance of Byzantine Fault Tolerant (BFT) protocols to one-half faults. However, existing works achieve this at the cost of increased communication complexity. In this work, we explore the design of communication-efficient BFT protocols that can boost fault tolerance to one-half without worsening communication complexity. Our results include a version of HotStuff that retains linear communication complexity in each view and a version of the VABA protocol with quadratic communication, both leveraging trusted hardware to tolerate a minority of corruptions. As a building block, we present communication-efficient provable broadcast, a core broadcast primitive with increased fault tolerance. Our results use expander graphs to achieve efficient communication in a manner that may be of independent interest.
Cite as

Sravya Yandamuri, Ittai Abraham, Kartik Nayak, and Michael Reiter. Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{yandamuri_et_al:LIPIcs.DISC.2021.62,
  author =	{Yandamuri, Sravya and Abraham, Ittai and Nayak, Kartik and Reiter, Michael},
  title =	{{Brief Announcement: Communication-Efficient BFT Using Small Trusted Hardware to Tolerate Minority Corruption}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{62:1--62:4},
  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.62},
  URN =		{urn:nbn:de:0030-drops-148647},
  doi =		{10.4230/LIPIcs.DISC.2021.62},
  annote =	{Keywords: communication complexity, consensus, trusted hardware}
}
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