Startseite > Publikationen > Publikationen


Mahlmann, Peter;Janson, Thomas;Schindelhauer, Christian:

3nuts: A Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs.

tr-ri-09-309, Paderborn, Germany, Dez. 2009


Categorizing peer-to-peer networks from an algorithmic point of view the two extremes of the spectrum are unstructured networks and networks based on plain distributed hash tables (DHT). Unstructured networks stand out with their simplicity, robustness, and support for complex queries. Though, they lack efficient query algorithms providing guarantees. On the other hand, DHT based networks feature efficient lookup algorithms with typically logarithmic hop distance and provide simple and efficient load balancing. Yet, they are limited to exact match queries and in many cases hard to maintain under churn. In this paper we introduce the 3nuts peer-to-peer network. The aim of 3nuts is to combine unstructured networks and DHTs to overcome their individual shortcomings. This is achieved by cleverly combining self maintaining random networks for robustness, a search tree to allow range queries, and DHTs for load balancing. All network operations in 3nuts are local and distributed, i.e.~simple handshake operations maintain the network structure. Efficiency of load balancing, fast data access, and guaranteed robustness are proven by rigorous analysis. Furthermore, 3nuts allows to adopt the structure of the overlay to the physical network with help of local maintenance operations.




author = {Mahlmann, Peter and Janson, Thomas and Schindelhauer, Christian},
title = {3nuts: A Locality-Aware Peer-to-Peer Network Combining Random Networks, Search Trees, and DHTs},
number = {tr-ri-09-309},
institution = {Heinz Nixdorf Institut},
address = {Paderborn, Germany},
month = dec,
year = {2009},

BibTeX in die Zwischenablage kopieren