17 Search Results for "Seredinschi, Dragos-Adrian"

Document
DOI: 10.4230/OASIcs.NINeS.2026.3
Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems

Authors: Cristina Băsescu, Georgia Fragkouli, Enis Ceyhun Alp, Michael F. Nowlan, Jose M. Faleiro, Gaylor Bosson, Kelong Cong, Pierluca Borsò-Tan, Vero Estrada-Galiñanes, and Bryan Ford

Published in: OASIcs, Volume 139, 1st New Ideas in Networked Systems (NINeS 2026)

Abstract
Globalized computing infrastructures offer the convenience and elasticity of globally managed objects and services, but lack the resilience to distant failures that localized infrastructures such as private clouds provide. Providing both global management and resilience to distant failures, however, poses a fundamental problem for configuration services: How to discover a possibly migratory, strongly-consistent service/object in a globalized infrastructure without dependencies on globalized state? Limix is the first metadata configuration service that addresses this problem. With Limix, global strongly-consistent data-plane services and objects are insulated from remote gray failures by ensuring that the definitive, strongly-consistent metadata for any object is always confined to the same region as the object itself. Limix guarantees availability bounds: any user can continue accessing any strongly consistent object that matters to the user located at distance Δ away, insulated from failures outside a small multiple of Δ. We built a Limix metadata service based on the key-value interface of CockroachDB. Our experiments on Internet-like networks and on AWS, using realistic trace-driven workloads, show that Limix enables global management and significantly improves availability over the state-of-the-art.
Cite as

Cristina Băsescu, Georgia Fragkouli, Enis Ceyhun Alp, Michael F. Nowlan, Jose M. Faleiro, Gaylor Bosson, Kelong Cong, Pierluca Borsò-Tan, Vero Estrada-Galiñanes, and Bryan Ford. Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems. In 1st New Ideas in Networked Systems (NINeS 2026). Open Access Series in Informatics (OASIcs), Volume 139, pp. 3:1-3:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{basescu_et_al:OASIcs.NINeS.2026.3,
  author =	{B\u{a}sescu, Cristina and Fragkouli, Georgia and Alp, Enis Ceyhun and Nowlan, Michael F. and Faleiro, Jose M. and Bosson, Gaylor and Cong, Kelong and Bors\`{o}-Tan, Pierluca and Estrada-Gali\~{n}anes, Vero and Ford, Bryan},
  title =	{{Limix: Limiting Lamport Exposure to Distant Failures in Globally-Managed Distributed Systems}},
  booktitle =	{1st New Ideas in Networked Systems (NINeS 2026)},
  pages =	{3:1--3:29},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-414-7},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{139},
  editor =	{Argyraki, Katerina and Panda, Aurojit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.NINeS.2026.3},
  URN =		{urn:nbn:de:0030-drops-255880},
  doi =		{10.4230/OASIcs.NINeS.2026.3},
  annote =	{Keywords: Distributed systems, Availability, Fault tolerance, Strong-consistency, Coordination systems, Lamport exposure}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2025.9
Contention-Aware Cooperation

Authors: Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani

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

Abstract
As shown by Reliable Broadcast and Consensus, cooperation among a set of independent computing entities (sequential processes) is crucial in fault-tolerant distributed computing. Considering n-process asynchronous message-passing systems where some processes may be Byzantine, this paper introduces a novel cooperation abstraction, Contention-Aware Cooperation (CAC). While Reliable Broadcast is a one-to-n cooperation abstraction and Consensus is an n-to-n cooperation abstraction, CAC is a d-to-n cooperation abstraction where d (1 ≤ d ≤ n) varies with each run and remains unknown to the processes. Correct processes accept the same set of 𝓁 pairs ⟨ v,i ⟩ (v is the value proposed by p_i) from the d proposer processes, where 1 ≤ 𝓁 ≤ d and (as d) 𝓁 remains unknown to the processes (except in specific cases). Those 𝓁 values are accepted one at a time, potentially in different orders at each process. In addition, CAC provides each process with an imperfect oracle that provides insights into the values that they may accept in the future. Interestingly, the CAC abstraction is particularly efficient in favorable circumstances, when the oracle becomes accurate, which processes can detect. To illustrate its practical utility, the paper details two applications leveraging CAC: a fast consensus implementation optimized for low contention (named Cascading Consensus), and a novel naming problem that can be solved under full asynchrony. All algorithms presented require signatures.
Cite as

Timothé Albouy, Davide Frey, Mathieu Gestin, Michel Raynal, and François Taïani. Contention-Aware Cooperation. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 9:1-9:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2025.9,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gestin, Mathieu and Raynal, Michel and Ta\"{i}ani, Fran\c{c}ois},
  title =	{{Contention-Aware Cooperation}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{9:1--9:19},
  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.9},
  URN =		{urn:nbn:de:0030-drops-251823},
  doi =		{10.4230/LIPIcs.OPODIS.2025.9},
  annote =	{Keywords: Agreement, Asynchronous message-passing system, Byzantine processes, Conflict detection, Consensus, Cooperation abstraction, Distributed computing, Fault tolerance, Optimistically terminating consensus, Short-naming}
}
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.33
Resolving Conflicts with Grace: Dynamically Concurrent Universality

Authors: Petr Kuznetsov and Nathan Josia Schrodt

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

Abstract
Synchronization is the major obstacle to scalability in distributed computing. Concurrent operations on the shared data engage in synchronization when they encounter a conflict, i.e., their effects depend on the order in which they are applied. Ideally, one would like to detect conflicts in a dynamic manner, i.e., adjusting to the current system state. Indeed, it is very common that two concurrent operations conflict only in some rarely occurring states. In this paper, we define the notion of dynamic concurrency: an operation employs strong synchronization primitives only if it has to arbitrate with concurrent operations, given the current system state. We then present a dynamically concurrent universal construction.
Cite as

Petr Kuznetsov and Nathan Josia Schrodt. Resolving Conflicts with Grace: Dynamically Concurrent Universality. In 29th International Conference on Principles of Distributed Systems (OPODIS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 361, pp. 33:1-33:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{kuznetsov_et_al:LIPIcs.OPODIS.2025.33,
  author =	{Kuznetsov, Petr and Schrodt, Nathan Josia},
  title =	{{Resolving Conflicts with Grace: Dynamically Concurrent Universality}},
  booktitle =	{29th International Conference on Principles of Distributed Systems (OPODIS 2025)},
  pages =	{33:1--33:29},
  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.33},
  URN =		{urn:nbn:de:0030-drops-252068},
  doi =		{10.4230/LIPIcs.OPODIS.2025.33},
  annote =	{Keywords: Universal Construction, Consensus, Dynamic Concurrency}
}
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.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.23
Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection

Authors: Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo

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

Abstract
Payment channel networks (PCNs) are a promising technology that alleviates blockchain scalability by shifting the transaction load from the blockchain to the PCN. Nevertheless, the network topology has to be carefully designed to maximise the transaction throughput in PCNs. Additionally, users in PCNs also have to make optimal decisions on which transactions to forward and which to reject to prolong the lifetime of their channels. In this work, we consider an input sequence of transactions over p parties. Each transaction consists of a transaction size, source, and target, and can be either accepted or rejected (entailing a cost). The goal is to design a PCN topology among the p cooperating parties, along with the channel capacities, and then output a decision for each transaction in the sequence to minimise the cost of creating and augmenting channels, as well as the cost of rejecting transactions. Our main contribution is an 𝒪(p) approximation algorithm for the problem with p parties. We further show that with some assumptions on the distribution of transactions, we can reduce the approximation ratio to 𝒪(√p). We complement our theoretical analysis with an empirical study of our assumptions and approach in the context of the Lightning Network.
Cite as

Krishnendu Chatterjee, Jan Matyáš Křišťan, Stefan Schmid, Jakub Svoboda, and Michelle Yeo. Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection. In 39th International Symposium on Distributed Computing (DISC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 356, pp. 23:1-23:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chatterjee_et_al:LIPIcs.DISC.2025.23,
  author =	{Chatterjee, Krishnendu and K\v{r}i\v{s}\v{t}an, Jan Maty\'{a}\v{s} and Schmid, Stefan and Svoboda, Jakub and Yeo, Michelle},
  title =	{{Boosting Payment Channel Network Liquidity with Topology Optimization and Transaction Selection}},
  booktitle =	{39th International Symposium on Distributed Computing (DISC 2025)},
  pages =	{23:1--23: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.23},
  URN =		{urn:nbn:de:0030-drops-248402},
  doi =		{10.4230/LIPIcs.DISC.2025.23},
  annote =	{Keywords: Blockchains, Cryptocurrencies, Payment Channel Networks, Throughput, Optimisation, Graph Algorithms, Approximation Algorithms}
}
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}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.3
Fast, Private and Regulated Payments in Asynchronous Networks

Authors: Maxence Brugeres, Victor Languille, Petr Kuznetsov, and Hamza Zarfaoui

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
We propose a decentralized asset-transfer system that enjoys full privacy: no party can learn the details of a transaction, except for its issuer and its recipient. Furthermore, the recipient is not aware of the sender’s identity. Our system does not rely on consensus or synchrony assumptions, and therefore, it is responsive, since it runs at the actual network speed. Under the hood, every transaction creates a consumable coin equipped with a non-interactive zero-knowledge proof (NIZK) that confirms that the issuer has sufficient funds without revealing any information about her identity, the recipient’s identity, or the payment amount. Moreover, we equip our system with a regulatory enforcement mechanism that can be used to regulate transfer limits or restrict specific addresses from sending or receiving funds, while preserving the system’s privacy guarantees. Finally, we report on PaxPay, our implementation of Fully Private Asset Transfer (FPAT) that uses the Gnark library for the NIZKs. In our benchmark, PaxPay exhibits better performance than earlier proposals that either ensure only partial privacy, require some kind of network synchrony or do not implement regulation features. Our system thus reconciles privacy, responsiveness, regulation enforcement and performance.
Cite as

Maxence Brugeres, Victor Languille, Petr Kuznetsov, and Hamza Zarfaoui. Fast, Private and Regulated Payments in Asynchronous Networks. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 3:1-3:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{brugeres_et_al:LIPIcs.AFT.2025.3,
  author =	{Brugeres, Maxence and Languille, Victor and Kuznetsov, Petr and Zarfaoui, Hamza},
  title =	{{Fast, Private and Regulated Payments in Asynchronous Networks}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{3:1--3:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.3},
  URN =		{urn:nbn:de:0030-drops-247227},
  doi =		{10.4230/LIPIcs.AFT.2025.3},
  annote =	{Keywords: Anonymous, Asset Transfer, Asynchronous System, BFT, CBDC, NIZK, Payment System, Privacy, Regulation, Scalability, zk-SNARK}
}
Document
DOI: 10.4230/LIPIcs.AFT.2025.18
From Permissioned to Proof-of-Stake Consensus

Authors: Jovan Komatovic, Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Ertem Nusret Tas

Published in: LIPIcs, Volume 354, 7th Conference on Advances in Financial Technologies (AFT 2025)

Abstract
This paper presents the first generic compiler that transforms any permissioned consensus protocol into a proof-of-stake permissionless consensus protocol. For each of the following properties, if the initial permissioned protocol satisfies that property in the partially synchronous setting, the consequent proof-of-stake protocol also satisfies that property in the partially synchronous and quasi-permissionless setting (with the same fault-tolerance): consistency; liveness; optimistic responsiveness; every composable log-specific property; and message complexity of a given order. Moreover, our transformation ensures that the output protocol satisfies accountability (identifying culprits in the event of a consistency violation), whether or not the original permissioned protocol satisfied it.
Cite as

Jovan Komatovic, Andrew Lewis-Pye, Joachim Neu, Tim Roughgarden, and Ertem Nusret Tas. From Permissioned to Proof-of-Stake Consensus. In 7th Conference on Advances in Financial Technologies (AFT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 354, pp. 18:1-18:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{komatovic_et_al:LIPIcs.AFT.2025.18,
  author =	{Komatovic, Jovan and Lewis-Pye, Andrew and Neu, Joachim and Roughgarden, Tim and Tas, Ertem Nusret},
  title =	{{From Permissioned to Proof-of-Stake Consensus}},
  booktitle =	{7th Conference on Advances in Financial Technologies (AFT 2025)},
  pages =	{18:1--18:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-400-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{354},
  editor =	{Avarikioti, Zeta and Christin, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AFT.2025.18},
  URN =		{urn:nbn:de:0030-drops-247373},
  doi =		{10.4230/LIPIcs.AFT.2025.18},
  annote =	{Keywords: Permissioned Consensus, Proof-of-Stake, generic Compiler, Blockchain}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.14
Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary

Authors: Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas

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

Abstract
We address the problem of Reliable Broadcast in asynchronous message-passing systems with n nodes, of which up to t are malicious (faulty), in addition to a message adversary that can drop some of the messages sent by correct (non-faulty) nodes. We present a Message-Adversary-Tolerant Byzantine Reliable Broadcast (MBRB) algorithm that communicates O(|m|+nκ) bits per node, where |m| represents the length of the application message and κ = Ω(log n) is a security parameter. This communication complexity is optimal up to the parameter κ. This significantly improves upon the state-of-the-art MBRB solution (Albouy, Frey, Raynal, and Taïani, TCS 2023), which incurs communication of O(n|m|+n²κ) bits per node. Our solution sends at most 4n² messages overall, which is asymptotically optimal. Reduced communication is achieved by employing coding techniques that replace the need for all nodes to (re-)broadcast the entire application message m. Instead, nodes forward authenticated fragments of the encoding of m using an erasure-correcting code. Under the cryptographic assumptions of threshold signatures and vector commitments, and assuming n > 3t+2d, where the adversary drops at most d messages per broadcast, our algorithm allows at least 𝓁 = n - t - (1 + ε)d (for any arbitrarily low ε > 0) correct nodes to reconstruct m, despite missing fragments caused by the malicious nodes and the message adversary.
Cite as

Timothé Albouy, Davide Frey, Ran Gelles, Carmit Hazay, Michel Raynal, Elad Michael Schiller, François Taïani, and Vassilis Zikas. Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 14:1-14:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{albouy_et_al:LIPIcs.OPODIS.2024.14,
  author =	{Albouy, Timoth\'{e} and Frey, Davide and Gelles, Ran and Hazay, Carmit and Raynal, Michel and Schiller, Elad Michael and Ta\"{i}ani, Fran\c{c}ois and Zikas, Vassilis},
  title =	{{Near-Optimal Communication Byzantine Reliable Broadcast Under a Message Adversary}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{14:1--14:29},
  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.14},
  URN =		{urn:nbn:de:0030-drops-225503},
  doi =		{10.4230/LIPIcs.OPODIS.2024.14},
  annote =	{Keywords: Asynchronous message-passing, Byzantine fault-tolerance, Message adversary, Reliable broadcast, Erasure-correction codes, \{Threshold\} signatures, \{Vector commitments\}}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2024.16
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
DOI: 10.4230/LIPIcs.OPODIS.2024.31
Dynamic Probabilistic Reliable Broadcast

Authors: João Paulo Bezerra, Veronika Anikina, Petr Kuznetsov, Liron Schiff, and Stefan Schmid

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

Abstract
Byzantine reliable broadcast is a fundamental primitive in distributed systems that allows a set of processes to agree on a message broadcast by a dedicated process, even when some of them are malicious (Byzantine). It guarantees that no two correct processes deliver different messages, and if a message is delivered by a correct process, every correct process eventually delivers one. Byzantine reliable broadcast protocols are known to scale poorly, as they require Ω(n²) message exchanges, where n is the number of system members. The quadratic cost can be explained by the inherent need for every process to relay a message to every other process. In this paper, we explore ways to overcome this limitation by casting the problem to the probabilistic setting. We propose a solution in which every broadcast message is validated by a small set of witnesses, which allows us to maintain low latency and small communication complexity. In order to tolerate the slow adaptive adversary, we dynamically select the witnesses through a novel stream-local hash function: given a stream of inputs, it generates a stream of output hashed values that adapts to small deviations of the inputs. Our performance analysis shows that the proposed solution exhibits significant scalability gains over state-of-the-art protocols.
Cite as

João Paulo Bezerra, Veronika Anikina, Petr Kuznetsov, Liron Schiff, and Stefan Schmid. Dynamic Probabilistic Reliable Broadcast. In 28th International Conference on Principles of Distributed Systems (OPODIS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 324, pp. 31:1-31:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{bezerra_et_al:LIPIcs.OPODIS.2024.31,
  author =	{Bezerra, Jo\~{a}o Paulo and Anikina, Veronika and Kuznetsov, Petr and Schiff, Liron and Schmid, Stefan},
  title =	{{Dynamic Probabilistic Reliable Broadcast}},
  booktitle =	{28th International Conference on Principles of Distributed Systems (OPODIS 2024)},
  pages =	{31:1--31:30},
  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.31},
  URN =		{urn:nbn:de:0030-drops-225679},
  doi =		{10.4230/LIPIcs.OPODIS.2024.31},
  annote =	{Keywords: Reliable broadcast, probabilistic algorithms, witness sets, stream-local hashing, cryptocurrencies, accountability}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.23
Dynamic Byzantine Reliable Broadcast

Authors: Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh

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

Abstract
Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a completely asynchronous environment, unlike stronger primitives like consensus and total-order broadcast, and yet (ii) reliable broadcast is powerful enough to implement important applications like payment systems. The problem we tackle in this paper is that of dynamic reliable broadcast, i.e., enabling processes to join or leave the system. This property is desirable for long-lived applications (aiming to be highly available), yet has been precluded in previous asynchronous reliable broadcast protocols. We study this property in a general adversarial (i.e., Byzantine) environment. We introduce the first specification of a dynamic Byzantine reliable broadcast (dbrb) primitive that is amenable to an asynchronous implementation. We then present an algorithm implementing this specification in an asynchronous network. Our dbrb algorithm ensures that if any correct process in the system broadcasts a message, then every correct process delivers that message unless it leaves the system. Moreover, if a correct process delivers a message, then every correct process that has not expressed its will to leave the system delivers that message. We assume that more than 2/3 of processes in the system are correct at all times, which is tight in our context. We also show that if only one process in the system can fail - and it can fail only by crashing - then it is impossible to implement a stronger primitive, ensuring that if any correct process in the system broadcasts or delivers a message, then every correct process in the system delivers that message - including those that leave.
Cite as

Rachid Guerraoui, Jovan Komatovic, Petr Kuznetsov, Yvonne-Anne Pignolet, Dragos-Adrian Seredinschi, and Andrei Tonkikh. Dynamic Byzantine Reliable Broadcast. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{guerraoui_et_al:LIPIcs.OPODIS.2020.23,
  author =	{Guerraoui, Rachid and Komatovic, Jovan and Kuznetsov, Petr and Pignolet, Yvonne-Anne and Seredinschi, Dragos-Adrian and Tonkikh, Andrei},
  title =	{{Dynamic Byzantine Reliable Broadcast}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{23:1--23:18},
  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.23},
  URN =		{urn:nbn:de:0030-drops-135087},
  doi =		{10.4230/LIPIcs.OPODIS.2020.23},
  annote =	{Keywords: Byzantine reliable broadcast, deterministic distributed algorithms, dynamic distributed systems}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.23
Making Byzantine Consensus Live

Authors: Manuel Bravo, Gregory Chockler, and Alexey Gotsman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
Partially synchronous Byzantine consensus protocols typically structure their execution into a sequence of views, each with a designated leader process. The key to guaranteeing liveness in these protocols is to ensure that all correct processes eventually overlap in a view with a correct leader for long enough to reach a decision. We propose a simple view synchronizer abstraction that encapsulates the corresponding functionality for Byzantine consensus protocols, thus simplifying their design. We present a formal specification of a view synchronizer and its implementation under partial synchrony, which runs in bounded space despite tolerating message loss during asynchronous periods. We show that our synchronizer specification is strong enough to guarantee liveness for single-shot versions of several well-known Byzantine consensus protocols, including HotStuff, Tendermint, PBFT and SBFT. We furthermore give precise latency bounds for these protocols when using our synchronizer. By factoring out the functionality of view synchronization we are able to specify and analyze the protocols in a uniform framework, which allows comparing them and highlights trade-offs.
Cite as

Manuel Bravo, Gregory Chockler, and Alexey Gotsman. Making Byzantine Consensus Live. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bravo_et_al:LIPIcs.DISC.2020.23,
  author =	{Bravo, Manuel and Chockler, Gregory and Gotsman, Alexey},
  title =	{{Making Byzantine Consensus Live}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.23},
  URN =		{urn:nbn:de:0030-drops-131013},
  doi =		{10.4230/LIPIcs.DISC.2020.23},
  annote =	{Keywords: Byzantine consensus, blockchain, partial synchrony, liveness}
}
  • Refine by Type
  • 17 Document/PDF
  • 13 Document/HTML

  • Refine by Publication Year
  • 5 2026
  • 8 2025
  • 1 2021
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 5 Kuznetsov, Petr
  • 3 Guerraoui, Rachid
  • 3 Seredinschi, Dragos-Adrian
  • 2 Albouy, Timothé
  • 2 Frey, Davide
  • Show More...

  • Refine by Series/Journal
  • 16 LIPIcs
  • 1 OASIcs

  • Refine by Classification
  • 9 Theory of computation → Distributed algorithms
  • 3 Computer systems organization → Dependable and fault-tolerant systems and networks
  • 3 Security and privacy → Distributed systems security
  • 2 Computer systems organization → Distributed architectures
  • 2 Computer systems organization → Fault-tolerant network topologies
  • Show More...

  • Refine by Keyword
  • 4 Consensus
  • 2 Blockchain
  • 2 Byzantine reliable broadcast
  • 2 Distributed computing
  • 2 Fault tolerance
  • 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
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact