Publications by Pierre Philippe Civit

Partial Synchrony for Free: New Upper Bounds for Byzantine Agreement

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

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, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

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, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

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, Seth Gilbert, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

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, Seth Gilbert, Manuel José Ribeiro Vidigueira, Jovan Komatovic, Pierre Philippe Civit

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

On the Validity of Consensus

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

The Byzantine consensus problem involves.. processes, out of which t < n could be faulty and behave arbitrarily. Three properties characterize consensus: (1) termination, requiring correct (nonfaulty) processes to eventually reach a decision, (2) agreement ...

Assoc Computing Machinery2023

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

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

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

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

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

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

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

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

It is known that the agreement property of the Byzantine consensus problem among n processes can be violated in a non-synchronous system if the number of faulty processes exceeds t0 = ┌n/3┐ − 1 [10], [19]. In this paper, we investigate the accountable Byza ...

IEEE2022

Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony!

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

The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether ...

Dagstuhl Publishing2022

Crime and Punishment in Distributed Byzantine Decision Tasks

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

A decision task is a distributed input-output problem in which each process starts with its input value and eventually produces its output value. Examples of such decision tasks are broad and range from consensus to reliable broadcast to lattice agreement. ...

IEEE COMPUTER SOC2022