Determining the Hop Count in Kademlia-type Systems

Abstract

—The family of Kademlia-type systems represents the most efficient and most widely deployed class of Internetscale distributed systems. However, prior research on these systems has mainly been restricted to analyzing deployed systems and suggesting improvements tailored to specific environments rather than exploiting the huge parameter space governing the routing performance. Concise analytic results are rare, due to the complexity of Kademlia’s parallel and non-deterministic lookups. This paper introduces the first comprehensive formal model of the routing for the entire family of Kademlia-type systems. We validate our model against simulations of both the BitTorrent Mainline DHT and eMule’s KAD implementation. The model allows a highly scalable comparison with respect to the hop distribution of different variations to the original protocol. In particular, we show that several of the recent improvements to the protocol in fact have been counterproductive with regard to routing efficiency.