Publications by Jovan Komatovic

Optimal Byzantine Agreement with Little Cryptography

Distributed systems, which enable the efficient processing of large-scale data and complex tasks across multiple interconnected processes, offer significant advantages over single-machine systems. These include enhanced scalability, improved fault toleran ...

EPFL2025

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira

Byzantine agreement allows n processes to decide on a common value, in spite of arbitrary failures. The seminal Dolev-Reischuk bound states that any deterministic solution to Byzantine agreement exchanges Ω(n2) bits. In synchronous networks, with a known u ...

Society for Industrial and Applied Mathematics2025

Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement

Jovan Komatovic

It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of t < n/2 corruptions, bypassing the setup-free t < n/3 barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that ...

Springer Science and Business Media Deutschland GmbH2025

Repeated Agreement is Cheap! On Weak Accountability and Multishot Byzantine Agreement

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira

Byzantine Agreement (BA) allows 𝑛 processes to propose input values to reach consensus on a common, valid 𝐿 𝑜-bit value, even in the presence of up to 𝑡 < 𝑛 faulty processes that can deviate arbitrarily from the protocol. Although strategies like randomiza ...

ACM2025

Efficient Signature-Free Validated Agreement

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira

Byzantine agreement enables n processes to agree on a common L-bit value, despite up to t > 0 arbitrary failures. A long line of work has been dedicated to improving the bit complexity of Byzantine agreement in synchrony. This has culminated in COOL, an er ...

Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing2024

All Byzantine Agreement Problems Are Expensive

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Seth Gilbert, Manuel José Ribeiro Vidigueira

Byzantine agreement, arguably the most fundamental problem in distributed computing, operates among n processes, out of which t < n can exhibit arbitrary failures. The problem states that all correct (non-faulty) processes must eventually decide (terminati ...

ACM2024

DARE to Agree: Byzantine Agreement With Optimal Resilience and Adaptive Communication

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Seth Gilbert, Manuel José Ribeiro Vidigueira

Byzantine Agreement (BA) enables n processes to reach consensus on a common valid Lo-bit value, even in the presence of up to t < n faulty processes that can deviate arbitrarily from their prescribed protocol. Despite its significance, the optimal communic ...

ACM2024

Carbon: Scaling Trusted Payments with Untrusted Machines

Rachid Guerraoui, Jovan Komatovic, Gauthier Jérôme Timothée Voron, Martina Camaioni, Matteo Monti, Manuel José Ribeiro Vidigueira, Pierre-Louis Blaise Roman

This paper introduces Carbon, a high-throughput system enabling asynchronous (safe) and consensus-free (efficient) payments and votes within a dynamic set of clients. Carbon is operated by a dynamic set of validators that may be reconfigured asynchronously ...

2024

As easy as ABC: Optimal (A)ccountable (B)yzantine (C)onsensus is easy!

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert

In a non-synchronous system with n processes, no t(0)-resilient (deterministic or probabilistic) Byzantine consensus protocol can prevent a disagreement among correct processes if the number of faulty processes is > n - 2t(0). Therefore, the community defi ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2023

Byzantine consensus is Θ(n^2): the Dolev-Reischuk bound is tight even in partial synchrony!

Rachid Guerraoui, Jovan Komatovic, Manuel José Ribeiro Vidigueira, Pierre Philippe Civit, Vincent Gramoli, Seth Gilbert

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic (in the number of processes) communication complexity in the worst case: given a system with n processes and at most f < n/3 failures, any solution t ...

2023