Publication

Reliable and Total Order Broadcast in the Crash-Recovery Model

Rachid Guerraoui, Romain Boichat
2001
Reports

Résumé

This paper addresses the problem of broadcasting messages in a reliable and totally ordered manner when processes and channels may crash and recover, or crash and never recover. We present a suite of specifications of reliable and total order broadcast primitives and we describe algorithms that implement those specifications. Our approach is modular and incremental. It is modular in the sense that the properties of broadcast primitives are first given separately and then composed: this provides a comprehensive design space for broadcast semantics. It is incremental in the sense that a broadcast algorithm implementing a given specification is obtained by transforming an algorithm that implements a weaker specification: this gives an automatic way to improve the resilience of broadcast primitives. We derive specific reliable and total order broadcast algorithms and we discuss their performance and optimality. Keywords:reliable broadcast, total order broadcast, modularity,transformation, optimisation, crash-recovery model.

Source officielle

https://infoscience.epfl.ch/entities/publication/1e62d433-faad-474a-9de6-e4130a050472

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

Graph Chat

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.

Rachid Guerraoui, Romain Boichat
2001
Reports

Résumé

Source officielle

https://infoscience.epfl.ch/entities/publication/1e62d433-faad-474a-9de6-e4130a050472

À propos de ce résultat

Concepts associés (20)

Algorithme de Prim

thumb|right|Arbre couvrant de poids minimum L'algorithme de Prim est un algorithme glouton qui calcule un arbre couvrant minimal dans un graphe connexe pondéré et non orienté. En d'autres termes, cet algorithme trouve un sous-ensemble d'arêtes formant un arbre sur l'ensemble des sommets du graphe initial et tel que la somme des poids de ces arêtes soit minimale. Si le graphe n'est pas connexe, alors l'algorithme détermine un arbre couvrant minimal d'une composante connexe du graphe.

Algorithme

thumb|Algorithme de découpe d'un polygone quelconque en triangles (triangulation). Un algorithme est une suite finie et non ambiguë d'instructions et d’opérations permettant de résoudre une classe de problèmes. Le domaine qui étudie les algorithmes est appelé l'algorithmique. On retrouve aujourd'hui des algorithmes dans de nombreuses applications telles que le fonctionnement des ordinateurs, la cryptographie, le routage d'informations, la planification et l'utilisation optimale des ressources, le , le traitement de textes, la bio-informatique L' algorithme peut être mis en forme de façon graphique dans un algorigramme ou organigramme de programmation.

Algorithme de recherche

En informatique, un algorithme de recherche est un type d'algorithme qui, pour un domaine, un problème de ce domaine et des critères donnés, retourne en résultat un ensemble de solutions répondant au problème. Supposons que l'ensemble de ses entrées soit divisible en sous-ensemble, par rapport à un critère donné, qui peut être, par exemple, une relation d'ordre. De façon générale, un tel algorithme vérifie un certain nombre de ces entrées et retourne en sortie une ou plusieurs des entrées visées.

Afficher plus

Publications associées (32)

Afficher plus

Reliable and Total Order Broadcast in the Crash-Recovery Model

Chattez avec Graph Search

SplineSplat: 3D Ray Tracing for Higher-Quality Tomography

Dataset: Modelling human activities in a system of cities

LWE with Quantum Amplitudes: Algorithm, Hardness, and Oblivious Sampling