Overlay Design for Topic-based Publish/Subscribe under Node Degree Constraints

Chen Chen, Yoav Tock, and Hans-Arno Jacobsen.

In Proceedings of the 36th IEEE International Conference on Distributed Computing Systems (ICDCS), Nara, Japan, June 2016.
Acceptance rate: 17.6%. 68 papers accepted out of 386 submissions.


It is important to construct overlays for topic-based publish/subscribe (pub/sub) under resource constraints. In a topic-connected overlay (TCO), each topic induces a connected sub-overlay among all nodes interested in this topic. 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.


Tags: icdcs16, overlay, pub/sub

Readers who enjoyed the above work, may also like the following:

  • OMen: Overlay Mending for Topic-based Publish/Subscribe Systems Under Churn.
    Chen Chen, Roman Vitenberg , and Hans-Arno Jacobsen.
    In Proceedings of the 10th ACM International Conference on Distributed and Event-Based Systems (DEBS 2016), June 2016.
    Best Paper Award.
    Tags: pub/sub, overlay
  • Weighted Overlay Design for Topic-based Publish/Subscribe on Geo-Distributed Data Centers.
    Chen Chen, Yoav Tock, Hans-Arno Jacobsen, and Roman Vitenberg.
    In Proceedings of the 35th IEEE International Conference on Distributed Computing Systems (ICDCS), pages 474-485, July 2015.
    Acceptance rate: 13%. 70 papers accepted out of 543 submissions..
    Tags: icdcs15, overlay, pub/sub