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 :
Rapport
[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

https://hal.inria.fr/inria-00383321
Contributeur : Philippe Lamarre <>
Soumis le : mardi 12 mai 2009 - 17:36:45
Dernière modification le : mercredi 11 avril 2018 - 01:57:16
Document(s) archivé(s) le : jeudi 30 juin 2011 - 11:27:49

Fichier

RR-6928.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00383321, version 1

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

269

Téléchargements de fichiers

98