About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
ICDCS 2016
Conference paper
Overlay Design for Topic-Based Publish/Subscribe under Node Degree Constraints
Abstract
It is important to build overlays for topic-based publish/subscribe (pub/sub) under resource constraints. In a topic-connected overlay (TCO), each topic t induces a connected sub-overlay among all nodes interested in t. Existing work merely consider how to optimize a complete TCO and implicitly commit the unrealistic assumption of unlimited resources. In contrast, we make maximum use of restricted node degree budgets to build a partial TCO. We formalize the notion of TCO support to capture the quality of the pub/sub overlay. Furthermore, we demonstrate that partial TCOs usually exhibit significantly better cost-effectiveness in practice. We propose two problems of maximizing TCO support in a partial TCO: (1) PTCOA with a bounded average node degree and (2) PTCOM under the maximum node degree constraint. We design two greedy algorithms, which achieve the constant approximation ratios of (1-e-1) for PTCOA and (1-e-1/6) for PTCOM, respectively. Empirical evaluation demonstrates the scalability of our algorithms under a variety of pub/sub workloads. Given practical data sets extracted from Facebook and Twitter, our algorithms produce an 80% TCO with fewer than 20% of the node degree budget as a complete TCO. We also show experimentally that it is promising to design decentralized protocols to compute a partial TCO for pub/sub.