title: The Price of Validity in Dynamic Networks
creator: Bawa, Mayank
creator: Gionis, Aristides
creator: Garcia-Molina, Hector
creator: Motwani, Rajeev
subject: Distributed Systems
description: 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.
publisher: Stanford InfoLab
date: 2004-06
type: Techreport
type: NonPeerReviewed
format: application/pdf
identifier: http://ilpubs.stanford.edu:8090/643/1/2004-22.pdf
identifier: Bawa, Mayank and Gionis, Aristides and Garcia-Molina, Hector and Motwani, Rajeev (2004) The Price of Validity in Dynamic Networks. Technical Report. Stanford InfoLab.
relation: http://ilpubs.stanford.edu:8090/643/