ElastO: Dynamic, Efficient, and Robust Maintenance of Low Fan-out Overlays for Topic-based Publish/Subscribe under Churn

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

University of Toronto & University of Oslo, 2013.


We propose, ElastO, a distributed system for constructing and maintaining scalable churn-resistant overlay networks for topic-based publish/subscribe (pub/sub) systems. ElastO is designed to dynamically tread the balance among several key dimensions: (a) topic-connected overlay (TCO), i.e., the sub-overlay induced by nodes interested in any topic is connected, (b) low maximum and average node fan-outs, (c) high efficiency to maintain the overlay in presence of churn, (d) balanced computation and communication overhead across all the nodes.

Existing approaches for maintaining pub/sub TCOs are either static and runtime-costly algorithms, or decentralized protocols that produce significantly higher node degrees. One main challenge is to effectively overcome departure of nodes central to the TCO. ElastO carefully maintains local view at each node and efficiently computes sets of shadow nodes upon churn events, so that all links adjacent to a failed node can be quickly replaced by adding links among the shadow nodes.

We evaluate ElastO using both synthetical pub/sub workloads and practical workloads extracted from Facebook and Twitter, and using real-world cluster churn traces released by Google. We show analytically and experimentally that ElastO achieves low fan-out close to static algorithms and high efficiency comparable to decentralized protocols.


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