The analysis of Kademlia for random IDs

DOI10.1080/15427951.2015.1051674MaRDI QIDQ4985806zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Xing Shi Cai, Luc Devroye

Publication date 26 April 2021

Published in Internet Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1402.1191

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Internet topics (68M11) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Abstract: Kademlia is the de facto standard searching algorithm for P2P (peer-to-peer) networks on the Internet. In our earlier work, we introduced two slightly different models for Kademlia and studied how many steps it takes to search for a target node by using Kademlia's searching algorithm. The first model, in which nodes of the network are labelled with deterministic IDs, had been discussed in that paper. The second one, in which nodes are labelled with random IDs, which we call the Random ID Model, was only briefly mentioned. Refined results with detailed proofs for this model are given in this paper. Our analysis shows that with high probability it takes about $clogn$ steps to locate any node, where $n$ is the total number of nodes in the network and $c$ is a constant that does not depend on $n$.

Recommendations

• A probabilistic analysis of Kademlia networks
• Specifying and Analyzing the Kademlia Protocol in Maude
• scientific article; zbMATH DE number 1931792
• Optimizing random walk search algorithms in P2P networks
• Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks

Cites work

• A probabilistic analysis of Kademlia networks
• Accessing nearby copies of replicated objects in a distributed environment
• scientific article; zbMATH DE number 2080510 (Why is no real title available?)
• scientific article; zbMATH DE number 2080852 (Why is no real title available?)
• scientific article; zbMATH DE number 1931792 (Why is no real title available?)
• Probability. Theory and examples.
• Univariate Discrete Distributions

Cited in

(1)

• A probabilistic analysis of Kademlia networks

Describes a project that uses

Uses Software

• Chord
• Pastry

This page was built for publication: The analysis of Kademlia for random IDs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4985806)