Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

Concept

Terminating Reliable Broadcast

Terminating Reliable Broadcast (TRB) is a problem in distributed computing that encapsulates the task of broadcasting a message to a set of receiving processes in the presence of faults. In particular, the sender and any other process might fail ("crash") at any time. Problem description A TRB protocol typically organizes the system into a sending process and a set of receiving processes, which may include the sender itself. A process is called "correct" if it does not fail at any point during its execution. The goal of the protocol is to transfer data (the "message") from the sender to the set of receiving processes. A process may perform many I/O operations during protocol execution, but eventually "delivers" a message by passing it to the application on that process that invoked the TRB protocol. The protocol must provide important guarantees to the receiving processes. All correct receiving processes, for example, must deliver the sender's message if the sender is also

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés

Chargement

Cours associés

Chargement

Séances de cours associées

Chargement

Résumé

Source officielle

À propos de ce résultat

Publications associées (17)

Publications associées

Chargement

Personnes associées (2)

Personnes associées

Chargement

Unités associées (1)

Unités associées

Chargement

Concepts associés

Chargement

Cours associés (2)

Cours associés

Chargement

Séances de cours associées (16)

Séances de cours associées

Chargement

An Adaptive Algorithm for Efficient Message Diffusion in Unreliable Environments

Benoît Garbinato, Rodrigo Malta Schmidt, Fernando Pedone

In this paper, we propose a novel approach for solving the reliable broadcast problem in a probabilistic model, i.e., where links lose messages and where processes crash and recover probabilistically. Our approach consists in first defining the optimality of probabilistic reliable broadcast algorithms and the adaptiveness of algorithms that aim at converging toward such optimality. Then, we propose an algorithm that precisely converges toward the optimal behavior, thanks to an adaptive strategy based on Bayesian statistical inference. Our adaptive algorithm is modular and consists of two activities. The first activity is responsible for solving the reliable broadcast, given information about the failure probability of each link and of each process. This activity relies on the notion of Maximum Reliability Tree, which we derive from the notion of Maximum Spanning Tree. The other activity is responsible for approximating failure probabilities of links and processes, using Bayesian networks. We compare the performance of our algorithm with that of a typical gossip algorithm through simulation. Our results show, for example, that our adaptive algorithm quickly converges toward such exact knowledge.

2004

Chargement

Collaborative Learning in the Jungle (Decentralized, Byzantine, Heterogeneous, Asynchronous and Nonconvex Learning)

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

We study Byzantine collaborative learning, where n nodes seek to collectively learn from each others' local data. The data distribution may vary from one node to another. No node is trusted, and f < n nodes can behave arbitrarily. We prove that collaborative learning is equivalent to a new form of agreement, which we call averaging agreement. In this problem, nodes start each with an initial vector and seek to approximately agree on a common vector, which is close to the average of honest nodes' initial vectors. We present two asynchronous solutions to averaging agreement, each we prove optimal according to some dimension. The first, based on the minimum-diameter averaging, requires n ≥ 6f+1, but achieves asymptotically the best-possible averaging constant up to a multiplicative constant. The second, based on reliable broadcast and coordinate-wise trimmed mean, achieves optimal Byzantine resilience, i.e., n≥3f+1. Each of these algorithms induces an optimal Byzantine collaborative learning protocol. In particular, our equivalence yields new impossibility theorems on what any collaborative learning algorithm can achieve in adversarial and heterogeneous environments.

2021

Chargement

An Adaptive Algorithm for Efficient Message Diffusion in Unreliable Environments

Benoît Garbinato, Rodrigo Malta Schmidt, Fernando Pedone

In this paper, we propose a novel approach for solving the reliable broadcast problem in a probabilistic unreliable model. Our approach consists in first defining the optimality of probabilistic reliable broadcast algorithms and the adaptiveness of algorithms that aim at converging toward such optimality. Then, we propose an algorithm that precisely converges toward the optimal behavior, thanks to an adaptive strategy based on Bayesian statistical inference. We compare the performance of our algorithm with that of a typical gossip algorithm through simulation. Our results show, for example, that our adaptive algorithm quickly converges toward such exact knowledge.

2004

Chargement

CS-451: Distributed algorithms

Computing is nowadays distributed over several machines, in a local IP-like network, a cloud or a P2P network. Failures are common and computations need to proceed despite partial failures of machines or communication links. This course will study the foundations of reliable distributed computing.

CS-438: Decentralized systems engineering

A decentralized system is one that works when no single party is in charge or fully trusted. This course teaches decentralized systems principles while guiding students through the development and testing of their own decentralized system incorporating messaging, encryption, and blockchain concepts.