6th International ICST Conference on Broadband Communications, Networks, and Systems

Research Article

Random Node Sampling in Kademlia

Download829 downloads
        author={Zolt\^{a}n Nov\^{a}k and Zolt\^{a}n Pap},
        title={Random Node Sampling in Kademlia},
        proceedings={6th International ICST Conference on Broadband Communications, Networks, and Systems},
        keywords={Area measurement Environmental economics Informatics Load management Peer to peer computing Protocols Random media Sampling methods Statistical analysis Telecommunications},
  • Zoltán Novák
    Zoltán Pap
    Year: 2009
    Random Node Sampling in Kademlia
    DOI: 10.4108/ICST.BROADNETS2009.7239
Zoltán Novák1,*, Zoltán Pap2,*
  • 1: Department of Telecommunications and Media Informatics, Budapest University of Technology and Economics, H-1117, Magyar tudósok körútja 2, Budapest, HUNGARY Phone: (36)1-463-2225, Fax: (36) 1-463-3107
  • 2: Ericsson Telecomm. Hungary, H-1117, Irinyi J. u. 4-20, Budapest, HUNGARY
*Contact email: novak@tmit.bme.hu, zoltan.pap@ericsson.com


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.