Friday, September 24, 2004
Scalable Percolation Search in Power Law Networks
[cond-mat/0406152] Scalable Percolation Search in Power Law Networks
"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, ... 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."
"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, ... 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."
0 Comments:
