Decentralized message ordering for publish/subscribe systems

TitleDecentralized message ordering for publish/subscribe systems
Publication TypeConference Papers
Year of Publication2006
AuthorsLumezanu C, Spring N, Bhattacharjee B
Conference NameProceedings of the ACM/IFIP/USENIX 2006 International Conference on Middleware
Date Published2006///
PublisherSpringer-Verlag New York, Inc.
Conference LocationNew York, NY, USA

We describe a method to order messages across groups in a publish/subscribe system without centralized control or large vector timestamps. We show that our scheme is practical---little state is required; that it is scalable---the maximum message load is limited by receivers; and that it performs well---the paths messages traverse to be ordered are not made much longer than necessary. Our insight is that only messages to groups that overlap in membership can be observed to arrive out of order: sequencing messages to these groups is sufficient to provide a consistent order, and when publishers subscribe to the groups to which they send, this message order is a causal order.