Scalable Atomic Multicast

Luís Rodrigues and Rachid Guerraoui and André Schiper

Selected sections of this report will be published in the Proceedings of the Seventh International Conference on Computer Communications and Networks (IC3N'98), Lafayette, Louisiana, USA, 12-15 October, 1998.


We present a new scalable fault-tolerant algorithm which ensures total order delivery of messages sent to multiple groups of processes. Our algorithm is particularly well suited for large scale systems because: (1) any process can multicast a message to one or more groups of processes without being forced to join those groups; (2) inter-group total order is ensured system-wide but, for each individual multicast, the number and size of messages exchanged depends only on the number of addressees; (3) process failure detection does not need to be reliable.

Our algorithm also exhibits a modular design. It uses two companion protocols, namely a reliable multicast protocol and a consensus protocol, and these protocols are not required to use the same communication channels or to share common variables with the total order protocol. This approach follows a design methodology based on the composition of (encapsulated) micro-protocols.

Also available extended report (gzip postscript).