Tech Report CS-00-08

Ordered Multicast and Distributed Swap

Maurice Herlihy Srikanta Tirthapura and Roger Wattenhofer

December 2000

Abstract:

A multicast protocol is ordered (or totally ordered) if it ensures that messages multicast to a group of nodes are delivered in the same order at each destination node, even when those messages are generated concurrently from several sources.

This paper shows how to reduce the complex problem of enforcing multicast ordering to a simpler distributed coordination problem we call distributed swap. Any distributed swap protocol can transform an unordered reliable multicast into an ordered multicast in a modular way.

We introduce two novel distributed swap protocols, the arrow swap protocol (based on the arrow directory protocol) and the combining swap protocol (based on combining trees) and discuss their corresponding ordered multicast protocols. These protocols have lower latency than more obvious approaches based on distributed counting.

(complete text in pdf or gzipped postscript)