Higham, LisaWarpechowska-Gruca, Jolanta2008-02-272008-02-271995-04-01http://hdl.handle.net/1880/45989Atomic 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.EngComputer Scienceunknown1995-562-1410.11575/PRISM/30830