Publication

The Generic Consensus Service

Résumé

This paper describes a modular approach for the construction of fault-tolerant agreement protocols. The approach is based on a generic consensus service. Fault-tolerant agreement protocols are built using a client-server interaction, where the clients are the processes that must solve the agreement problem, and the servers implement the consensus service. This service is accessed through ``a generic consensus filter'', customized for each specific agreement problem. We illustrate our approach on the construction of various fault-tolerant agreement protocols such as non-blocking atomic commitment, group membership, view synchronous communication and total order multicast. Through a systematic reduction to consensus, we provide a simple way to solve agreement problems. In addition to its modularity, our approach enables efficient implementations of agreement protocols, and precise characterization of the assumptions underlying their liveness and safety properties.

À 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.
Concepts associés (32)
Problème du consensus
Le problème du consensus est un problème fondamental en théorie du calcul distribué. Il consiste pour un ensemble de machines à se mettre d'accord sur une valeur ou, par extension, sur une séquence de valeurs. La résolution du consensus est primordiale pour la coordination des systèmes distribués. Elle permet notamment la consistance des systèmes répliqués malgré la défaillance d'une partie de leurs composants.
Problème des généraux byzantins
En informatique, le problème des généraux byzantins est une métaphore qui traite de la remise en cause de la fiabilité des transmissions et de l'intégrité des interlocuteurs. La question est donc de savoir comment, et dans quelle mesure, il est possible de prendre en compte une information dont la source ou le canal de transmission est suspect. La solution implique l'établissement d'un algorithme (d'une stratégie) adapté. Ce problème a été traité en profondeur pour la première fois dans l'article The Byzantine Generals Problem publié en 1982.
Serveur informatique
thumb|Des serveurs empilés. Un serveur informatique est un dispositif informatique (matériel et logiciel) qui offre des services à un ou plusieurs clients (parfois des milliers). Les services les plus courants sont : l'accès aux informations du World Wide Web ; le courrier électronique ; le partage de périphériques (imprimantes, disque durs) ; le commerce électronique ; le stockage en base de données ; la gestion de l'authentification et du contrôle d'accès ; le jeu et la mise à disposition de logiciels applicatifs.
Afficher plus
Publications associées (33)

Planetary-Scale Byzantine Fault Tolerance

Matteo Monti

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

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
Afficher plus
MOOCs associés (2)
Information, Calcul, Communication: Introduction à la pensée informatique
Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d
Information, Calcul, Communication: Introduction à la pensée informatique
Dans une première partie, nous étudierons d’abord comment résoudre de manière très concrète un problème au moyen d’un algorithme, ce qui nous amènera dans un second temps à une des grandes questions d