A Generalized Algorithm for Publish/Subscribe Overlay Design and Its Fast Implementation

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

University of Toronto, University of Oslo, 2012.


It is a challenging and fundamental problem to construct the underlying overlay network to support efficient and scalable information distribution in topic-based publish/subscribe systems. Existing overlay design algorithms aim to minimize the node fan-out while building topic-connected overlays, in which all nodes interested in the same topic are organized in a directly connected dissemination sub-overlay. However, most state-of-the-art algorithms suffer from high computational complexity, such as $O(|V|^4|T|)$, where $V$ is the node set and $T$ is the topic set.

We devise a general indexing data structure that %allows us to provides a significantly faster implementation, with $O(|V|^2|T|)$ running time, for different state-of-the-art algorithms. The generality of the indexing data structure is due to the fact that it enables edge lookup by both node degree and \emph{edge contribution}, a central metric in all existing algorithms. When tested on typical pub/sub workloads, the speedup observed was by a factor of over $1\,000$, thereby rendering the algorithms more suitable for practical use. For example, under a typically Zipf distributed pub/sub workload, with $1\,000$ nodes and $100$ topics, our new implementation completes in $3.823$ seconds, while the previous alternative takes over $555$ minutes.


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
  • 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.
    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 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