On-Line Optimization of Publish/Subscribe Overlays

Abstract : Loosely coupled applications can take advantage of the publish/subscribe communication paradigm. In this latter, subscribers declare which events, or which range of events, they wish to monitor, and are asynchronously informed whenever a publishers throws an event. In such a system, when a publication occurs, all peers whose subscriptions contain the publication must be informed. In our approach, the subscriptions are represented by a DR-tree, which is an R-tree where each minimum bounding rectangle is supervised by a peer. Instead of attempting to statically optimize the DR-tree, we give an on-line algorithm, the work function algorithm, which continually changes the DR-tree in response to the sequence of publications, in attempt to dynamically optimize the structure. The competitiveness of this algorithm is computed to be at most 5 for any example where there are at most three subscriptions and the R-tree has height 2. The benefit of the on-line approach is that no prior knowledge of the distribution of publications in the attribute space is needed.
Document type :
Conference papers
Complete list of metadatas

https://hal.inria.fr/hal-00758593
Contributor : Eddy Caron <>
Submitted on : Thursday, November 29, 2012 - 2:28:35 AM
Last modification on : Friday, April 20, 2018 - 3:44:24 PM

Identifiers

Collections

Citation

Eddy Caron, Ajoy Datta, Benjamin Depardon, Lawrence Larmore. On-Line Optimization of Publish/Subscribe Overlays. Workshop PCO'11. Parallel Computing and Optimization In conjunction with IPDPS 2011, May 2011, Anchorage, USA, United States. ⟨10.1109/IPDPS.2011.356⟩. ⟨hal-00758593⟩

Share

Metrics

Record views

127