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.
