Random node sampling in Kademlia

We present a novel distributed method for selecting random nodes uniformly in Kademlia DHT networks. The algorithm does not require any extension to the Kademlia protocol and can be applied to any Kademlia-type network. It is easily tunable with one parameter to set an appropriate tradeoff between the evenness of the distribution and time-message-complexity. The method may be used as a building block for network algorithms in areas such as load balancing, Byzantine agreement, fault recovery and statistical measurements.