|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'506'133
Articles rated: 2609
26 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Scalable Percolation Search in Power Law Networks | | Nima Sarshar
; P.Oscar Boykin
; Vwani P. Roychowdhury
; | | Date: |
7 Jun 2004 | | Journal: | In Proceedings of Fourth International Conference on Peer-to-Peer Computing, pp. 2-9, 2004 | | Subject: | Disordered Systems and Neural Networks; Networking and Internet Architecture | cond-mat.dis-nn cs.NI | | Abstract: | We introduce a scalable searching algorithm for finding nodes and contents in random networks with Power-Law (PL) and heavy-tailed degree distributions. The network is searched using a probabilistic broadcast algorithm, where a query message is relayed on each edge with probability just above the bond percolation threshold of the network. We show that if each node caches its directory via a short random walk, then the total number of {em accessible contents exhibits a first-order phase transition}, ensuring very high hit rates just above the percolation threshold. In any random PL network of size, $N$, and exponent, $2 leq au < 3$, the total traffic per query scales sub-linearly, while the search time scales as $O(log N)$. In a PL network with exponent, $ au approx 2$, {em any content or node} can be located in the network with {em probability approaching one} in time $O(log N)$, while generating traffic that scales as $O(log^2 N)$, if the maximum degree, $k_{max}$, is unconstrained, and as $O(N^{{1/2}+epsilon})$ (for any $epsilon>0$) if $ k_{max}=O(sqrt{N})$. Extensive large-scale simulations show these scaling laws to be precise. We discuss how this percolation search algorithm can be directly adapted to solve the well-known scaling problem in unstructured Peer-to-Peer (P2P) networks. Simulations of the protocol on sample large-scale subnetworks of existing P2P services show that overall traffic can be reduced by almost two-orders of magnitude, without any significant loss in search performance. | | Source: | arXiv, cond-mat/0406152 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser Mozilla/5.0 AppleWebKit/537.36 (KHTML, like Gecko; compatible; ClaudeBot/1.0; +claudebot@anthropic.com)
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER