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.
Notes
We are currently acquiring citations for the work deposited into this collection. We recognize the distribution rights of this item may have been assigned to another entity, other than the author(s) of the work.If you can provide the citation for this work or you think you own the distribution rights to this work please contact the Institutional Repository Administrator at digitize@ucalgary.ca
