Ordered Multicast and Distributed Swap preliminary report

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. Ordered multicast is a natural foundation for push-based cache coherence and certain kinds of middleware. 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, and discuss their corresponding ordered multicast protocols. These protocols have lower latency than more obvious approaches based on distributed counting.