Crash-tolerant causal broadcast in O(n) messages

Achour Mostéfaoui, Matthieu Perrin, Michel Raynal, Jiannong Cao

Research output: Journal article publicationJournal articleAcademic researchpeer-review

Abstract

Causal broadcast is a communication abstraction designed for asynchronous systems. It ensures that the messages broadcast by the processes are delivered in their broadcast causality order, namely, if the broadcast of a message m causally precedes the broadcast of a message m, no process delivers m unless it has previously delivered m. Several algorithms implementing causal broadcast have been proposed for asynchronous systems prone to any number of process crashes. These algorithms rely on an underlying Reliable Broadcast abstraction, whose message cost is n2. This paper presents a simple causal broadcast algorithm whose cost is n messages per causal broadcast. This is obtained at the cost of protocol messages whose size can be up to n application messages.

Original languageEnglish
Article number105837
Pages (from-to)1-6
JournalInformation Processing Letters
Volume151
DOIs
Publication statusPublished - Nov 2019

Keywords

  • Algorithms
  • Distributed computing
  • Fault-tolerance
  • Reliable communication

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Signal Processing
  • Information Systems
  • Computer Science Applications

Cite this