usenix conference policies
You are here
Beehive: O(1) Lookup Performance for Power-Law Query Distributions in Peer-to-Peer Overlays
Structured peer-to-peer hash tables provide decentralization, self-organization, failure-resilience, and good worst-case lookup performance for applications, but suffer from high latencies (O(log N)) in the average case. Such high latencies prohibit them from being used in many relevant, demanding applications such as DNS. In this paper, we present a proactive replication framework that can provide constant lookup performance for common Zipf-like query distributions. This framework is based around a closed-form optimal solution that achieves O(1) lookup performance with low storage requirements, bandwidth overhead and network load. Simulations show that this replication framework can realistically achieve good latencies, outperform passive caching, and adapt efficiently to sudden changes in object popularity, also known as flash crowds. This framework provides a feasible substrate for high-performance, low-latency applications, such as peer-to-peer domain name service.
author = {Venugopalan Ramasubramanian and Emin Gun Sirer},
title = {Beehive: O(1) Lookup Performance for {Power-Law} Query Distributions in {Peer-to-Peer} Overlays},
booktitle = {First Symposium on Networked Systems Design and Implementation (NSDI 04)},
year = {2004},
address = {San Francisco, CA},
url = {https://www.usenix.org/conference/nsdi-04/beehive-o1-lookup-performance-power-law-query-distributions-peer-peer-overlays},
publisher = {USENIX Association},
month = mar
}
connect with us