University of Toronto, University of Oslo, 2012.
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
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.