Query Replication in Distributed Information Systems with Autonomous Participants

Philippe Lamarre 1 Jorge-Arnulfo Quiané-Ruiz 1 Patrick Valduriez 1
1 ATLAS - Complex data management in distributed systems
UN - Université de Nantes, Inria Rennes – Bretagne Atlantique
Abstract : We consider Distributed Information Systems with Autonomous Participants (DISAP), i.e., participants (consumers and providers) may have special interests towards queries and other participants. Recent applications of DISAP on the Internet have emerged to share data, services, or computing resources at an unprecedented scale (e.g. SETI@home). With autonomous participants, the only way to avoid a participant to voluntarily leave the system is to satisfy its interests when allocating queries. But, participants' satisfaction may also be badly affected by other participants' failures or comportment. In this context, replicating queries is useful to address two different problems: tolerate providers' failures and deal with Byzantine providers. In this paper, we make the following main contributions. First, we formalize the query allocation problem over faulty participants in the context of DISAP. Second, we define participant's satisfaction and define a notion of global satisfaction, which considers participants' satisfaction and their probability of failure. Third, we propose a query replication algorithm, SbQR, which deals with the participants' failures by deciding on-line whether a query should be replicated and at which rate. Fourth, we propose another query replication algorithm, called SbQR+, which generalizes SbQR with the goal of prioritizing critical queries. Finally, we implemented both algorithms and compared them to the popular baseline algorithm. The results demonstrate that our algorithms significantly outperform the baseline algorithm from the performance and satisfaction points of view. In particular, Sb QR+ is excellent at choosing the queries that must be replicated to guarantee both participants' satisfaction and good system performance.
Type de document :
[Research Report] RR-6928, INRIA. 2009, pp.31
Liste complète des métadonnées

Littérature citée [37 références]  Voir  Masquer  Télécharger

Contributeur : Philippe Lamarre <>
Soumis le : mardi 12 mai 2009 - 17:36:45
Dernière modification le : samedi 17 septembre 2016 - 01:36:04
Document(s) archivé(s) le : jeudi 30 juin 2011 - 11:27:49


Fichiers produits par l'(les) auteur(s)


  • HAL Id : inria-00383321, version 1



Philippe Lamarre, Jorge-Arnulfo Quiané-Ruiz, Patrick Valduriez. Query Replication in Distributed Information Systems with Autonomous Participants. [Research Report] RR-6928, INRIA. 2009, pp.31. 〈inria-00383321〉



Consultations de la notice


Téléchargements de fichiers