Building Fault-Tolerant Overlays with Low Node Degrees for Topic-Based Publish/Subscribe

We present a new approach for designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the MinAvg-kTCO problem parameterized by k: use the minimum number of edges to create a k-topic-connected overlay kTCO) for pub/sub systems, i.e., for each topic, the sub-overlay induced by nodes interested in the topic is k-connected. We prove the NP-completeness of MinAvg-kTCO and show a lower-bound for the hardness of its approximation. For MinAvg-2TCO, we present GM2, the first polynomial-time algorithm with an approximation ratio. For MinAvg-kTCO, where k≥2, we propose HararyPT, a simple and efficient heuristic that aligns nodes across different sub-overlays. We experimentally demonstrate the scalability of GM2 and HararyPT with regards to overlay quality under representative pub/sub workloads. GM2 outputs 2TCO with an empirically insignificant increase in the average node degree, e.g., an increase by 4 in a 1000-node network, as compared to the baseline 1TCO produced by the best-known algorithm. Moreover, GM2 reduces the topic diameters by around 50 percent with respect to those in 1TCO.