8 Search Results for "Stern, Gilad"


Document
Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance

Authors: Ittai Abraham, Gilad Asharov, and Anirudh Chandramouli

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)


Abstract
The COOL protocol of Chen (DISC'21) is a major advance that enables perfect security for various tasks (in particular, Byzantine Agreement in Synchrony and Reliable Broadcast in Asynchrony). For an input of size L bits, its communication complexity is O(nL+n² log n), which is optimal up to a log n factor. Unfortunately, Chen’s analysis is rather intricate and complex. Our main contribution is a simple analysis of a new variant of COOL based on elementary counting arguments. Our main consistency proof takes less than two pages (instead of over 20 pages), making the COOL protocol much more accessible. In addition, the simple analysis allows us to improve the protocol by reducing one round of communication and reducing the communication complexity by 40%. In addition, we suggest a new way of extracting the core properties of COOL as a new primitive, which we call Graded Dispersal. We show how Graded Dispersal can then be used to obtain efficient solutions for Byzantine Agreement, Verifiable Information Dispersal, Gradecast, and Reliable Broadcast (in both Synchrony and Asynchrony, where appropriate). Our improvement of COOL directly applies here, and we improve the state-of-the-art in all those primitives by reducing at least one round and 40% communication.

Cite as

Ittai Abraham, Gilad Asharov, and Anirudh Chandramouli. Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)


Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.ITCS.2025.1,
  author =	{Abraham, Ittai and Asharov, Gilad and Chandramouli, Anirudh},
  title =	{{Simple Is COOL: Graded Dispersal and Its Applications for Byzantine Fault Tolerance}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.1},
  URN =		{urn:nbn:de:0030-drops-226295},
  doi =		{10.4230/LIPIcs.ITCS.2025.1},
  annote =	{Keywords: Byzantine Agreement, Broadcast}
}
Document
Quit-Resistant Reliable Broadcast and Efficient Terminating Gather

Authors: Mose Mizrahi Erbes and Roger Wattenhofer

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)


Abstract
Termination is a central property in distributed computing. A party terminates a protocol once it stops accepting and sending messages. We discover that byzantine reliable broadcast is sometimes used in a manner which leads to non-terminating protocols. We consider an asynchronous network of n parties up to t of which are byzantine, and show that if each party is to broadcast its value and terminate upon obtaining n - t values, then composing n parallel reliable broadcast instances leads to non-termination. The issue is that a party must quit t broadcast instances early in order to terminate, a behaviour not supported by ordinary reliable broadcast. So, we modify Bracha’s protocol into a quit-resistant reliable broadcast (QBRB) protocol which lets the parties quit early. This protocol retains its termination guarantees as long as no party quits before some party terminates. Then, we turn our attention to Gather, an all-to-all broadcast primitive which guarantees that the parties obtain n - t common values. Existing error-free deterministic Gather protocols either run forever, or fail to terminate since the parties quit reliable broadcast instances. We design an error-free, deterministic, terminating (and binding) Gather protocol for 𝓁-bit inputs with the communication complexity 𝒪(𝓁 n² + n³log n). This matches the state-of-the-art for non-terminating Gather. Finally, inspired by our QBRB protocol, we design a reliable broadcast protocol which retains its termination guarantees no matter when any party quits. To achieve this, we give each party the option to output ⊥ if more than q parties quit before some party terminates. The protocol requires 4t + q < n, which is optimal, and it lets parties quit after they have suffered transient crash failures so that they can help the remaining parties terminate.

Cite as

Mose Mizrahi Erbes and Roger Wattenhofer. Quit-Resistant Reliable Broadcast and Efficient Terminating Gather. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{mizrahierbes_et_al:LIPIcs.OPODIS.2024.15,
  author =	{Mizrahi Erbes, Mose and Wattenhofer, Roger},
  title =	{{Quit-Resistant Reliable Broadcast and Efficient Terminating Gather}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.15},
  URN =		{urn:nbn:de:0030-drops-225519},
  doi =		{10.4230/LIPIcs.OPODIS.2024.15},
  annote =	{Keywords: Asynchronous networks, byzantine fault tolerance, protocol termination, reliable broadcast, all-to-all broadcast, gather}
}
Document
Byzantine Reliable Broadcast with Low Communication and Time Complexity

Authors: Thomas Locher

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)


Abstract
Byzantine reliable broadcast is a fundamental problem in distributed computing, which has been studied extensively over the past decades. State-of-the-art algorithms are predominantly based on the approach to share encoded fragments of the broadcast message, yielding an asymptotically optimal communication complexity when the message size exceeds the network size, a condition frequently encountered in practice. However, algorithms following the standard coding approach incur an overhead factor of at least 3, which can already be a burden for bandwidth-constrained applications. Minimizing this overhead is an important objective with immediate benefits to protocols that use a reliable broadcast routine as a building block. This paper introduces a novel mechanism to lower the communication and computational complexity. Two algorithms are presented that employ this mechanism to reliably broadcast messages in an asynchronous network where less than a third of all nodes are Byzantine. The first algorithm reduces the overhead factor to 2 and has a time complexity of 3 if the sender is honest, whereas the second algorithm attains an optimal time complexity of 2 with the same overhead factor in the absence of equivocation. Moreover, an optimization is proposed that reduces the overhead factor to 3/2 under normal operation in practice. Lastly, a lower bound is proved that an overhead factor lower than 3/2 cannot be achieved for a relevant class of reliable broadcast algorithms.

Cite as

Thomas Locher. Byzantine Reliable Broadcast with Low Communication and Time Complexity. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{locher:LIPIcs.OPODIS.2024.16,
  author =	{Locher, Thomas},
  title =	{{Byzantine Reliable Broadcast with Low Communication and Time Complexity}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.16},
  URN =		{urn:nbn:de:0030-drops-225524},
  doi =		{10.4230/LIPIcs.OPODIS.2024.16},
  annote =	{Keywords: Asynchronous Networks, Reliable Broadcast, Communication Complexity}
}
Document
Reliable Communication in Hybrid Authentication and Trust Models

Authors: Rowdy Chotkan, Bart Cox, Vincent Rahli, and Jérémie Decouchant

Published in: LIPIcs, Volume 324, 28th International Conference on Principles of Distributed Systems (OPODIS 2024)


Abstract
Reliable communication is a fundamental distributed communication abstraction that allows any two nodes within a network to communicate with each other. It is necessary for more powerful communication primitives, such as broadcast and consensus. Using different authentication models, two classical protocols implement reliable communication in unknown and sufficiently connected networks. In the former, network links are authenticated, and processes rely on dissemination paths to authenticate messages. In the latter, processes generate digital signatures that are flooded throughout the network. This work considers the hybrid system model that combines authenticated links and authenticated processes. Additionally, we aim to leverage the possible presence of trusted nodes (e.g., network gateways) and trusted components (e.g., Intel SGX enclaves). We first extend the two classical reliable communication protocols to leverage trusted nodes. Then we propose DualRC, our most generic algorithm that considers the hybrid authentication model by manipulating dissemination paths and digital signatures, and leverages the possible presence of trusted nodes and trusted components. We describe and prove methods that establish whether our algorithms implement reliable communication on a given network.

Cite as

Rowdy Chotkan, Bart Cox, Vincent Rahli, and Jérémie Decouchant. Reliable Communication in Hybrid Authentication and Trust Models. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 25:1-25:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{chotkan_et_al:LIPIcs.OPODIS.2024.25,
  author =	{Chotkan, Rowdy and Cox, Bart and Rahli, Vincent and Decouchant, J\'{e}r\'{e}mie},
  title =	{{Reliable Communication in Hybrid Authentication and Trust Models}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{25:1--25:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-360-7},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{324},
  editor =	{Bonomi, Silvia and Galletta, Letterio and Rivi\`{e}re, Etienne and Schiavoni, Valerio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2024.25},
  URN =		{urn:nbn:de:0030-drops-225611},
  doi =		{10.4230/LIPIcs.OPODIS.2024.25},
  annote =	{Keywords: Reliable communication, Byzantine, Authentication models, Trust}
}
Document
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
New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks

Authors: Ittai Abraham and Gilad Stern

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


Abstract
In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First, we extend the Dolev-Reischuk family of lower bounds and prove a new lower bound for Crusader Broadcast protocols. Our lower bound for crusader broadcast requires non-trivial extensions and a much stronger Byzantine adversary with the ability to simulate honest parties. Secondly, we extend our lower bounds to all-but-m Crusader Broadcast, in which up to m parties are allowed to output a different value. Finally, we discuss the ways in which these lower bounds relate to the security of blockchain systems. We show how Eclipse-style attacks in such systems can be viewed as specific instances of the attacks used in our lower bound for Crusader Broadcast. This connection suggests a more systematic way of analyzing and reasoning about Eclipse-style attacks through the lens of the Dolev-Reischuk family of attacks.

Cite as

Ittai Abraham and Gilad Stern. New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks. In 26th International Conference on Principles of Distributed Systems (OPODIS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 253, pp. 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)


Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2022.16,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{New Dolev-Reischuk Lower Bounds Meet Blockchain Eclipse Attacks}},
  booktitle =	{26th International Conference on Principles of Distributed Systems (OPODIS 2022)},
  pages =	{16:1--16:18},
  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.16},
  URN =		{urn:nbn:de:0030-drops-176368},
  doi =		{10.4230/LIPIcs.OPODIS.2022.16},
  annote =	{Keywords: consensus, crusader broadcast, Byzantine fault tolerance, blockchain, synchrony, lower bounds}
}
Document
Brief Announcement
Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults

Authors: Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)


Abstract
Protocols solving authenticated consensus in synchronous networks with Byzantine faults have been widely researched and known to exists if and only if n > 2f for f Byzantine faults. Similarly, protocols solving authenticated consensus in partially synchronous networks are known to exist if n > 3f+2k for f Byzantine faults and k crash faults. In this work we fill a natural gap in our knowledge by presenting MixSync, an authenticated consensus protocol in synchronous networks resilient to f Byzantine faults and k crash faults if n > 2f+k. As a basic building block, we first define and then construct a publicly verifiable crusader agreement protocol with the same resilience. The protocol uses a simple double-send round to guarantee non-equivocation, a technique later used in the MixSync protocol. We then discuss how to construct a state machine replication protocol using these ideas, and how they can be used in general to make such protocols resilient to crash faults. Finally, we prove lower bounds showing that n > 2f+k is optimally resilient for consensus and state machine replication protocols.

Cite as

Ittai Abraham, Danny Dolev, Alon Kagan, and Gilad Stern. Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 38:1-38:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)


Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2022.38,
  author =	{Abraham, Ittai and Dolev, Danny and Kagan, Alon and Stern, Gilad},
  title =	{{Brief Announcement: Authenticated Consensus in Synchronous Systems with Mixed Faults}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{38:1--38:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.38},
  URN =		{urn:nbn:de:0030-drops-172292},
  doi =		{10.4230/LIPIcs.DISC.2022.38},
  annote =	{Keywords: consensus, state machine replication, mixed faults, synchrony, lower bounds}
}
Document
Information Theoretic HotStuff

Authors: Ittai Abraham and Gilad Stern

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


Abstract
This work presents Information Theoretic HotStuff (IT-HS), a new optimally resilient protocol for solving Byzantine Agreement in partial synchrony with information theoretic security guarantees. In particular, IT-HS does not depend on any PKI or common setup assumptions and is resilient to computationally unbounded adversaries. IT-HS is based on the Primary-Backup view-based paradigm. In IT-HS, in each view, and in each view change, each party sends only a constant number of words to every other party. This yields an O(n²) word and message complexity in each view. In addition, IT-HS requires just O(1) persistent local storage and O(n) transient local storage. Finally, like all Primary-Backup view-based protocols in partial synchrony, after the system becomes synchronous, all nonfaulty parties decide on a value in the first view a nonfaulty leader is chosen. Moreover, like PBFT and HotStuff, IT-HS is optimistically responsive: with a nonfaulty leader, parties decide as quickly as the network allows them to do so, without regard for the known upper bound on network delay. Our work improves in multiple dimensions upon the information theoretic version of PBFT presented by Miguel Castro, and can be seen as an information theoretic variant of the HotStuff paradigm.

Cite as

Ittai Abraham and Gilad Stern. Information Theoretic HotStuff. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)


Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.OPODIS.2020.11,
  author =	{Abraham, Ittai and Stern, Gilad},
  title =	{{Information Theoretic HotStuff}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{11:1--11: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.11},
  URN =		{urn:nbn:de:0030-drops-134969},
  doi =		{10.4230/LIPIcs.OPODIS.2020.11},
  annote =	{Keywords: byzantine agreement, partial synchrony, bounded space}
}
  • Refine by Type
  • 8 Document/PDF
  • 4 Document/HTML

  • Refine by Publication Year
  • 4 2025
  • 1 2024
  • 1 2023
  • 1 2022
  • 1 2021

  • Refine by Author
  • 5 Abraham, Ittai
  • 4 Stern, Gilad
  • 1 Asharov, Gilad
  • 1 Ben-David, Naama
  • 1 Chandramouli, Anirudh
  • Show More...

  • Refine by Series/Journal
  • 8 LIPIcs

  • Refine by Classification
  • 7 Theory of computation → Distributed algorithms
  • 2 Computer systems organization → Fault-tolerant network topologies
  • 1 Security and privacy
  • 1 Security and privacy → Cryptography
  • 1 Security and privacy → Distributed systems security
  • Show More...

  • Refine by Keyword
  • 3 lower bounds
  • 2 consensus
  • 2 synchrony
  • 1 Asynchronous Networks
  • 1 Asynchronous networks
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail