Computer Science – Networking and Internet Architecture
Scientific paper
2002-10-14
Computer Science
Networking and Internet Architecture
13 pages, 2 figures, preprint version
Scientific paper
We propose a new and easily-realizable distributed hash table (DHT) peer-to-peer structure, incorporating a random caching strategy that allows for {\em polylogarithmic search time} while having only a {\em constant cache} size. We also show that a very large class of deterministic caching strategies, which covers almost all previously proposed DHT systems, can not achieve polylog search time with constant cache size. In general, the new scheme is the first known DHT structure with the following highly-desired properties: (a) Random caching strategy with constant cache size; (b) Average search time of $O(log^{2}(N))$; (c) Guaranteed search time of $O(log^{3}(N))$; (d) Truly local cache dynamics with constant overhead for node deletions and additions; (e) Self-organization from any initial network state towards the desired structure; and (f) Allows a seamless means for various trade-offs, e.g., search speed or anonymity at the expense of larger cache size.
Roychowdhury Vwani
Sarshar Nima
No associations
LandOfFree
A Random Structure for Optimum Cache Size Distributed hash table (DHT) Peer-to-Peer design does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Random Structure for Optimum Cache Size Distributed hash table (DHT) Peer-to-Peer design, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Random Structure for Optimum Cache Size Distributed hash table (DHT) Peer-to-Peer design will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-412047