Publications de Manuel José Ribeiro Vidigueira

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

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

The Tight Cost of Byzantine Agreement

Manuel José Ribeiro Vidigueira

Distributed computer systems have become a fundamental part of our lives. These systems power so many critical functions of our society that it is hard to imagine the consequences if they were to collapse. However, many of these systems are just a single p ...

EPFL2025

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

Rapidly verifiable aggregate signatures

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

A method for aggregating digital signatures comprises the following steps carried out by a signature aggregator: receiving first data packages from signers, each first data package comprising a signer identifier, a payload, and a payload signature; verifyi ...

2024

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

Chop Chop: Byzantine Atomic Broadcast to the Network Limit

Rachid Guerraoui, Gauthier Jérôme Timothée Voron, Martina Camaioni, Matteo Monti, Manuel José Ribeiro Vidigueira

At the heart of state machine replication, the celebrated technique enabling decentralized and secure universal computation, lies Atomic Broadcast, a fundamental communication primitive that orders, authenticates, and deduplicates messages. This paper pres ...

USENIX2024

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

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