Brief Announcement: Constructing Fault-Tolerant Overlay Networks for Topic-based Publish/Subscribe

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

In ACM Symposium on Principles of Distributed Computing (PODC), pages 184 - 186, July 2013.


We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the MinAvg-kTCO problem parameterized by k: 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 MinAvg-2TCO, we present GM2 , the first polynomial time algorithm with an approximation ratio. With regards to MinAvg-kTCO, where k >= 2 , we propose a simple and efficient heuristic algorithm, namely HararyPT, that aligns nodes across different sub-overlays.

We experimentally demonstrate the scalability of GM2 and HararyPT under representative pub/sub workloads.


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