A Random Structure for Optimum Cache Size Distributed hash table (DHT) Peer-to-Peer design

Simple item page
dc.creatorSarshar, Nima
dc.creatorRoychowdhury, Vwani
dc.date2002-10-14
dc.date.accessioned2026-07-07T03:18:55Z
dc.date.available2026-07-07T03:18:55Z
dc.descriptionWe 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.
dc.description13 pages, 2 figures, preprint version
dc.identifierhttps://arxiv.org/abs/cs/0210010
dc.identifierhttp://arxiv.org/abs/cs/0210010
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/31312
dc.subjectNetworking and Internet Architecture
dc.subjectDistributed, Parallel, and Cluster Computing
dc.subjectH.3.3
dc.titleA Random Structure for Optimum Cache Size Distributed hash table (DHT) Peer-to-Peer design
dc.typetext

Files

Collections

arXiv