The price of validity in dynamic networks Export

@article{citeulike:2081825, abstract = {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.}, author = {Bawa, Mayank and Gionis, Aristides and Garcia-Molina, Hector and Motwani, Rajeev}, booktitle = {Special Issue: Database Theory 2004}, citeulike-article-id = {2081825}, citeulike-linkout-0 = {http://dx.doi.org/10.1016/j.jcss.2006.10.007}, citeulike-linkout-1 = {http://www.sciencedirect.com/science/article/B6WJ0-4MHPJ04-2/2/ec7db9487d4262ba0b012a703955eee6}, citeulike-linkout-2 = {http://dx.doi.org/http://dx.doi.org/10.1016/j.jcss.2006.10.007}, doi = {10.1016/j.jcss.2006.10.007}, journal = {Journal of Computer and System Sciences}, keywords = {p2p}, month = {May}, number = {3}, pages = {245--264}, posted-at = {2007-12-09 15:52:02}, priority = {2}, title = {The price of validity in dynamic networks}, url = {http://dx.doi.org/10.1016/j.jcss.2006.10.007}, volume = {73}, year = {2007} }

TY - JOUR ID - citeulike:2081825 L3 - citeulike-article-id:2081825 N2 - 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. IS - 3 JF - Journal of Computer and System Sciences EP - 264 TI - The price of validity in dynamic networks VL - 73 T2 - Special Issue: Database Theory 2004 SP - 245 KW - p2p AU - Bawa, Mayank AU - Gionis, Aristides AU - Garcia-Molina, Hector AU - Motwani, Rajeev PY - 2007/05// UR - http://dx.doi.org/10.1016/j.jcss.2006.10.007 ER -