DROPS

Document

A Survey of Real-Time Support, Analysis, and Advancements in ROS 2

Authors: Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper

Published in: LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1

Abstract

The Robot Operating System 2 (ROS 2) has emerged as a relevant middleware framework for robotic applications, offering modularity, distributed execution, and communication. In the last six years, ROS 2 has drawn increasing attention from the real-time systems community and industry. This survey presents a comprehensive overview of research efforts that analyze, enhance, and extend ROS 2 to support real-time execution. We first provide a detailed description of the internal scheduling mechanisms of ROS 2 and its layered architecture, including the interaction with DDS-based communication and other communication middleware. We then review key contributions from the literature, covering timing analysis for both single- and multi-threaded executors, metrics such as response time, reaction time, and data age, and different communication modes. The survey also discusses community-driven enhancements to the ROS 2 runtime, including new executor algorithm designs, real-time GPU management, and microcontroller support via micro-ROS. Furthermore, we summarize techniques for bounding DDS communication delays, message filters, and profiling tools that have been developed to support analysis and experimentation. To help systematize this growing body of work, we introduce taxonomies that classify the surveyed contributions based on different criteria. This survey aims to guide both researchers and practitioners in understanding and improving the real-time capabilities of ROS 2.

Cite as

Daniel Casini, Jian-Jia Chen, Jing Li, Federico Reghenzani, and Harun Teper. A Survey of Real-Time Support, Analysis, and Advancements in ROS 2. In LITES, Volume 11, Issue 1 (2026). Leibniz Transactions on Embedded Systems, Volume 11, Issue 1, pp. 1:1-1:37, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@Article{casini_et_al:LITES.11.1.1,
  author =	{Casini, Daniel and Chen, Jian-Jia and Li, Jing and Reghenzani, Federico and Teper, Harun},
  title =	{{A Survey of Real-Time Support, Analysis, and Advancements in ROS 2}},
  journal =	{Leibniz Transactions on Embedded Systems},
  pages =	{1:1--1:37},
  ISSN =	{2199-2002},
  year =	{2026},
  volume =	{11},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LITES.11.1.1},
  URN =		{urn:nbn:de:0030-drops-257914},
  doi =		{10.4230/LITES.11.1.1},
  annote =	{Keywords: ROS 2, middleware, real-time, timing predictability, publish-subscribe}
}

Document

DOI: 10.4230/LIPIcs.ITCS.2026.52

Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract

In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.

Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.7

Mobile Byzantine Agreement in a Trusted World

Authors: Bo Pan and Maria Potop-Butucaru

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

Abstract

In this paper, we address the Byzantine Agreement problem in synchronous systems where Byzantine agents can move from process to process, corrupting their host. We focus on two representative models: Garay’s and Buhrman’s models. In Garay’s model, when a process has been left by the Byzantine agent, it enters a cured state, is aware of its condition, and can remain silent for a round to prevent the dissemination of incorrect information. In Buhrman’s model, a Byzantine agent moves together with the message. It has been shown that solving Byzantine Agreement requires at least 4t + 1 processes in Garay’s model, and at least 3t + 1 in Buhrman’s model. In this paper, we aim to increase the tolerance to mobile Byzantine agents by integrating a trusted counter abstraction into both models. This abstraction prevents nodes from equivocating. In the new models, we prove that at least 3t+1, respectively 2t+1 processors are needed to tolerate t mobile Byzantine agents. Furthermore, we propose novel Mobile Byzantine Agreement algorithms that match these new lower bounds for both Garay’s and Buhrman’s models, achieving agreement in 𝒪(n) synchronous rounds.

Cite as

Bo Pan and Maria Potop-Butucaru. Mobile Byzantine Agreement in a Trusted World. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pan_et_al:LIPIcs.OPODIS.2025.7,
  author =	{Pan, Bo and Potop-Butucaru, Maria},
  title =	{{Mobile Byzantine Agreement in a Trusted World}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{7:1--7: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.7},
  URN =		{urn:nbn:de:0030-drops-251809},
  doi =		{10.4230/LIPIcs.OPODIS.2025.7},
  annote =	{Keywords: Byzantine Agreement, Mobile Faults, Trusted Abstractions}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.12

Efficient Byzantine Reliable Broadcast in the Failure Case

Authors: Thomas Locher

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

Abstract

Reliable broadcast is a fundamental primitive in distributed computing that is widely used in various applications. Several new reliable broadcast algorithms have been presented in recent years, primarily focusing on reducing the communication complexity, which is the total number of exchanged bits in the worst case. While significant progress has been achieved, all proposed algorithms share a common weakness. Executions may fail, i.e., no message is ever delivered, while incurring a communication complexity equal or nearly equal to the communication complexity of executions where a message is delivered. In fact, a single Byzantine node, acting as the dedicated sender, is sufficient to trigger such executions, causing all nodes to consume bandwidth in vain. This paper introduces the novel concept of a reliable broadcast detector, a distributed algorithm that can be coupled with a reliable broadcast algorithm to minimize the communication complexity of failed executions. Two concrete detectors are presented with different requirements and properties. Additionally, reliable broadcast algorithms that utilize detectors are introduced, the main algorithm guaranteeing an overhead factor, compared to an ideal failure-free execution, that tends to 2 as the network size increases. Furthermore, a lower bound is proven that an overhead factor of 5/3 is inevitable when the sender initially broadcasts the message, as is the case for the proposed algorithm. Therefore, it achieves a bound that is close to optimal for any algorithm with this property.

Cite as

Thomas Locher. Efficient Byzantine Reliable Broadcast in the Failure Case. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 12:1-12:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{locher:LIPIcs.OPODIS.2025.12,
  author =	{Locher, Thomas},
  title =	{{Efficient Byzantine Reliable Broadcast in the Failure Case}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{12:1--12: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.12},
  URN =		{urn:nbn:de:0030-drops-251854},
  doi =		{10.4230/LIPIcs.OPODIS.2025.12},
  annote =	{Keywords: asynchronous networks, reliable broadcast, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.15

Time-Optimal and Energy-Efficient Deterministic Consensus

Authors: Shachar Meir, Hugo Mirault, David Peleg, and Peter Robinson

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

Abstract

We study fault-tolerant consensus in a variant of the synchronous message passing model, where, in each round, every node can choose to be awake or asleep. This is known as the sleeping model (Chatterjee, Gmyr, Pandurangan PODC 2020) and defines the awake complexity (also called energy complexity), which measures the maximum number of rounds that any node is awake throughout the execution. Only awake nodes can send and receive messages in a given round and all messages sent to sleeping nodes are lost. We present new deterministic consensus algorithms that tolerate up to f < n crash failures, where n is the number of nodes. Our algorithms match the optimal time complexity lower bound of f+1 rounds. For multi-value consensus, where the input values are chosen from some possibly large set, we achieve an energy complexity of 𝒪(⌈ f² / n ⌉) rounds, whereas for binary consensus, we show an algorithm to achieve 𝒪(⌈ f / √n ⌉) energy complexity.

Cite as

Shachar Meir, Hugo Mirault, David Peleg, and Peter Robinson. Time-Optimal and Energy-Efficient Deterministic Consensus. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 15:1-15:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{meir_et_al:LIPIcs.OPODIS.2025.15,
  author =	{Meir, Shachar and Mirault, Hugo and Peleg, David and Robinson, Peter},
  title =	{{Time-Optimal and Energy-Efficient Deterministic Consensus}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{15:1--15:16},
  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.15},
  URN =		{urn:nbn:de:0030-drops-251881},
  doi =		{10.4230/LIPIcs.OPODIS.2025.15},
  annote =	{Keywords: Distributed computing, Crash faults, Consensus, Energy complexity, Sleeping model}
}

Document

DOI: 10.4230/LIPIcs.OPODIS.2025.16

Asynchronous Approximate Agreement with Quadratic Communication

Authors: Mose Mizrahi Erbes and Roger Wattenhofer

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

Abstract

We study approximate agreement in an asynchronous network of n parties, up to t of which are byzantine. This an agreement task where the parties obtain approximately equal inputs in the convex hull of their inputs. In an asynchronous network, it can be solved with the optimal resilience t < n/3 by forcing the parties to reliably broadcast their messages and thus preventing inconsistent byzantine behavior. This costs Θ(n²) messages per reliable broadcast, or Θ(n³) messages per protocol iteration. In this work, we forgo reliable broadcast to achieve asynchronous approximate agreement against t < n/3 faults with quadratic communication. In a tree with the maximum degree Δ and the centroid decomposition height h, we achieve edge agreement (agreement on two adjacent vertices) in at most 6h + 1 rounds with 𝒪(n²) messages of size 𝒪(log Δ + log h) per round. We do this by designing a 6-round multivalued 2-graded consensus protocol and using it to construct a recursive edge agreement protocol. Then, we achieve edge agreement in the infinite path ℤ, again by using 2-graded consensus. Finally, we show that our edge agreement protocol enables approximate agreement in ℝ (with outputs that are at most some small parameter ε > 0 apart) in 6log₂M/(ε) + 𝒪(log log M/(ε)) rounds with 𝒪(n²) messages of size 𝒪(log log M/(ε)) per round, where M is the maximum non-byzantine input magnitude.

Cite as

Mose Mizrahi Erbes and Roger Wattenhofer. Asynchronous Approximate Agreement with Quadratic Communication. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 16:1-16:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mizrahierbes_et_al:LIPIcs.OPODIS.2025.16,
  author =	{Mizrahi Erbes, Mose and Wattenhofer, Roger},
  title =	{{Asynchronous Approximate Agreement with Quadratic Communication}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{16:1--16:26},
  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.16},
  URN =		{urn:nbn:de:0030-drops-251890},
  doi =		{10.4230/LIPIcs.OPODIS.2025.16},
  annote =	{Keywords: Approximate agreement, byzantine fault tolerance, communication complexity}
}

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.2025.6

Hierarchical Consensus: Scalability Through Optimism and Weak Liveness

Authors: Pedro Antonino, Antoine Durand, and A. W. Roscoe

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

Scalability is a central concern of Byzantine Fault Tolerant (BFT) distributed protocols. The ubiquitous approach to work around the well-known Dolev-Reischuk Ω(n²) communication complexity lower bound is to use a random selection process to draw a hopefully small committee from a population of agents to run the communication-heavy protocol. We propose a notion of hierarchical consensus that combines two sub-protocols: an optimistic primary sub-protocol that can tolerate less than 1/2 failures and a fallback secondary protocol that can tolerate less than 1/3 failures; we achieve the higher failure threshold by requiring a weaker notion of liveness for the primary. This distinction between the level of fault tolerance between primary and secondary is reflected in the size of committees implementing these protocols. For a population of agents with close to 2/3 of honest agents, we need to select a committee with hundreds of agents to reach the level of tolerance expected for the primary, whereas we need thousands to reach the level expected for the secondary with a very small probability of error ε. Our hierarchical construct is such that if the primary comes to a decision, it can simply propagate it to the secondary protocol, so it does not need to properly engage in an agreement protocol independently. Our architecture is flexible and allows us to use our technique for most protocols that are based on random sampling. By studying hierarchical protocols, we discovered new theoretical results of independent interest. Specifically, the ability to handover from a primary protocol requires a new Justifiability property that allows agents to pre-decide on a value, such that if the protocol decides, it must be on that pre-decided value.

Cite as

Pedro Antonino, Antoine Durand, and A. W. Roscoe. Hierarchical Consensus: Scalability Through Optimism and Weak Liveness. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 6:1-6:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{antonino_et_al:LIPIcs.DISC.2025.6,
  author =	{Antonino, Pedro and Durand, Antoine and Roscoe, A. W.},
  title =	{{Hierarchical Consensus: Scalability Through Optimism and Weak Liveness}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{6:1--6:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.6},
  URN =		{urn:nbn:de:0030-drops-248232},
  doi =		{10.4230/LIPIcs.DISC.2025.6},
  annote =	{Keywords: Hierarchical, Handover, Justifiability, Consensus, Distributed Systems, Blockchain}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.4

pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer

Authors: Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

This work addresses the inherent issues of high latency in blockchains and low scalability in traditional consensus protocols. We present pod, a novel notion of consensus whose first priority is to achieve the physically-optimal latency of 2δ, or one round-trip, i.e., requiring only one network trip (duration δ) for writing a transaction and one for reading it. To accomplish this, we first eliminate inter-replica communication. Instead, clients send transactions directly to all replicas, which independently process transactions and append them to local logs. Replicas assign a timestamp and a sequence number to each transaction in their logs, allowing clients to extract valuable metadata about the transactions and the system state. Later on, clients retrieve these logs and extract transactions (and associated metadata) from them. Necessarily, this construction achieves weaker properties than a total-order broadcast protocol, due to existing lower bounds. Our work models the primitive of pod and defines its security properties. We then show pod-core, a protocol that satisfies properties such as transaction confirmation within 2δ, censorship resistance against Byzantine replicas, and accountability for safety violations. We show that single-shot auctions can be realized using the pod notion and observe that it is also sufficient for other popular applications.

Cite as

Orestis Alpos, Bernardo David, Jakov Mitrovski, Odysseas Sofikitis, and Dionysis Zindros. pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 4:1-4:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{alpos_et_al:LIPIcs.DISC.2025.4,
  author =	{Alpos, Orestis and David, Bernardo and Mitrovski, Jakov and Sofikitis, Odysseas and Zindros, Dionysis},
  title =	{{pod: An Optimal-Latency, Censorship-Free, and Accountable Generalized Consensus Layer}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{4:1--4:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.4},
  URN =		{urn:nbn:de:0030-drops-248219},
  doi =		{10.4230/LIPIcs.DISC.2025.4},
  annote =	{Keywords: consensus, censorship resistance, accountability, auctions}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.5

DAG It Off: Latency Prefers No Common Coins

Authors: Ignacio Amores-Sesar, Viktor Grøndal, Adam Holmgård, and Mads Ottendal

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We introduce Black Marlin, the first Directed Acyclic Graph (DAG)-based Byzantine atomic broadcast protocol in a partially synchronous setting that successfully forgoes the reliable broadcast and common coin primitives. Black Marlin achieves the optimal latency of 3 rounds of communication (4.25 with Byzantine faults) while maintaining optimal communication and amortized communication complexities. We present a formal security analysis of the protocol, accompanied by empirical evidence that Black Marlin outperforms state-of-the-art DAG-based protocols in both throughput and latency.

Cite as

Ignacio Amores-Sesar, Viktor Grøndal, Adam Holmgård, and Mads Ottendal. DAG It Off: Latency Prefers No Common Coins. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 5:1-5:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amoressesar_et_al:LIPIcs.DISC.2025.5,
  author =	{Amores-Sesar, Ignacio and Gr{\o}ndal, Viktor and Holmg\r{a}rd, Adam and Ottendal, Mads},
  title =	{{DAG It Off: Latency Prefers No Common Coins}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{5:1--5:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.5},
  URN =		{urn:nbn:de:0030-drops-248221},
  doi =		{10.4230/LIPIcs.DISC.2025.5},
  annote =	{Keywords: Atomic broadcast, DAG-based, Partial synchrony}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.1

ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding

Authors: Ittai Abraham and Gilad Asharov

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

Asynchronous byzantine agreement extension studies the message complexity of L-bit multivalued asynchronous byzantine agreement given access to a binary asynchronous Byzantine agreement protocol. We prove that asynchronous byzantine agreement extension can be solved with perfect security and optimal resilience in O(nL+n² log n) total communication (in bits) in addition to a single call to a binary asynchronous Byzantine agreement protocol. For L = O(n log n), this gives an asymptotically optimal protocol, resolving a question that remained open for nearly two decades. List decoding is a fundamental concept in theoretical computer science and cryptography, enabling error correction beyond the unique decoding radius and playing a critical role in constructing robust codes, hardness amplification, and secure cryptographic protocols. A key novelty of our perfectly secure and optimally resilient asynchronous byzantine agreement extension protocol is that it uses list decoding - making a striking new connection between list decoding and asynchronous Byzantine agreement.

Cite as

Ittai Abraham and Gilad Asharov. ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 1:1-1:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{abraham_et_al:LIPIcs.DISC.2025.1,
  author =	{Abraham, Ittai and Asharov, Gilad},
  title =	{{ABEL: Perfect Asynchronous Byzantine Extension from List-Decoding}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{1:1--1:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.1},
  URN =		{urn:nbn:de:0030-drops-248185},
  doi =		{10.4230/LIPIcs.DISC.2025.1},
  annote =	{Keywords: Asynchronous Byzantine Agreement, Perfect Security}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.39

TEE Is Not a Healer: Rollback-Resistant Reliable Storage

Authors: Sadegh Keshavarzi, Gregory Chockler, and Alexey Gotsman

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

Recent advances in secure hardware technologies, such as Intel SGX or ARM TrustZone, offer an opportunity to substantially reduce the costs of Byzantine fault-tolerance by placing the program code and state within a secure enclave known as a Trusted Execution Environment (TEE). However, the protection offered by a TEE only applies during program execution. Once power is switched off, the non-volatile portion of the program state becomes vulnerable to rollback attacks wherein it is undetectably reverted to an older version. In this paper we consider the problem of implementing reliable read/write registers out of failure-prone replicas subject to state rollbacks. To this end, we introduce a new unified model that captures multiple failure types that can affect a TEE-based system and establish tight bounds on the fault-tolerance of register constructions in this model. We consider both the static case, where failure thresholds hold throughout the entire execution, and the dynamic case, where any number of replicas can roll back, provided these failures do not occur too often. Our dynamic register emulation algorithm, TEE-Rex , provides the first correct implementation of a distributed state recovery procedure that requires neither durable storage nor specialized hardware, such as trusted monotonic counters.

Cite as

Sadegh Keshavarzi, Gregory Chockler, and Alexey Gotsman. TEE Is Not a Healer: Rollback-Resistant Reliable Storage. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 39:1-39:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{keshavarzi_et_al:LIPIcs.DISC.2025.39,
  author =	{Keshavarzi, Sadegh and Chockler, Gregory and Gotsman, Alexey},
  title =	{{TEE Is Not a Healer: Rollback-Resistant Reliable Storage}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{39:1--39:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.39},
  URN =		{urn:nbn:de:0030-drops-248560},
  doi =		{10.4230/LIPIcs.DISC.2025.39},
  annote =	{Keywords: Trusted execution environments, fault tolerance, crash recovery}
}

Document

Brief Announcement

DOI: 10.4230/LIPIcs.DISC.2025.61

Brief Announcement: Asynchronous Approximate Agreement with Quadratic Communication

Authors: Mose Mizrahi Erbes and Roger Wattenhofer

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We consider an asynchronous network of n message-sending parties, up to t of which are byzantine. We study approximate agreement, where the parties obtain approximately equal outputs in the convex hull of their inputs. In their seminal work, Abraham, Amit and Dolev [OPODIS '04] solve this problem in ℝ with the optimal resilience t < n/3 with a protocol where each party reliably broadcasts a value in every iteration. This takes Θ(n²) messages per reliable broadcast, or Θ(n³) messages per iteration. In this work, we forgo reliable broadcast to achieve asynchronous approximate agreement against t < n/3 faults with quadratic communication. In a tree with the maximum degree Δ and the centroid decomposition height h, we achieve edge agreement in at most 6h + 1 rounds with 𝒪(n²) messages of size 𝒪(log Δ + log h) per round. We do this by designing a 6-round multivalued 2-graded consensus protocol and using it to recursively reduce the task to edge agreement in a subtree with a smaller centroid decomposition height. Then, we achieve edge agreement in the infinite path ℤ, again with the help of 2-graded consensus. Finally, we show that our edge agreement protocol enables ε-agreement in ℝ in 6log₂M/(ε) + 𝒪(log log M/(ε)) rounds with 𝒪(n² log M/(ε)) messages and 𝒪(n²log M/(ε)log log M/(ε)) bits of communication, where M is the maximum non-byzantine input magnitude.

Cite as

Mose Mizrahi Erbes and Roger Wattenhofer. Brief Announcement: Asynchronous Approximate Agreement with Quadratic Communication. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 61:1-61:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{mizrahierbes_et_al:LIPIcs.DISC.2025.61,
  author =	{Mizrahi Erbes, Mose and Wattenhofer, Roger},
  title =	{{Brief Announcement: Asynchronous Approximate Agreement with Quadratic Communication}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{61:1--61:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.61},
  URN =		{urn:nbn:de:0030-drops-248771},
  doi =		{10.4230/LIPIcs.DISC.2025.61},
  annote =	{Keywords: Approximate agreement, byzantine fault tolerance, communication complexity}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.15

Asynchronous Latency and Fast Atomic Snapshot

Authors: João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

This paper introduces a novel, fast atomic-snapshot protocol for asynchronous message-passing systems. In the process of defining what "fast" means exactly, we spot a few interesting issues that arise when conventional time metrics are applied to long-lived asynchronous algorithms. We reveal some gaps in latency claims made in earlier work on snapshot algorithms, which hamper their comparative time-complexity analysis. We then come up with a new unifying time-complexity metric that captures the latency of an operation in an asynchronous, long-lived implementation. This allows us to formally grasp latency improvements of our atomic-snapshot algorithm with respect to the state-of-the-art protocols: optimal latency in fault-free runs without contention, short constant latency in fault-free runs with contention, the worst-case latency proportional to the number of active concurrent failures, and constant amortized latency.

Cite as

João Paulo Bezerra, Luciano Freitas, Petr Kuznetsov, and Matthieu Rambaud. Asynchronous Latency and Fast Atomic Snapshot. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 15:1-15:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.DISC.2025.15,
  author =	{Bezerra, Jo\~{a}o Paulo and Freitas, Luciano and Kuznetsov, Petr and Rambaud, Matthieu},
  title =	{{Asynchronous Latency and Fast Atomic Snapshot}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{15:1--15:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.15},
  URN =		{urn:nbn:de:0030-drops-248326},
  doi =		{10.4230/LIPIcs.DISC.2025.15},
  annote =	{Keywords: Asynchronous systems, time complexity, atomic snapshot, crash faults}
}

Document

DOI: 10.4230/LIPIcs.DISC.2025.42

Kudzu: Fast and Simple High-Throughput BFT

Authors: Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen

Published in: LIPIcs, Volume 356, 39th International Symposium on Distributed Computing (DISC 2025)

Abstract

We present Kudzu, a high-throughput atomic broadcast protocol with an integrated fast path. Our contribution is based on the combination of two lines of work. Firstly, our protocol achieves finality in just two rounds of communication if all but p out of n = 3f + 2p + 1 participating replicas behave correctly, where f is the number of Byzantine faults that are tolerated. Due to the seamless integration of the fast path, even in the presence of more than p faults, our protocol maintains state-of-the-art characteristics. Secondly, our protocol utilizes the bandwidth of participating replicas in a balanced way, alleviating the bottleneck at the leader, and thus enabling high throughput. This is achieved by disseminating blocks using erasure codes. Despite combining a novel set of advantages, Kudzu is remarkably simple: intricacies such as "progress certificates", complex view changes, and speculative execution are avoided.

Cite as

Victor Shoup, Jakub Sliwinski, and Yann Vonlanthen. Kudzu: Fast and Simple High-Throughput BFT. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 42:1-42:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{shoup_et_al:LIPIcs.DISC.2025.42,
  author =	{Shoup, Victor and Sliwinski, Jakub and Vonlanthen, Yann},
  title =	{{Kudzu: Fast and Simple High-Throughput BFT}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{42:1--42:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-402-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{356},
  editor =	{Kowalski, Dariusz R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2025.42},
  URN =		{urn:nbn:de:0030-drops-248597},
  doi =		{10.4230/LIPIcs.DISC.2025.42},
  annote =	{Keywords: Consensus, Blockchain, Byzantine Fault Tolerance, Fast Path, State Machine Replication}
}

55 Search Results for "Ren, Ling"

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message