Vincent Gramoli | EPFL Graph Search

Vincent Gramoli is an Associate Professor and the head of the Concurrent Systems Research Group at the University of Sydney, and a Visiting Professor at EPFL. Prior to this, he was affiliated with INRIA, University of Neuchatel and Cornell University. Vincent received his Habilitation from Sorbonne University. He is a Future Fellow of the Australian Research Council.

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 payment problems did not require this success, or any form of progress. We introduce a new specification formalism called Asynchronous Networks of Timed Automata to formalise such protocols. We present the first cross-chain payment protocol that ensures termination in a bounded amount of time and works correctly in the presence of clock drift. We then demonstrate that it is impossible to solve this problem without assuming synchrony, in the sense that each message is guaranteed to arrive within a known amount of time. Yet, we solve an eventually terminating weaker variant of this problem, where success is conditional on the patience of the participants, without assuming synchrony, and in the presence of Byzantine failures. We also discuss the relation with the recently defined cross-chain deals.

SPRINGER2023

Leaderless consensus

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

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 they tolerate unexpected delays and find practical applications in blockchains running over an open network like the Internet, their performance is highly dependent on the activity of a single participant. This paper asks whether, under eventual synchrony, it is possible to deterministically solve consensus without a leader. The fact that the weakest failure detector to solve consensus is one that also eventually elects a leader seems to indicate that the answer to the question is negative. We prove in this paper that the answer is actually positive.We first give a precise definition of the very notion of a leaderless algorithm. Then we present three indulgent leaderless consensus algorithms, each we believe interesting in its own right: (i) for shared memory, (ii) for message passing with omission failures and (iii) for message passing with Byzantine failures.Finally, we implement a Byzantine fault tolerant (BFT) state machine replication (SMR), that is leaderless. Our empirical results demonstrate that it is faster and more robust than HotStuff, the recent BFT SMR algorithm used in the Facebook Libra blockchain when deployed in a wide area network.(c) 2023 Elsevier Inc. All rights reserved.

ACADEMIC PRESS INC ELSEVIER SCIENCE2023

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

Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic

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 Byzantine consensus problem in non-synchronous systems: the problem of solving Byzantine consensus whenever possible (e.g., when the number of faulty processes does not exceed t0) and allowing correct processes to obtain proof of culpability of (at least) t0+1 faulty processes whenever correct processes disagree. We present four complementary contributions: 1) We introduce ABC: a simple yet efficient transformation of any Byzantine consensus protocol to an accountable one. ABC introduces an overhead of only two all-to-all communication rounds and O(n2) additional bits in executions with up to t0 faults (i.e., in the common case). 2) We define the accountability complexity, a complex-ity metric representing the number of accountability-specific messages that correct processes must send. Fur-thermore, we prove a tight lower bound. In particular, we show that any accountable Byzantine consensus protocol incurs cubic accountability complexity. Moreover, we illustrate that the bound is tight by applying the ABC transformation to any Byzantine consensus protocol. 3) We demonstrate that, when applied to an optimal Byzan-tine consensus protocol, ABC constructs an accountable Byzantine consensus protocol that is (1) optimal with respect to the communication complexity in solving consensus whenever consensus is solvable, and (2) op-timal with respect to the accountability complexity in obtaining accountability whenever disagreement occurs. 4) We generalize ABC to other distributed computing prob-lems besides the classic consensus problem. We charac-terize a class of agreement tasks, including reliable and consistent broadcast [5], that ABC renders accountable.

IEEE2022

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

Seth Gilbert, Vincent Gramoli, Rachid Guerraoui, Jovan Komatovic

IEEE2022