LAND: Stretch (1+ε) Locality Aware Networks for DHTs

Ittai Abraham ittaia@cs.huji.ac.il

Dahlia Malkhi dalia@cs.huji.ac.il

Oren Dobzinski orend@cs.huji.ac.il

Abstract

This paper proposes the first peer-to-peer network and lookup algorithm that for any 0 < ε has worst case stretch bounded by 1 + ε. The construction uses an expected logarithmic number of links. It is suitable for a very realistic class of metrics in which the only restriction on density is a growth-bound. It is completely decentralized and readily deployable in dynamic networks.

[SODA version pdf] [improves over the earlier TR version pdf]