Complex Queries in P2P Networks with Resource-Constrained Devices

Structured Peer-to-Peer (P2P) systems are increasingly important for scalable data dissemination and search. At the same time, the importance of mobile devices like smartphones, PDAs, and netbooks for accessing and storing data is rapidly increasing. Current distributed approaches for resolving complex search queries, like multi-attribute and range queries, typically require multiple messages to resolve a single search request. This generates significant messaging overhead and increases the response latency. To reduce the messaging overhead and the search latency, some approaches like the Multi-Attribute Addressable Network (MAAN) use static replication. However, this results in high main memory requirements and large data transfers each time a device joins the P2P network. Those drawbacks can be tolerated for P2P networks that mainly consist of fixed, powerful nodes like PCs but are intolerable for resource-constrained nodes with high churn, like mobile devices. As mobile devices will play a significant role in accessing and distributing data in the future, we present an improved search mechanism for distributed resolution of complex queries on resourceconstrained devices. Compared to MAAN, our approach significantly reduces the memory footprint and bandwidth requirements (up to a factor of three – five, depending on the load model and the type of query in our sample scenario). At the same time, the good latency properties and the low messaging overhead of MAAN are retained on average. This is achieved via a dynamic replication scheme which introduces an adjustable trade-off between memory footprint and search latency. Thereby, our approach makes efficient, distributed resolution of complex queries on resource-constrained devices feasible, allowing such devices to live up to their important role in the future.