Publication: Search Algorithms for Unstructured Peer-to-Peer Networks
Due to scheduled power outages at multiple SHARCNET institutions, several clusters (angel, copper, guppy, mako, mosaic, orca, redfin and saw) as well as global /work are currently unavailable and will return to service no later than 1 pm. Monday May 2.
We will use this outage to perform some much needed maintenance on a number of critical systems.
Other clusters will remain up but any jobs that require access to /work will crash. Users should only submit jobs requiring access to /home and /scratch
|| By Area
|| By Year
Search Algorithms for Unstructured Peer-to-Peer Networks
Reza Dorrigiv, Alejandro Lopez-Ortiz, Pawel Pralat
||Proceedings of 32nd IEEE Conference on Local Computer Networks (LCN)
||We study the performance of several search algorithms on unstructured peer-to-peer networks, both using classic search algorithms such as flooding and random walk, as well as a new hybrid algorithm proposed in this paper. This hybrid algorithm first uses flooding to find sufficient number of nodes and then starts random walks from these nodes. We compare the performance of the search algorithms on several graphs corresponding to common topologies proposed for peer-to-peer networks. In particular, we consider binomial random graphs, regular random graphs, power-law graphs, and clustered topologies. Our experiments show that for binomial random graphs and regular random graphs all algorithms have similar performance. For power-law graphs, flooding is effective for small number of messages, but for large number of messages our hybrid algorithm outperforms it. Flooding is ineffective for clustered topologies in which random walk is the best algorithm. For these topologies, our hybrid algorithm provides a compromise between flooding and random walk. We also compare the proposed hybrid algorithm with the k-walker algorithm on power-law and clustered topologies. Our experiments show that while they have close performance on clustered topologies, the hybrid algorithm has much better performance on power-law graphs. We theoretically prove that flooding is effective for regular random graphs which is consistent with our experimental results.
Go to Random Graph Theory
Back to page 69 of list