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

Planetary-Scale Byzantine Fault Tolerance

The scale and pervasiveness of the Internet make it a pillar of planetary communication, industry and economy, as well as a fundamental medium for public discourse and democratic engagement. In stark contrast with the Internet's decentralized infrastructur ...

EPFL2024

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

Building Strongly-Consistent Systems Resilient to Failures, Partitions, and Slowdowns

Cristina Basescu

Distributed systems designers typically strive to improve performance and preserve availability despite failures or attacks; but, when strong consistency is also needed, they encounter fundamental limitations. The bottleneck is in replica coordination, whi ...

EPFL2023

Leaderless consensus

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

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

Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search

Rachid Guerraoui, Andrei Kucharavy, Matteo Monti

Modern machine learning (ML) models are capable of impressive performances. However, their prowess is not due only to the improvements in their architecture and training algorithms but also to a drastic increase in computational power used to train them.|S ...

Assoc Computing Machinery2023

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

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

Toward Mobile Distributed Ledgers

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos, Anurag Jain

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on Device-to-Device (D2D) ecosystems (e.g., crowdsensing). Sophisticated applications, like cryptocurrencies, need distr ...

IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC2022

Data-driven and Safe Networked Control with Applications to Microgrids

Mustafa Sahin Turan

Today, automatic control is integrated into a wide spectrum of real-world systems such as electrical grids and transportation networks. Many of these systems comprise numerous interconnected agents, perform safety-critical operations, or generate large amo ...

EPFL2022

Asynchronous distributed coordination and consensus with threshold logical clocks

Bryan Alexander Ford

Consensus protocols for asynchronous networks are usually complex and inefficient, leading practical systems to rely on synchronous protocols. The invention proposes an approach to simplify asynchronous consensus by building it atop a novel threshold logic ...

2021

Leaderless Consensus

Rachid Guerraoui, Vincent Gramoli, Mihail Igor Zablotchi, Karolos Antoniadis, Antoine Philippe Matthieu Desjardins

Classical synchronous consensus algorithms are leaderless: processes exchange their proposals, retain the maximum value and decide when they see the same choice across a couple of rounds. Indulgent consensus algorithms are more robust in that they only req ...

IEEE COMPUTER SOC2021

Rational Agreement in the Presence of Crash Faults

Vincent Gramoli, Alejandro Ranchal Pedrosa

Blockchain systems need to solve consensus despite the presence of rational users and failures. The notion of (k, t)-robustness is key to derive impossibility results with k rational players and t faulty players. However, these t faulty players are always ...

IEEE2021

Dynamic Byzantine Reliable Broadcast

Rachid Guerraoui, Dragos-Adrian Seredinschi, Jovan Komatovic, Andrei Tonkikh

Reliable broadcast is a communication primitive guaranteeing, intuitively, that all processes in a distributed system deliver the same set of messages. The reason why this primitive is appealing is twofold: (i) we can implement it deterministically in a co ...

Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik2021

The Performance of Byzantine Fault Tolerant Blockchains

Vincent Gramoli

Blockchains have captured the attention of many, resulting in an abundance of new systems available for use. However, selecting an appropriate blockchain for an application is challenging due to the lack of comparative information discussing core metrics s ...

IEEE2020

Mneme: A Mobile Distributed Ledger

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos

Advances in mobile computing have paved the way for new types of distributed applications that can be executed solely by mobile devices on device-to-device (D2D) ecosystems (e.g., crowdsensing). More sophisticated applications, like cryptocurrencies, need ...

IEEE2020

Genuinely Distributed Byzantine Machine Learning

Rachid Guerraoui, El Mahdi El Mhamdi, Le Nguyen Hoang, Sébastien Louis Alexandre Rouault, Arsany Hany Abdelmessih Guirguis

Machine Learning (ML) solutions are nowadays distributed, according to the so-called server/worker architecture. One server holds the model parameters while several workers train the model. Clearly, such architecture is prone to various types of component ...

Association for Computing Machinery2020

The Hidden Complexity of Distributed Systems

Karolos Antoniadis

The field of distributed computing has a long history, of more than fifty years. During that time, our understanding of the field has improved immensely and a certain body of folklore beliefs has formed. However, such folklore beliefs are not necessarily a ...

EPFL2020

Private and Secure Distributed Learning

Georgios Damaskinos

The ever-growing number of edge devices (e.g., smartphones) and the exploding volume of sensitive data they produce, call for distributed machine learning techniques that are privacy-preserving. Given the increasing computing capabilities of modern edge de ...

EPFL2020

Scalable Byzantine Reliable Broadcast

Rachid Guerraoui, Matej Pavlovic, Dragos-Adrian Seredinschi, Matteo Monti

Byzantine reliable broadcast is a powerful primitive that allows a set of processes to agree on a message from a designated sender, even if some processes (including the sender) are Byzantine. Existing broadcast protocols for this setting scale poorly, as ...

Schloss Dagstuhl--Leibniz-Zentrum fer Informatik2019

Scaling Byzantine Fault Tolerance

Matej Pavlovic

Online services are becoming more and more ubiquitous and keep growing in scale. At the same time, they are required to be highly available, secure, energy-efficient, and to achieve high performance. To ensure these (and many other) properties, replication ...

EPFL2019