Publications related to Generic construction of consensus algorithms for benign and Byzantine faults

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

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

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

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

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

Impact of Redundancy on Resilience in Distributed Optimization and Learning

Shuo Liu, Nirupam Gupta

This paper considers the problem of resilient distributed optimization and stochastic learning in a server-based architecture. The system comprises a server and multiple agents, where each agent has its own local cost function. The agents collaborate with ...

Assoc Computing Machinery2023

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

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

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

AGGREGATHOR: Byzantine Machine Learning via Robust Gradient Aggregation

Rachid Guerraoui, El Mahdi El Mhamdi, Georgios Damaskinos, Sébastien Louis Alexandre Rouault, Arsany Hany Abdelmessih Guirguis

We present AGGREGATHOR, a framework that implements state-of-the-art robust (Byzantine-resilient) distributed stochastic gradient descent. Following the standard parameter server model, we assume that a minority of worker machines can be controlled by an a ...

2019

The Impact of RDMA on Agreement

Rachid Guerraoui, Mihail Igor Zablotchi, Naama Ben David

Remote Direct Memory Access (RDMA) is becoming widely available in data centers. This technology allows a process to directly read and write the memory of a remote host, with a mechanism to control access permissions. In this paper, we study the fundamenta ...

2019

Asynchronous Byzantine Machine Learning (the case of SGD)

Rachid Guerraoui, El Mahdi El Mhamdi, Rhicheek Patra, Mahsa Taziki, Georgios Damaskinos

Asynchronous distributed machine learning solutions have proven very effective so far, but always assuming perfectly functioning workers. In practice, some of the workers can however exhibit Byzantine behavior, caused by hardware failures, software bugs, c ...

2018

Enhancing Bitcoin Security and Performance with Strong Consistency via Collective Signing

Linus Gasser, Nicolas Gailly, Bryan Alexander Ford, Ismail Khoffi, Philipp Svetolik Jovanovic

While showing great promise, Bitcoin requires users to wait tens of minutes for transactions to commit, and even then, offering only probabilistic guarantees. This paper introduces ByzCoin, a novel Byzantine consensus protocol that leverages scalable colle ...

USENIX Association2016

Poster: LocalCoin: An Ad-hoc Payment Scheme for Areas with High Connectivity

Boi Faltings, Sujit Prakash Gujar, Dimitrios Chatzopoulos

The popularity of digital currencies, especially cryptocurrencies, has been continuously growing since the appearance of Bitcoin. Bitcoin is a peer-to-peer (P2P) cryptocurrency protocol enabling transactions between individuals without the need of a truste ...

Assoc Computing Machinery2016

Byzantine Fireflies

Rachid Guerraoui, Alexandre David Olivier Maurer

This paper addresses the problem of synchronous beeping, as addressed by swarms of fireflies. We present Byzantine-resilient algorithms ensuring that the correct processes eventually beep synchronously despite a subset of nodes beeping asynchronously. We a ...

2015

Abstractions for Solving Consensus and Related Problems with Byzantine Faults

Zarko Milosevic

We become increasingly dependent on online services; therefore, their availability and correct behavior become increasingly important. Software replication is a popular technique for ensuring that computer systems continue to provide a correct service even ...

EPFL2013

Byzantine Agreement with Homonyms

Rachid Guerraoui, Eric Ruppert, Anne-Marie Kermarrec

So far, the distributed computing community has either assumed that all the processes of a distributed system have distinct identifiers or, more rarely, that the processes are anonymous and have no identifiers. These are two extremes of the same general mo ...

Springer2013