Ordered Multicast and Distributed Swap
Maurice P. Herlihy, Srikanta Tirthapura, Rogert Wattenhofer · ACM SIGOPS Operating Systems Review · 2001
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.