Middleware Systems Research Group

University of Toronto, Canada

• << Publications

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

Abstract

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.

Download