Constructing Fault-Tolerant Overlay Networks for Topic-based Pub/Sub

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

University of Toronto & University of Oslo, 2013.


We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based publish/subscribe communication. We propose a new family of optimization problems, named MinAvg-kTCO, that captures the trade-offs among several key dimensions including fault tolerance, scalability, performance, and message dissemination. Roughly speaking, the MinAvg-kTCO problem is: use the minimum number of edges to create a k-topic-connected overlay} (kTCO) for pub/sub systems, i.e., for each topic the sub-overlay induced by nodes interested in the topic is k-connected.

We prove the NP-completeness of MinAvg-kTCO and show a lower-bound for the hardness of its approximation. With regard to the MinAvg-2TCO problem, we present the first polynomial time algorithm, namely GM2, with a guaranteed approximation factor relative to the optimum. %approximation ratio. We show experimentally that on representative publish/subscribe workloads, the GM2 algorithm outputs 2TCO at the cost of an empirically insignificant increase in the average node degree, which is around $1.65$ times that of 1TCO produced by the algorithm with the best known approximation ratio. Besides, GM2 reduces the topic diameters around $50\%$ as compared to those in the baseline 1TCO.

With regards to the MinAvg-kTCO problem, where $k >= 2$, we propose a simple and efficient heuristic algorithm, namely HararyPT, that aligns nodes across different sub-overlays. We show the practical scalability of HararyPT for highly correlated pub/sub workloads in terms of the number of nodes, the number of topics, and the number of subscriptions per node.


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