Publications related to Planetary-Scale Byzantine Fault Tolerance

Related publications (32)

Fly-Swat or Cannon? Cost-Effective Language Model Choice via Meta-Modeling

Robert West, Maxime Jean Julien Peyrard, Marija Sakota

Generative language models (LMs) have become omnipresent across data science. For a wide variety of tasks, inputs can be phrased as natural language prompts for an LM, from whose output the solution can then be extracted. LM performance has consistently be ...

Assoc Computing Machinery2024

Quantifying the Unknown: Data-Driven Approaches and Applications in Energy Systems

Paul Scharnhorst

In light of the challenges posed by climate change and the goals of the Paris Agreement, electricity generation is shifting to a more renewable and decentralized pattern, while the operation of systems like buildings is increasingly electrified. This calls ...

EPFL2024

On the Theory and Practice of Modern Secure Messaging

Daniel Patrick Collins

Billions of people now have conversations daily over the Internet. A large portion of this communication takes place via secure messaging protocols that offer "end-to-end encryption'" guarantees and resilience to compromise like the widely-used Double Ratc ...

EPFL2024

Towards General-Purpose Decentralized Computing with Permissionless Extensibility

Enis Ceyhun Alp

Smart contracts have emerged as the most promising foundations for applications of the blockchain technology. Even though smart contracts are expected to serve as the backbone of the next-generation web, they have several limitations that hinder their wide ...

EPFL2024

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

Rachid Guerraoui, Vincent Gramoli, Seth Gilbert, Jovan Komatovic, Manuel José Ribeiro Vidigueira, 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

Hypergraph-Based Fast Distributed AC Power Flow Optimization

Colin Neil Jones, Yuning Jiang, Yingzhao Lian

This paper presents a novel distributed approach for solving AC power flow (PF) problems. The optimization problem is reformulated into a distributed form using a communication structure corresponding to a hypergraph, by which complex relationships between ...

IEEE2023

Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search

Rachid Guerraoui, Matteo Monti, Andrei Kucharavy

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

Impact of Redundancy on Resilience in Distributed Optimization and Learning

Nirupam Gupta, Shuo Liu

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

Reliable Microsecond-Scale Distributed Computing

Athanasios Xygkis

The landscape of computing is changing, thanks to the advent of modern networking equipment that allows machines to exchange information in as little as one microsecond. Such advancement has enabled microsecond-scale distributed computing, where entire dis ...

EPFL2023

Byzantine Fault-Tolerance in Federated Local SGD Under 2f-Redundancy

Nirupam Gupta

In this article, we study the problem of Byzantine fault-tolerance in a federated optimization setting, where there is a group of agents communicating with a centralized coordinator. We allow up to

f

Byzantine-faulty agents, which may not follow a prescr ...

Ieee-Inst Electrical Electronics Engineers Inc2023

Leaderless consensus

Rachid Guerraoui, Vincent Gramoli, Mihail Igor Zablotchi, Karolos Antoniadis, 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

Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

Mika Tapani Göös

We prove an N2-o(1) lower bound on the randomized communication complexity of finding an epsilon-approximate Nash equilibrium (for constant epsilon > 0) in a two-player N x N game. ...

Siam Publications2023

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

Rachid Guerraoui, Vincent Gramoli, Seth Gilbert, 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

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

Byzantine Machine Learning: A Primer

Rachid Guerraoui, Nirupam Gupta, Rafaël Benjamin Pinot

The problem of Byzantine resilience in distributed machine learning, a.k.a., Byzantine machine learning, consists in designing distributed algorithms that can train an accurate model despite the presence of Byzantine nodes, i.e., nodes with corrupt data or ...

2023

On the Validity of Consensus

Rachid Guerraoui, Seth Gilbert, Jovan Komatovic, Manuel José Ribeiro Vidigueira, 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

DChannel: Accelerating Mobile ApplicationsWith Parallel High-bandwidth and Low-latency Channels

Haitham Al Hassanieh

Interactive mobile applications like web browsing and gaming are known to benefit significantly from low latency networking, as applications communicate with cloud servers and other users' devices. Emerging mobile channel standards have not met these needs ...

USENIX ASSOC2023

Time vs. Truth: Age-Distortion Tradeoffs and Strategies for Distributed Inference

Yunus Inan

In 1948, Claude Shannon laid the foundations of information theory, which grew out of a study to find the ultimate limits of source compression, and of reliable communication. Since then, information theory has proved itself not only as a quest to find the ...

EPFL2023

Efficient Online Clustering with Moving Costs

Volkan Cevher, Efstratios Panteleimon Skoulakis

In this work we consider an online learning problem, called Online k-Clustering with Moving Costs, at which a learner maintains a set of k facilities over T rounds so as to minimize the connection cost of an adversarially selected sequence of clients. The ...

2023