Automatic consistency assessment for query results in dynamic environments

ABSTRACT

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.

REFERENCES

• 1: Daniel Barbará, Mobile Computing and Databases-A Survey, IEEE Transactions on Knowledge and Data Engineering, v.11 n.1, p.108-117, January 1999 [doi>10.1109/69.755619]
• 2: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 3: Ravi A. Dirckze , Le Gruenwald, A toggle transaction management technique for mobile multidatabases, Proceedings of the seventh international conference on Information and knowledge management, p.371-377, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288679]
• 4: Margaret H. Dunham , Abdelsalam Helal , Santosh Balakrishnan, A mobile transaction model that captures both the data and movement behavior, Mobile Networks and Applications, v.2 n.2, p.149-162, Oct. 1997 [doi>10.1023/A:1013672431080]
• 5: Christine Julien , Gruia-Catalin Roman, Egocentric context-aware programming in ad hoc mobile environments, Proceedings of the 10th ACM SIGSOFT symposium on Foundations of software engineering, November 18-22, 2002, Charleston, South Carolina, USA [doi>10.1145/587051.587056]
• 6: Sanem Kabadayi , Christine Julien, A Local Data Abstraction and Communication Paradigm for Pervasive Computing, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications, p.57-68, March 19-23, 2007 [doi>10.1109/PERCOM.2007.2]
• 7: James J. Kistler , M. Satyanarayanan, Disconnected operation in the Coda File System, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.3-25, Feb. 1992 [doi>10.1145/146941.146942]
• 8: M. Loebbers, D. Willkomm, and A. Koepke. The Mobility Framework for OMNeT++. http://mobility-fw.sourceforge.net
• 9: Qi Lu , M. Satyanaranyanan, Isolation-only transactions for mobile computing, ACM SIGOPS Operating Systems Review, v.28 n.2, p.81-87, April 1994 [doi>10.1145/198153.198164]
• 10: N. Lynch and M. Tuttle. An introduction to I/O automata. CWI-Quarterly , 2(3):219--246, 1989.
• 11: S. K. Madria , B. Bhargava, A Transaction Model for Mobile Computing, Proceedings of the 1998 International Symposium on Database Engineering & Applications, p.92, July 08-10, 1998
• 12: E. Pitoura , B. Bhargava, Maintaining consistency of data in mobile distributed environments, Proceedings of the 15th International Conference on Distributed Computing Systems, p.404, May 30-June 02, 1995
• 13: Gruia-Catalin Roman , Christine Julien , Qingfend Huang, Network abstractions for context-aware mobile computing, Proceedings of the 24th International Conference on Software Engineering, May 19-25, 2002, Orlando, Florida [doi>10.1145/581339.581385]
• 14: Weisheng Si , Chengzhi Li, RMAC: A Reliable Multicast MAC Protocol for Wireless Ad Hoc Networks, Proceedings of the 2004 International Conference on Parallel Processing, p.494-501, August 15-18, 2004 [doi>10.1109/ICPP.2004.66]
• 15: A. Prasad Sistla , Ouri Wolfson , Yixiu Huang, Minimization of Communication Cost Through Caching in Mobile Environments, IEEE Transactions on Parallel and Distributed Systems, v.9 n.4, p.378-390, April 1998 [doi>10.1109/71.667898]
• 16: A. Vargas. OMNeT++. http://www.omnetpp.org
• 17: Mayank Bawa , Aristides Gionis , Hector Garcia-Molina , Rajeev Motwani, The price of validity in dynamic networks, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007627]
• 18: Badri N. Vellambi , Ramanan Subramanian , Faramarz Fekri , Mostafa Ammar, Reliable and efficient message delivery in delay tolerant networks using rateless codes, Proceedings of the 1st international MobiSys workshop on Mobile opportunistic networking, June 11-11, 2007, San Juan, Puerto Rico [doi>10.1145/1247694.1247712]
• 19: Gary D. Walborn , Panos K. Chrysanthis, Transaction processing in PRO-MOTION, Proceedings of the 1999 ACM symposium on Applied computing, p.389-398, February 28-March 02, 1999, San Antonio, Texas, United States [doi>10.1145/298151.298393]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Distributed programming

General Terms:
Algorithms, Reliability

Keywords:
mobile computing, query semantics