Skip to Main content Skip to Navigation

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.
Document type :
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download
Contributor : Philippe Lamarre Connect in order to contact the contributor
Submitted on : Tuesday, May 12, 2009 - 5:36:45 PM
Last modification on : Wednesday, April 27, 2022 - 3:50:17 AM
Long-term archiving on: : Thursday, June 30, 2011 - 11:27:49 AM


Files produced by the author(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⟩



Record views


Files downloads