Atomic Multicast harder than Atomic Broadcast.pdf

Atomic Multicast harderthan Atomic BroadcastRachid Guerraoui Andre SchiperDepartement dInformatiqueEcole Polytechnique Federale de Lausanne1015 Lausanne, SwitzerlandAbstractAtomic broadcast and atomic multicast are communication primitives which ensurethat processes agree on the sequence of messages they deliver. Whereas atomic broadcastis used to send messages to the set of all the processes in the system, atomic multicastsends messages to specic subsets of processes. We say that an atomic multicast algorithmis \genuine, if only the sender and the destination processes of a message take part inthe protocol needed to deliver the message.We formally dene the genuine atomic multicast problem, and we show that this prob-lem turns out to be harder than the atomic broadcast problem. Whereas atomic broadcastcan be solved with unreliable failure detectors that can make false failure suspicions, weshow that atomic multicast cannot.Keywords. Atomic multicast, atomic broadcast, asynchronous system, crash failure, reli-able channel, failure detector. 1 IntroductionThe motivation of this work was to nd out whether the results stated by Chandra andToueg [1], on solving the atomic broadcast problem in distributed asynchronous systems withunreliable failure detectors 1, also apply to the atomic multicast problem. Whereas the twoproblems might appear to be equivalent, it turns out that atomic multicast is harder thanatomic broadcast, as atomic multicast cannot be solved using unreliable failure detectors.1.1 Atomic multicast vs atomic broadcastAn atomic broadcast primitive enables to send messages to all the processes in a system,with the guarantee that all correct processes (those that do not crash) agree on the sequenceof messages they deliver. This primitive guarantees the agreement both on (1) the set ofmessages delivered, and (2) the order according to which the messages are delivered.Contrary to a broadcast that is targeted to the set of all the processes in a system,