Xor-Overlay Topology Management beyond Kademlia
Erick Lavoie, Miguel Pupo Correia, Laurie Jane Hendren · 2017
Kademlia is a widely successful Distributed Hash Table (DHT) implementation, better known for its use in the BitTorrent protocol. In this paper, we revisit its overlay management separately from the DHT operations to allow it to be used with other distributed abstractions by providing an accurate and consistent view of the k-closest nodes to any given identifier. We then present invariants that avoid the irregularities that are necessary with the original k-bucket design and improve on later published solutions by not needing an additional parameter to tune. We then provide a specification of a distributed abstraction that provides the automatic management of routing tables using our invariants and a pseudo-code implementation of that abstraction. We finally sketch how our abstraction may be used for a security mechanism and how it could be combined with other known distributed abstractions to provide other services than file sharing in xor-based overlay networks enabling xor-based network overlays to go beyond their original Kademlia design.