Divide and conquer algorithms for publish/subscribe overlay design

Chen Chen, Hans Arno Jacobsen, Roman Vitenberg

Publikation: Beitrag in Buch/Bericht/KonferenzbandKonferenzbeitragBegutachtung

16 Zitate (Scopus)

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 topic-connected overlay, in which for every topic the graph induced by nodes interested in the topic is connected, is a fundamental problem. Existing algorithms for this problem suffer from three key drawbacks: (1) prohibitively high running time cost, (2) requirement of full system knowledge and centralized operation, and (3) constructing overlay from scratch. From a practical point of view, these are all significant limitations. To address these concerns, in this paper, we develop novel algorithms that efficiently solve the problem of dynamically joining two or more topic-connected overlays. Inspired from the divide-and-conquer character of our approach, we derive an algorithm that solves the original problem at a fraction (up to 1.7%) of the running time cost of alternative solutions, but at the expense of an empirically insignificant increase in the average node degree.

OriginalspracheEnglisch
TitelICDCS 2010 - 2010 International Conference on Distributed Computing Systems
Seiten622-633
Seitenumfang12
DOIs
PublikationsstatusVeröffentlicht - 2010
Extern publiziertJa
Veranstaltung30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010 - Genova, Italien
Dauer: 21 Juni 201025 Juni 2010

Publikationsreihe

NameProceedings - International Conference on Distributed Computing Systems

Konferenz

Konferenz30th IEEE International Conference on Distributed Computing Systems, ICDCS 2010
Land/GebietItalien
OrtGenova
Zeitraum21/06/1025/06/10

Fingerprint

Untersuchen Sie die Forschungsthemen von „Divide and conquer algorithms for publish/subscribe overlay design“. Zusammen bilden sie einen einzigartigen Fingerprint.

Dieses zitieren