NOTES ON ATOMIC BROADCAST
Date
1995-04-01
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Atomic broadcast [1] is a powerful communication primitive, which is
applied in a natural way in sequentially consistent implementations of
various data structures (see [1]). Unfortunately the atomic
broadcast algorithm
as given in [1] is incorrect. Here some ways of correcting it are
analyzed under assumptions of blocking versus nonblocking communication.
Two atomic broadcast algorithms are proposed: one correct if it is used in
a blocking manner, the other correct unconditionally. The latter
algorithm, when used in the sequentially consistent implementations of
data structures proposed in [1], has the same time complexity and a
reduced message complexity compared to that claimed in the original
application.
Description
Keywords
Computer Science