In ACM Symposium on Principles of Distributed Computing (PODC), pages 184 - 186, July 2013.
We incorporate fault tolerance in 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. With regard to MinAvg-2TCO, we present GM2 , the first polynomial time algorithm with an approximation ratio. With regards to MinAvg-kTCO, where k >= 2 , we propose a simple and efficient heuristic algorithm, namely HararyPT, that aligns nodes across different sub-overlays.
We experimentally demonstrate the scalability of GM2 and HararyPT under representative pub/sub workloads.