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.
Type de document :
Communication dans un congrès
Workshop PCO'11. Parallel Computing and Optimization In conjunction with IPDPS 2011, May 2011, Anchorage, USA, United States. 2011, 〈10.1109/IPDPS.2011.356〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00758593
Contributeur : Eddy Caron <>
Soumis le : jeudi 29 novembre 2012 - 02:28:35
Dernière modification le : mardi 16 janvier 2018 - 15:50:51

Identifiants

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. 2011, 〈10.1109/IPDPS.2011.356〉. 〈hal-00758593〉

Partager

Métriques

Consultations de la notice

87