NOTES ON ATOMIC BROADCAST

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.