Publications de Vincent Gramoli

Blockchain Double Spending with Low Mining Power and Network Delays

Traditional blockchain systems offer a secure way of tracking the ownership of digital assets as long as the attacker does not control a large portion of the overall computational or mining power. They typically require participants to generate a proof-of- ...

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

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

Leaderless consensus

Rachid Guerraoui, Gauthier Jérôme Timothée Voron, Vincent Gramoli, Mihail Igor Zablotchi, Karolos Antoniadis, Antoine Philippe Matthieu Desjardins

Classic synchronous consensus algorithms are leaderless in that processes exchange proposals, choose the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are typically leader-based. Although t ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2023

DIABLO: A Benchmark Suite for Blockchains

Rachid Guerraoui, Gauthier Jérôme Timothée Voron, Vincent Gramoli, Andrei Lebedev

With the recent advent of blockchains, we have witnessed a plethora of blockchain proposals. These proposals range from using work to using time, storage or stake in order to select blocks to be appended to the chain. As a drawback it makes it difficult fo ...

ASSOC COMPUTING MACHINERY2023

Cross-chain payment protocols with success guarantees

Vincent Gramoli

In this paper, we consider the problem of cross-chain payment whereby customers of different escrows-implemented by a bank or a blockchain smart contract-successfully transfer digital assets without trusting each other. Prior to this work, cross-chain paym ...

SPRINGER2023

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

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

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

Crime and Punishment in Distributed Byzantine Decision Tasks

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

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

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

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

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

Federated Learning Over Wireless Networks: Convergence Analysis and Resource Allocation

Vincent Gramoli

There is an increasing interest in a fast-growing machine learning technique called Federated Learning (FL), in which the model training is distributed over mobile user equipment (UEs), exploiting UEs' local computation and training data. Despite its advan ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2021