Incremental consistency checking for pervasive context

ABSTRACT

Applications in pervasive computing are typically required to interact seamlessly with their changing environments. To provide users with smart computational services, these applications must be aware of incessant context changes in their environments and adjust their behaviors accordingly. As these environments are highly dynamic and noisy, context changes thus acquired could be obsolete, corrupted or inaccurate. This gives rise to the problem of context inconsistency, which must be timely detected in order to prevent applications from behaving anomalously. In this paper, we propose a formal model of incremental consistency checking for pervasive contexts. Based on this model, we further propose an efficient checking algorithm to detect inconsistent contexts. The performance of the algorithm and its advantages over conventional checking techniques are evaluated experimentally using Cabot middleware.

REFERENCES

• 1: Asaf Adi , Opher Etzion, Amit - the situation manager, The VLDB Journal — The International Journal on Very Large Data Bases, v.13 n.2, p.177-203, May 2004 [doi>10.1007/s00778-003-0108-y]
• 2: Andrey Balmin , Yannis Papakonstantinou , Victor Vianu, Incremental validation of XML documents, ACM Transactions on Database Systems (TODS), v.29 n.4, December 2004 [doi>10.1145/1042046.1042050]
• 3: Denilson Barbosa , Alberto O. Mendelzon , Leonid Libkin , Laurent Mignet , Marcelo Arenas, Efficient Incremental Validation of XML Documents, Proceedings of the 20th International Conference on Data Engineering, p.671, March 30-April 02, 2004
• 4: Barry Brumitt , Brian Meyers , John Krumm , Amanda Kern , Steven A. Shafer, EasyLiving: Technologies for Intelligent Environments, Proceedings of the 2nd international symposium on Handheld and Ubiquitous Computing, p.12-29, September 25-27, 2000, Bristol, UK
• 5: Capra, L., Emmerich, W., and Mascolo, C. CARISMA: Context-Aware Reflective Middleware System for Mobile Applications. IEEE Transactions on Software Engineering 29(10), pp. 929--945, Oct 2003.
• 6: Dey, A.K., Abowd, G.D., and Salber, D. A Context-Based Infrastructure for Smart Environments. Proceedings of the 1st International Workshop on Managing Interactions in Smart Environments, pp. 114--128, Dublin, Ireland, Dec 1999.
• 7: Wenfei Fan , Leonid Libkin, On XML integrity constraints in the presence of DTDs, Journal of the ACM (JACM), v.49 n.3, p.368-406, May 2002 [doi>10.1145/567112.567117]
• 8: William G. Griswold , Robert Boyer , Steven W. Brown , Tan Minh Truong, A component architecture for an extensible, highly integrated context-aware computing infrastructure, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 9: Andy Harter , Andy Hopper , Pete Steggles , Andy Ward , Paul Webster, The anatomy of a context-aware application, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.59-68, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313476]
• 10: Karen Henricksen , Jadwiga Indulska, A Software Engineering Framework for Context-Aware Pervasive Computing, Proceedings of the Second IEEE International Conference on Pervasive Computing and Communications (PerCom'04), p.77, March 14-17, 2004
• 11: Glenn Judd , Peter Steenkiste, Providing Contextual Information to Pervasive Computing Applications, Proceedings of the First IEEE International Conference on Pervasive Computing and Communications, p.133, March 23-26, 2003
• 12: 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]
• 13: Aloysius K. Mok , Prabhudev Konana , Guangtian Liu , Chan-Gun Lee , Honguk Woo, Specifying Timing Constraints and Composite Events: An Application in the Design of Electronic Brokerages, IEEE Transactions on Software Engineering, v.30 n.12, p.841-858, December 2004 [doi>10.1109/TSE.2004.105]
• 14: Christian Nentwich , Licia Capra , Wolfgang Emmerich , Anthony Finkelstein, xlinkit: a consistency checking and smart link generation service, ACM Transactions on Internet Technology (TOIT), v.2 n.2, p.151-185, May 2002 [doi>10.1145/514183.514186]
• 15: Christian Nentwich , Wolfgang Emmerich , Anthony Finkelstein, Consistency management with repair actions, Proceedings of the 25th International Conference on Software Engineering, May 03-10, 2003, Portland, Oregon
• 16: Christian Nentwich , Wolfgang Emmerich , Anthony Finkelstein , Ernst Ellmer, Flexible consistency checking, ACM Transactions on Software Engineering and Methodology (TOSEM), v.12 n.1, p.28-63, January 2003 [doi>10.1145/839268.839271]
• 17: Insuk Park , Dongman Lee , Soon J. Hyun, A Dynamic Context-Conflict Management Scheme for Group-Aware Ubiquitous Computing Environments, Proceedings of the 29th Annual International Computer Software and Applications Conference (COMPSAC'05) Volume 1, p.359-364, July 26-28, 2005
• 18: Anand Ranganathan , Roy H. Campbell , Arathi Ravi , Anupama Mahajan, ConChat: A Context-Aware Chat Program, IEEE Pervasive Computing, v.1 n.3, p.51-57, July 2002 [doi>10.1109/MPRV.2002.1037722]
• 19: Steven P. Reiss, Incremental Maintenance of Software Artifacts, Proceedings of the 21st IEEE International Conference on Software Maintenance (ICSM'05), p.113-122, September 25-30, 2005 [doi>10.1109/ICSM.2005.54]
• 20: Manuel Román , Christopher Hess , Renato Cerqueira , Anand Ranganathan , Roy H. Campbell , Klara Nahrstedt, A Middleware Infrastructure for Active Spaces, IEEE Pervasive Computing, v.1 n.4, p.74-83, October 2002 [doi>10.1109/MPRV.2002.1158281]
• 21: Albrecht Schmidt , Kofi Asante Aidoo , Antti Takaluoma , Urpo Tuomela , Kristof Van Laerhoven , Walter Van de Velde, Advanced Interaction in Context, Proceedings of the 1st international symposium on Handheld and Ubiquitous Computing, p.89-101, September 27-29, 1999, Karlsruhe, Germany
• 22: João Pedro Sousa , David Garlan, Aura: an Architectural Framework for User Mobility in Ubiquitous Computing Environments, Proceedings of the IFIP 17th World Computer Congress - TC2 Stream / 3rd IEEE/IFIP Conference on Software Architecture: System Design, Development and Maintenance, p.29-43, August 25-30, 2002
• 23: Roy Want , Andy Hopper , Veronica Falcão , Jonathan Gibbons, The active badge location system, ACM Transactions on Information Systems (TOIS), v.10 n.1, p.91-102, Jan. 1992 [doi>10.1145/128756.128759]
• 24: Chang Xu , S. C. Cheung, Inconsistency detection and resolution for context-aware middleware support, Proceedings of the 10th European software engineering conference held jointly with 13th ACM SIGSOFT international symposium on Foundations of software engineering, September 05-09, 2005, Lisbon, Portugal
• 25: Xu, C. and Cheung, S.C. Incremental Context Consistency Checking. Technical Report HKUST-CS05-15. Department of Computer Science, Hong Kong University of Science and Technology, Hong Kong, China, Oct 2005.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification
          Subjects: Validation

General Terms:
Algorithms, Performance, Theory, Verification

Keywords:
context management, incremental consistency checking, pervasive computing