Consistency mechanisms for a distributed lookup service supporting mobile applications

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.