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, Topology-Based 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