Evenly distributing combinatorial tasks in a peer-to-peer system

Abstract

This paper presents an algorithm to evenly distribute a combinatorial task to participating nodes in a peer-to-peer system. Subtasks divided by our algorithm can be independently computed and the size of each subtask is almost identical so that we can achieve optimal resource utilization, maximize throughput, minimize response time, and avoid unfair overload to some nodes. An algorithm to find similarity among user-generated contents is used as an example of combinatorial tasks. Using a real-world data obtained from YouTube contents, we measured the reduction in processing time achievable by cooperation with other peers in a peer-to-peer environment. The result shows that the processing time for combination tasks can be significantly reduced as the number of peers to accomplish the tasks is increased. ？ 2010 IEEE.