Improving validity of query answering in dynamic systems

Let us consider a large scale distributed system and a query executed on top of it where every process has to contribute to the result. Informally, a query satisfies the interval validity property if its result has been calculated by retrieving data from a set of processes containing at least all those ones that have been present in the system during the whole query lifetime. If the system is prone to churn, it is easy to show that a query cannot deterministically satisfy interval validity. In this paper we propose a novel algorithm that can be used to support distributed queries by increasing the probability of a query to satisfy interval validity. The algorithm strives to (i) reduce the query calculation time (to reduce the net effect of churn) and to (ii) increase the robustness of the overlay network it builds by clustering nodes into cliques of limited size in order for their implementation to be still practical. The paper provides a set of experiments that show the tradeoff between the churn rate and the number of times the interval validity is satisfied. Copyright 2010 ACM.