The price of validity in dynamic networks

作者:

Highlights:

摘要

Massive-scale self-administered networks like Peer-to-Peer and Sensor Networks have data distributed across thousands of participant hosts. These networks are highly dynamic with short-lived hosts being the norm rather than an exception. In recent years, researchers have investigated best-effort algorithms to efficiently process aggregate queries (e.g., sum, count, average, minimum and maximum) on these networks. Unfortunately, query semantics for best-effort algorithms are ill-defined, making it hard to reason about guarantees associated with the result returned. In this paper, we specify a correctness condition, Single-Site Validity, with respect to which the above algorithms are best-effort. We present a class of algorithms that guarantee validity in dynamic networks. Experiments on real-life and synthetic network topologies validate performance of our algorithms, revealing the hitherto unknown price of validity.

论文关键词:Peer-to-Peer,Sensor,Aggregate queries,Correctness criterion

论文评审过程:Received 22 December 2004, Revised 2 May 2006, Available online 8 December 2006.

论文官网地址:https://doi.org/10.1016/j.jcss.2006.10.007