The analysis of Kademlia for random IDs
From MaRDI portal
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 steps to locate any node, where is the total number of nodes in the network and is a constant that does not depend on .
Recommendations
- A probabilistic analysis of Kademlia networks
- Specifying and Analyzing the Kademlia Protocol in Maude
- Kademlia: A peer-to-peer information system based on the XOR metric
- 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
- Application-level multicast using content-addressable networks
- Kademlia: A peer-to-peer information system based on the XOR metric
- Pastry: Scalable, decentralized object location, and routing for large-scale peer-to-peer systems
- Probability. Theory and examples.
- Univariate Discrete Distributions
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)