Divide and Conquer Algorithms for Publish/Subscribe Overlay Design

Chen Chen, Hans-Arno Jacobsen, and Roman Vitenberg.

In Proceedings of The 30th IEEE International Conference on Distributed Computing Systems (ICDCS 2010), pages 622-633, June 2010. IEEE Computer Society.
Acceptance rate: 14%.

Share

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.

Download




Tags: overlay design, algorithms, publish/subscribe


Readers who enjoyed the above work, may also like the following:
  • A Generalized Algorithm for Publish/Subscribe Overlay Design and its Fast Implementation.
    Chen Chen, Roman Vitenberg, and Hans-Arno Jacobsen.
    In Proceedings of The 26th International Symposium on Distributed Computing (DISC 2012), pages 76-90, October 2012. Springer.
    Acceptance rate: 24%.
    Tags: algorithms, overlay design, overlay networks, publish/subscribe
  • Scaling Construction of Low Fan-out Overlays for Topic-based Publish/Subscribe Systems.
    Chen Chen, Roman Vitenberg, and Hans-Arno Jacobsen.
    In Proceedings of The 31th IEEE International Conference on Distributed Computing Systems (ICDCS 2011), pages 225-236, June 2011. IEEE Computer Society.
    Acceptance rate: 15%.
    Tags: overlay design, algorithms, publish/subscribe