Automatic consistency assessment for query results in dynamic environments

Queries are convenient abstractions for the discovery of information and services, as they offer content-based information access. In distributed settings, query semantics are well-defined, e.g., they often satisfy ACID transactional properties. In a dynamic network setting, however, achieving transactional semantics becomes complex due to the openness and unpredictability. In this paper, we propose a query processing model for mobile ad hoc and sensor networks suitable for expressing a wide range of query semantics; the semantics differ in the degree of consistency with which results reflect the state of the environment during execution. We introduce several distinct notions of consistency and formalize them. A practical contribution of this paper is a protocol for query processing that automatically assesses and adaptively provides an achievable degree of consistency given the state of the operational environment throughout its execution. The protocol attaches an assessment of the achieved guarantee to returned query results, allowing precise reasoning about a query with a range of possible semantics.