Percolation search in power law networks: making unstructured peer-to-peer networks scalable
N. Sarshar, P. Oscar Boykin, Vwani Roychowdhury · 2004
We introduce a scalable searching protocol for locating and retrieving content in random networks with Power-Law (PL) and heavy-tailed degree distributions. The proposed algorithm is capable of finding any content in the network with probability one in time O(logN), with a total traf-fic that provably scales sub-linearly with the network size, N. Unlike other proposed solutions, there is no need to as-sume that the network has multiple copies of contents; the protocol finds all contents reliably, even if every node in the network starts with a unique content. The scaling be-havior of the size of the giant connected component of a random graph with heavy tailed degree distributions under bond percolation is at the heart of our results. The perco-lation search algorithm can be directly applied to make un-structured Peer-to-Peer (P2P) networks, such as Gnutella, Limewire and other file-sharing systems (which naturally display heavy-tailed degree distributions and scale-free net-work structures), scalable. For example, simulations of the protocol on the limewire crawl number 5 network[12], con-sisting of over 65,000 links and 10,000 nodes, shows that even for this snapshot network, the traffic can be reduced by a factor of at least 100, and yet achieve a hit-rate greater than 90%. 1