Search Results

Documents authored by Shapiro, Ehud

Document
DOI: 10.4230/LIPIcs.OPODIS.2025.35
Morpheus Consensus: Excelling on Trails and Autobahns

Authors: Andrew Lewis-Pye and Ehud Shapiro

Published in: LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025)

Abstract
Recent research in consensus has often focussed on protocols for State-Machine-Replication (SMR) that can handle high throughputs. Such state-of-the-art protocols (generally DAG-based) induce undue overhead when the needed throughput is low, or else exhibit unnecessarily-poor latency and communication complexity during periods of low throughput. Here we present Morpheus Consensus, which naturally morphs from a quiescent low-throughput leaderless blockchain protocol to a high-throughput leader-based DAG protocol and back, excelling in latency and complexity in both settings. During high-throughout, Morpheus pars with state-of-the-art DAG-based protocols, including Autobahn [Giridharan et al., 2024]. During low-throughput, Morpheus exhibits competitive complexity and lower latency than standard protocols such as PBFT [Castro et al., 1999] and Tendermint [Buchman, 2016; Buchman et al., 2018], which in turn do not perform well during high-throughput. The key idea of Morpheus is that as long as blocks do not conflict (due to Byzantine behaviour, network delays, or high-throughput simultaneous production) it produces a forkless blockchain, promptly finalizing each block upon arrival. It assigns a leader only if one is needed to resolve conflicts, in a manner and with performance not unlike Autobahn.
Cite as

Andrew Lewis-Pye and Ehud Shapiro. Morpheus Consensus: Excelling on Trails and Autobahns. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lewispye_et_al:LIPIcs.OPODIS.2025.35,
  author =	{Lewis-Pye, Andrew and Shapiro, Ehud},
  title =	{{Morpheus Consensus: Excelling on Trails and Autobahns}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-409-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{361},
  editor =	{Arusoaie, Andrei and Onica, Emanuel and Spear, Michael and Tucci-Piergiovanni, Sara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.35},
  URN =		{urn:nbn:de:0030-drops-252086},
  doi =		{10.4230/LIPIcs.OPODIS.2025.35},
  annote =	{Keywords: Distributed computing, consensus, quiescence}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.26
Cordial Miners: Fast and Efficient Consensus for Every Eventuality

Authors: Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Cordial Miners are a family of efficient Byzantine Atomic Broadcast protocols, with instances for asynchrony and eventual synchrony. They improve the latency of state-of-the-art DAG-based protocols by almost 2× and achieve optimal good-case complexity of O(n) by forgoing Reliable Broadcast as a building block. Rather, Cordial Miners use the blocklace - a partially-ordered counterpart of the totally-ordered blockchain data structure - to implement the three algorithmic components of consensus: Dissemination, equivocation-exclusion, and ordering.
Cite as

Idit Keidar, Oded Naor, Ouri Poupko, and Ehud Shapiro. Cordial Miners: Fast and Efficient Consensus for Every Eventuality. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 26:1-26:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{keidar_et_al:LIPIcs.DISC.2023.26,
  author =	{Keidar, Idit and Naor, Oded and Poupko, Ouri and Shapiro, Ehud},
  title =	{{Cordial Miners: Fast and Efficient Consensus for Every Eventuality}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{26:1--26:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.26},
  URN =		{urn:nbn:de:0030-drops-191525},
  doi =		{10.4230/LIPIcs.DISC.2023.26},
  annote =	{Keywords: Byzantine Fault Tolerance, State Machine Replication, DAG, Consensus, Blockchain, Blocklace, Cordial Dissemination}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2023.47
Brief Announcement: Grassroots Distributed Systems: Concept, Examples, Implementation and Applications

Authors: Ehud Shapiro

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
Informally, a distributed system is grassroots if it is permissionless and can have autonomous, independently-deployed instances - geographically and over time - that may interoperate voluntarily once interconnected. More formally, in a grassroots system the set of all correct behaviors of a set of agents P is strictly included in the set of the correct behaviors of P when they are embedded within a larger set of agents P' ⊃ P. Grassroots systems are potentially important as they may allow communities to conduct their social, economic, civic, and political lives in the digital realm solely using their members' networked computing devices (e.g., smartphones), free of third-party control, surveillance, manipulation, coercion, or rent seeking (e.g., by global digital platforms such as Facebook or Bitcoin). Client-server/cloud computing systems are not grassroots, and neither are systems designed to have a single global instance (Bitcoin/Ethereum with hardwired seed miners/bootnodes), and systems that rely on a single global data structure (IPFS, DHTs). An example grassroots system would be a serverless smartphone-based social network supporting multiple independently-budding communities that can merge when a member of one community becomes also a member of another. Here, we formalize the notion of grassroots distributed systems; describe a grassroots dissemination protocol for the model of asynchrony and argue its safety, liveness, and being grassroots; extend the implementation to mobile (address-changing) devices that communicate via an unreliable network (e.g. smartphones using UDP); and discuss how grassroots dissemination can realize grassroots social networking and grassroots cryptocurrencies. The mathematical construction employs distributed multiagent transition systems to define the notions of grassroots protocols, to specify the grassroots dissemination protocols, and to prove their correctness. The protocols use the blocklace - a distributed, partially-ordered counterpart of the replicated, totally-ordered blockchain.
Cite as

Ehud Shapiro. Brief Announcement: Grassroots Distributed Systems: Concept, Examples, Implementation and Applications. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 47:1-47:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{shapiro:LIPIcs.DISC.2023.47,
  author =	{Shapiro, Ehud},
  title =	{{Brief Announcement: Grassroots Distributed Systems: Concept, Examples, Implementation and Applications}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{47:1--47:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.47},
  URN =		{urn:nbn:de:0030-drops-191735},
  doi =		{10.4230/LIPIcs.DISC.2023.47},
  annote =	{Keywords: Grassroots Distributed Systems, Dissemination Protocol, Multiagent Transition Systems, Blocklace, Cordial Dissemination}
}
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
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact