Login
Computer Science @ Rochester
Thursday, April 28, 2005
10:00 AM
CSB 703
Ph.D. Thesis Proposal
Ming Zhong
University of Rochester
Algorithmic Study on Some Peer-to-Peer Network Problems: Peer Sampling, Load Balancing, and Search
Our research is mainly focused on a variety of key problems in peer-to-peer (p2p) networks, including peer sampling, load balancing, search, incentive mechanisms, and routing. The difficulty of these problems is due to the hardness of gathering and maintaining global knowledge in p2p networks with frequent structure changes. This proposal summarizes our previous research results and outlines future work.

For the problem of peer sampling, we propose a scalable non- uniform random membership management algorithm, which provides each node with a random membership subset with application- specified probability distributions. Our algorithm is the first non-uniform random membership management algorithm with proved convergence and bounded convergence time. Moreover, our algorithm does not put specific restrictions on the network topologies and thus has wide applicability.

One of the key issues for dynamic load balancing in p2p networks is to find hotspots (highly overloaded nodes) and reassign their loads to others. Based on load-based random walks, we propose a load balancing algorithm with much faster load imbalance reduction speed than previous p2p load balancing algorithms.

Current peer-to-peer full-text keyword search techniques fall into the following categories: document-based partitioning, keyword -based partitioning, hybrid indexing, and semantic search. We provide an overall performance evaluation and comparison of current p2p keyword search techniques on a dataset of 3.7 million web pages and 6.8 million queries, which is an order of magnitude larger than the datasets employed in previous studies (up to 528,543 web pages and 100,000 queries). Our evaluation results can serve as a guide for a user to choose p2p keyword search techniques based on specific system parameters, such as network size, the number of documents, and the number of queries per second.

The problems that we will address in the future include optimal p2p topology construction, random walk based p2p search, hidden p2p communities, and incentive mechanisms for un-cooperative p2p systems.