Reliable broadcasts and communication models: tradeoffs and lower bounds
type: Item
instance of: scholarly article
title: Reliable broadcasts and communication models: tradeoffs and lower bounds
zbMATH Open document ID: 0659.68043
DOI: 10.1007/BF01872844
author: Pat Stephenson
author: Rogério Drummond
author: Ozalp Babaoglu
published in: Distributed Computing
publication date: 1988-01-01T00:00:00Z
review text: Reliable broadcast is a mechanism by which a processor in a distributed system disseminates a value to all other processors in the presence of both communication and processor failures. Protocols to achieve reliable broadcast are at the heart of most fault-tolerant applications. We characterize the execution time of reliable broadcast protocols as a function of the communication model. This model includes similar communication structures such as fully-connected point-to-point graphs, linear chains, rings, broadcast networks (such as Ethernet) and buses. We derive a parameterized protocol that implements reliable broadcast for any member within this class. We obtain lower bound results that show the optimality of our protocols. The lower bound results identify a time complexity gap between systems where processors may only fail to send messages, and systems where processors may fail both to send and to receive messages. The tradeoffs that our results reveal between performance, resiliency and network cost offer many new alternatives previously not considered in designing fault-tolerant systems.
Mathematics Subject Classification ID: 68N25
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4078783
zbMATH Keywords: distributed systems
zbMATH Keywords: Byzantine agreement
zbMATH Keywords: hardware/software tradeoff
zbMATH Keywords: reliable broadcast
zbMATH Keywords: protocols
zbMATH Keywords: communication model
zbMATH Keywords: broadcast networks
zbMATH Keywords: lower bound results
zbMATH Keywords: time complexity
zbMATH Keywords: fault-tolerant systems
Wikidata QID: Q59491571
MaRDI profile type: Publication
cites work: Efficient fault-tolerant routings in networks
cites work: Authenticated Algorithms for Byzantine Agreement
cites work: Q3666268
cites work: A lower bound for the time to assure interactive consistency
cites work: The Byzantine Generals Problem
cites work: Q4319638
full work available at URL: https://doi.org/10.1007/bf01872844
OpenAlex ID: W1967084447
DBLP publication ID: journals/dc/BabaogluSD88
description: scientific article; zbMATH DE number 4078783