The price of validity in dynamic networks

被引:14
作者
Bawa, Mayank
Gionis, Aristides [1 ]
Garcia-Molina, Hector
Motwani, Rajeev
机构
[1] Univ Helsinki, Dept Comp Sci, FIN-00014 Helsinki, Finland
[2] Stanford Univ, Dept Comp Sci, Stanford, CA 94305 USA
关键词
peer-to-peer; sensor; aggregate queries; correctness criterion;
D O I
10.1016/j.jcss.2006.10.007
中图分类号
TP3 [计算技术、计算机技术];
学科分类号
0812 ;
摘要
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. (c) 2006 Elsevier Inc. All rights reserved.
引用
收藏
页码:245 / 264
页数:20
相关论文
共 39 条
[1]  
AGRAWAL D, 1997, P PODS
[2]  
ALBERT R, 1999, NATURE, V401
[3]  
Alon N., 1996, P STOC
[4]  
Balakrishnan H., 2001, P SIGCOMM
[5]  
BARABASI A, 1999, SCIENCE, V286
[6]  
Bonnet P., 2001, P MDM
[7]  
BOYD S, 2005, P IEEE INF
[8]  
CONSIDINE J, 2004, P ICDE
[9]  
DECOUTO D, 2002, P HOTNETS
[10]  
DEMERS A, 1987, P PODC