Spanning Trees for Distributed Search in P2P Systems

N.R. Kaushik and S.M. Figueira (USA)


P2P Systems, Distributed Search, Spanning Trees, Bino mial Trees, TopologyBased Binomial Trees.


Searching for data location in P2P systems is a message intensive task. Basically, a query needs to reach all the nodes in order to find the locations of a specified data. This search involves a broadcast, and an inappropriate broadcast strategy may not only lead to inefficient data sharing, but also directly affect the scalability of the P2P system. We propose the utilization of an ad-hoc spanning tree for distributed search in P2P systems. This spanning tree is built as an overlay network. We define algorithms to maintain the ad-hoc spanning tree, and we compare the search time obtained with the ad-hoc spanning tree with the time obtained with other structures used for broadcast ing in parallel and distributed systems. This comparison is done with an MPI emulation.

Important Links:

Go Back