Brief announcement: Constructing fault-tolerant overlay networks for topic-based publish/subscribe

Chen Chen, Roman Vitenberg, Hans Arno Jacobsen

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

1 Zitat (Scopus)

Abstract

We incorporate fault tolerance in designing reliable and scalable overlay networks to support topic-based pub/sub communication. We propose the M in Avg-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 M in Avg-kTCO and show a lower-bound for the hardness of its approximation. With regard to M in Avg-2TCO, we present GM2, the first polynomial time algorithm with an approximation ratio. With regards to M in Avg-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 GM 2 and HararyPT under representative pub/sub workloads.

OriginalspracheEnglisch
TitelPODC 2013 - Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing
Seiten184-186
Seitenumfang3
DOIs
PublikationsstatusVeröffentlicht - 2013
Extern publiziertJa
Veranstaltung2013 ACM Symposium on Principles of Distributed Computing, PODC 2013 - Montreal, QC, Kanada
Dauer: 22 Juli 201324 Juli 2013

Publikationsreihe

NameProceedings of the Annual ACM Symposium on Principles of Distributed Computing

Konferenz

Konferenz2013 ACM Symposium on Principles of Distributed Computing, PODC 2013
Land/GebietKanada
OrtMontreal, QC
Zeitraum22/07/1324/07/13

Fingerprint

Untersuchen Sie die Forschungsthemen von „Brief announcement: Constructing fault-tolerant overlay networks for topic-based publish/subscribe“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren