Reliable and Total Order Broadcast in the Crash-Recovery Model

Rachid Guerraoui, Romain Boichat
2001
Report or working paper

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.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Rachid Guerraoui, Romain Boichat
2001
Report or working paper

Abstract

Official source

https://infoscience.epfl.ch/record/52392?ln=en

About this result

Related concepts (2)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes (referred to as automated decision-making) and deduce valid inferences (referred to as automated reasoning), achieving automation eventually.

Atomic broadcast

In fault-tolerant distributed computing, an atomic broadcast or total order broadcast is a broadcast where all correct processes in a system of multiple processes receive the same set of messages in the same order; that is, the same sequence of messages. The broadcast is termed "atomic" because it either eventually completes correctly at all participants, or all participants abort without side effects. Atomic broadcasts are an important distributed computing primitive.