Valid Query Answers exploting Node Virtualization

This thesis studies the problem of answering system-wide queries, satisfying the interval validity semantics, in a distributed system prone to continuous arrival and departure of participants. The interval validity semantic states that the query answer must be calculated considering contributions of at least all processes that remain in the distributed system for the whole query duration. It is impossible to satisfy this semantics in systems experiencing unbounded churn due to the lack of connectivity and path stability between processes. This thesis presents a novel architecture, named Virtual Tree, for building and maintaining a structured overlay network with guaranteed connectivity and path stability in settings characterized by bounded churn rate. The architecture includes a simple query answering algorithm that provides interval valid answers. The overlay network generated by the Virtual Tree architecture is a tree-shaped topology with virtual nodes constituted by clusters of processes and virtual links constituted by multiple communication links connecting processes located in adjacent virtual nodes. A bound has been formally proved on the churn rate for interval valid queries and it has been carried out an extensive experimental evaluation that shows the degree of robustness of the overlay network generated by the virtual tree architecture under different churn rates. The thesis also provide an application scenario of the proposed architecture in the field of the volunteer computing. The application scenario shows that Virtual Tree represents a fundamental building block for the architecture of a volunteer computing platform and its capability of offering valid queries enhances the performance of the system providing a better accuracy in the task-scheduling procedure.