Loading...
Please wait, while we are loading the content...
Similar Documents
The price of validity in dynamic networks
| Content Provider | CiteSeerX |
|---|---|
| Author | Garcia-Molina, Hector Motwani, Rajeev Bawa, Mayank Gionis, Aristides |
| Description | In Proc. SIGMOD ’04 |
| Abstract | Massive-scale self-administered networks like Peer-to-Peer and Sensor Networks have data distributed across thou-sands of participant hosts. These networks are highly dy-namic with short-lived hosts being the norm rather than an exception. In recent years, researchers have investigated best-eort algorithms to eciently process aggregate queries (e.g., sum, count, average, minimum and maximum) [6, 13, 21, 34, 35, 37] on these networks. Unfortunately, query se-mantics for best-eort algorithms are ill-dened, 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 algo-rithms are best-eort. We present a class of algorithms that guarantee validity in dynamic networks. Experiments on real-life and synthetic network topologies validate perfor-mance of our algorithms, revealing the hitherto unknown price of validity. 1. |
| File Format | |
| Access Restriction | Open |
| Subject Keyword | Dynamic Network Participant Host Guarantee Validity Correctness Condition Sensor Network Best-eort Algorithm Hitherto Unknown Price Query Se-mantics Massive-scale Self-administered Network Aggregate Query Synthetic Network Topology Short-lived Host Single-site Validity |
| Content Type | Text |
