Reinforce Your Overlay with Shadows: Efficient Dynamic Maintenance of Robust Low Fan-out Overlays for Topic-based Publish/Subscribe Under Churn

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

University of Toronto, University of Oslo, 2012.
Pages 1-13.


Overlay network design for topic-based publish/ subscribe systems is of primary importance because the overlay directly impacts the system’s performance. Determining a low fan-out topic-connected overlay (TCO) is a fundamental problem.

Existing algorithms for constructing TCOs with provably low fan-out build the overlays from scratch. In this paper, we propose the first fully dynamic algorithms for efficiently maintaining TCO in presence of node churn such that both the average and maximum node degrees stay provably low. The main challenge of dynamic maintenance is to efficiently overcome departure of nodes central to topic-connectivity. This is attained by maintaining sets of shadow nodes so that all links adjacent to a failed node can quickly be replaced by adding links among shadow nodes.

Compared to constructing TCOs from scratch, the proposed algorithms exhibit two important advantages: When a node joins or leaves, topic connectivity is restored much faster, and changes to the overlay are incremental so that existing links do not need to be torn down. We corroborate these advantages by extensive evaluations on typical workloads with up to 2000 nodes and 200 topics under 1000 rounds of churn.


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 10th ACM International Conference on Distributed and Event-Based Systems (DEBS), June 2016.
    Tags: overlay, pub/sub, churn handling, topic-connected overlay, t-man
  • Overlay Design for Topic-based Publish/Subscribe under Node Degree Constraints.
    Chen Chen, Yoav Tock, and Hans-Arno Jacobsen.
    In 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 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