Consistency mechanisms for a distributed lookup service supporting mobile applications

ABSTRACT

This paper presents a general-purpose distributed lookup service, denoted Passive Distributed Indexing (PDI). PDI stores entries in form of (key, value) pairs in index caches located in each mobile device. Index caches are filled by epidemic dissemination of popular index entries. By exploiting node mobility, PDI can resolve most queries locally without sending messages outside the radio coverage of the inquiring node. Thus, PDI reduces network traffic for the resolution of keys to values. For keeping index caches coherent, configurable value timeouts implementing implicit invalidation and lazy invalidation caches implementing explicit invalidation are introduced. Inconsistency in index caches due to weak connectivity or node failure is handled by value timeouts. Lazy invalidation caches reduce the fraction of stale index entries due to modified data at the origin node. Similar to index caches, invalidation caches are filled by epidemic distributions of invalidation messages. Simulation results show that with the suitable integration of both invalidation mechanisms, more than 95% of results delivered by PDI index caches are up-to-date for the considered scenario.

REFERENCES

• 1: 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]
• 2: Alan Demers , Dan Greene , Carl Hauser , Wes Irish , John Larson , Scott Shenker , Howard Sturgis , Dan Swinehart , Doug Terry, Epidemic algorithms for replicated database maintenance, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.1-12, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41841]
• 3: K. Fall and K. Varadhan (editors), The ns-2 manual, Technical Report, The VINT Project, UC Berkeley, LBL, and Xerox PARC, 2003.
• 4: Efficient Peer-to-Peer Data Dissemination in Mobile Ad-Hoc Networks, Proceedings of the 2002 International Conference on Parallel Processing Workshops, p.152, August 18-21, 2002
• 5: Wendi Rabiner Heinzelman , Joanna Kulik , Hari Balakrishnan, Adaptive protocols for information dissemination in wireless sensor networks, Proceedings of the 5th annual ACM/IEEE international conference on Mobile computing and networking, p.174-185, August 15-19, 1999, Seattle, Washington, United States [doi>10.1145/313451.313529]
• 6: Katrina M. Hanna , Brian Neil Levine , R. Manmatha, Mobile Distributed Information Retrieval for Highly-Partitioned Networks, Proceedings of the 11th IEEE International Conference on Network Protocols, p.38, November 04-07, 2003
• 7: IEEE Computer Society LAN MAN Standards Committee, Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Standard 802.11-1997, New York, NY, 1997.
• 8: Abdelmajid Khelil , Christian Becker , Jing Tian , Kurt Rothermel, An epidemic model for information diffusion in MANETs, Proceedings of the 5th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 28-28, 2002, Atlanta, Georgia, USA [doi>10.1145/570758.570768]
• 9: Christoph Lindemann , Oliver P. Waldhorst, A Distributed Search Service for Peer-to-Peer File Sharing in Mobile Applications, Proceedings of the Second International Conference on Peer-to-Peer Computing, p.73, September 05-07, 2002
• 10: Internet Engeneering Task Force Working Group Mobile Ad hoc Networks (MANET). http://www.ietf.org/html.charters/ manet-charter.html.
• 11: P. Mockapetris, Domain Names - Concepts and Facilities, IETF Request for Comments 1034, 1987.
• 12: Maria Papadopouli , Henning Schulzrinne, Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501433]
• 13: M. Papadopouli and H. Schulzrinne, Performance of Data Dissemination and Message Relaying in Mobile Ad Hoc Networks, Technical Report CUCS-004-02, Columbia University, 2003. Under submission.
• 14: Sylvia Ratnasamy , Paul Francis , Mark Handley , Richard Karp , Scott Schenker, A scalable content-addressable network, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.161-172, August 2001, San Diego, California, United States
• 15: Ion Stoica , Robert Morris , David Karger , M. Frans Kaashoek , Hari Balakrishnan, Chord: A scalable peer-to-peer lookup service for internet applications, Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, p.149-160, August 2001, San Diego, California, United States
• 16: K. Sripanidkulchai, The Popularity of Gnutella Queries and its Implications on Scalability. Proc. O'Reilly Peer-to-Peer and Web Services Conf., 2001.
• 17: Beverly Yang , Hector Garcia-Molina, Comparing Hybrid Peer-to-Peer Systems, Proceedings of the 27th International Conference on Very Large Data Bases, p.561-570, September 11-14, 2001
• 18: Y. Xie and D. O'Hallaron, Locality in Search Engine Queries and Its Implications for Caching, Proc. IEEE INFOCOM 2002, New York, NJ, 2002.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed applications

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems
          Subjects: Distributed databases
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Design studies

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Search process

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
ad-hoc networked databases, consistency maintenance in weakly connected environments, data caching, epidemic algorithms for data dissemination