On the Rout­ing of Kadem­lia-type Sys­tems

Abstract

The family of Kademlia-type systems represents the most efficient and most widely deployed class of Internet-scale distributed systems. Its success has caused plenty of large-scale measurements and simulation studies, and several improvements have been introduced. Kademlia’s use of parallel and nondeterministic lookups, however, so far has prevented any concise formal analysis. We introduce a comprehensive formal model of the routing of the entire family of systems that is validated against both simulations and real-world measurements. In particular, we extend our previous work by excluding the effect of churn into the model. Our evaluation additionally shows that several of the recent improvements to the protocol in fact are counterproductive and identify preferable designs with regard to routing overhead and robustness to failures.