LAND: stretch (1 + ε) locality-aware networks for DHTs
Ittai Abraham, Dahlia Malkhi, Oren Dobzinski · Symposium on Discrete Algorithms · 2004
This paper proposes the first peer-to-peer network and lookup algorithm that for any 0 < e has worst case stretch bounded by 1 + e. 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.