Star Merge and Divide-and-conquer Algorithms for Publish/Subscribe Topic-connected Overlay Design

Chen Chen, Hans-Arno Jacobsen, and Roman Vitenberg.

University of Toronto, University of Oslo, April 2010.
Pages 1-18.


Overlay network design for topic-based publish/subscribe systems is of primary importance because the overlay directly impacts the system's performance. Determining a topic-connected overlay, in which for every topic the graph induced by nodes interested in the topic is connected, is a fundamental problem.

Existing algorithms for this problem suffer from three key drawbacks: (1) prohibitively high running time cost, (2) requirement of full system knowledge and centralized operation, and (3) constructing overlay from scratch. From a practical point of view, these are all significant limitations.

To address these concerns, in this paper, we develop novel algorithms that efficiently solve the problem of dynamically joining two or more topic-connected overlays. Inspired from the divide-and-conquer character of our approach, we derive an algorithm that solves the original problem at a fraction (up to 1.7%) of the running time cost of alternative solutions, but at the expense of an empirically insignificant increase in the average node degree.


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 10th ACM International Conference on Distributed and Event-Based Systems (DEBS), June 2016.
    Tags: overlay, pub/sub, churn handling, topic-connected overlay, t-man
  • Overlay Design for Topic-based Publish/Subscribe under Node Degree Constraints.
    Chen Chen, Yoav Tock, and Hans-Arno Jacobsen.
    In 36th IEEE International Conference on Distributed Computing Systems (ICDCS), Nara, Japan, June 2016.
    Acceptance rate: 17.6%. 68 papers accepted out of 386 submissions.
    Tags: icdcs16, overlay, pub/sub
  • Weighted Overlay Design for Topic-based Publish/Subscribe on Geo-Distributed Data Centers.
    Chen Chen, Yoav Tock, Hans-Arno Jacobsen, and Roman Vitenberg.
    In 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