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.


We propose, OMen, a distributed system for dynamically maintaining overlays for topic-based publish/subscribe (pub/sub) systems. In particular, OMen supports churn-resistant construction of topic-connected overlays (TCO), which organizes all nodes interested in the same topic in a directly connected dissemination sub-overlay. While aiming at pub/sub deployments in data centers, OMen internally leverages selected peer-to-peer technologies, such as T-Man as the underlying topology maintenance protocol.

Existing approaches for constructing pub/sub TCOs are (i) centralized algorithms that guarantee low node degrees at the cost of prohibitive running time and (ii) decentralized protocols that are time efficient while lacking bounds on node degrees.

We show both analytically and experimentally that OMen combines the best from both worlds. Namely, OMen achieves (i) low node degrees, close to centralized algorithms, and (ii) high efficiency, scalability, and load balance, comparable to decentralized protocols. Our evaluation uses both synthetic pub/sub workloads and real-world ones extracted from Facebook and Twitter. We generate churn traces with Google cluster data.


Tags: pub/sub, overlay

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

  • 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