Publications related to Soft real-time analysis of asynchronous agreement algorithms using Petri nets

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-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 ...

New York2023

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

Rachid Guerraoui, Jovan Komatovic, Pierre Philippe Civit, Manuel José Ribeiro Vidigueira, 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

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

Paolo Ienne, Kubilay Atasu, Jovan Blanusa

Finding cycles in directed graphs enables important applications in various domains such as finance, biology, chemistry, and network science. However, as the size of graph datasets continues to grow, it becomes increasingly difficult to discover cycles wit ...

arXiv2023

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

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 ...

Piscataway2023

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

Hybrid Flock - Formation Control Algorithms

Alcherio Martinoli, Cyrill Silvan Baumann, Jonas Perolini, Emna Tourki

Two prominent categories for achieving coordinated multirobot displacement are flocking and navigation in formation. Both categories have their own body of literature and characteristics, including their respective advantages and disadvantages. While typic ...

2022

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

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

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

Soft real-time analysis of asynchronous agreement algorithms using Petri nets

Graph Chatbot

Chat with Graph Search

Planetary-Scale Byzantine Fault Tolerance

Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search

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

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

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

Reliable Microsecond-Scale Distributed Computing

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

Cross-chain payment protocols with success guarantees

Hybrid Flock - Formation Control Algorithms

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

Planetary-Scale Byzantine Fault Tolerance

Byzantine-Resilient Learning Beyond Gradients: Distributing Evolutionary Search

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

Reliable Microsecond-Scale Distributed Computing

Hybrid Flock - Formation Control Algorithms

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

Fast Parallel Algorithms for Enumeration of Simple, Temporal, and Hop-Constrained Cycles

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

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

Cross-chain payment protocols with success guarantees