A General Algorithmic Model for Subscription Propagation and Content-based Routing with Delivery Guarantees

This paper examines the problem of subscription propagation and aggregation in content-based publish/subscribe systems. We present a general model for subscription propagation and content-based routing and the correctness criteria for it to support reliable delivery. This formal model is used to construct a generic subscription propagation algorithm for asynchronous content-based routing networks with redundant paths and failures. This algorithm does not require agreement between multiple paths in the network and hence is efficient and highly available.


We analyze the safety aspects of the generic algorithm and interpret many previously known algorithms as different encodings of the generic algorithm, with various space optimizations for different circumstances. The algorithm is applicable to both best-effort and reliable delivery of messages.