Influence of Overlay Topology on Capability-Centered Decentralized Resource Scheduling in Volunteer Computing Environment

Current volunteer computing systems are essentially centralized systems, which lead to scalability and accessibility problems. The latest developments of volunteer computing introduce a new infrastructure based on P2P overlay topology. It facilitates more flexible and effective computing resource sharing by constructing P2P overlays among participants. Capability-centered resource scheduling is a new decentralized scheduling for the new volunteer computing environments, which is simple and lightweight. However, its effectiveness is influenced by the underlying overlay topologies. A theoretical analysis model is built in this paper, by which effectiveness of this decentralized scheduling method is evaluated. The model estimates expectations of searching hops as well as capability level of the final node located by the scheduling method under P2P overlay topologies with different degrees and cluster coefficients. The estimation is performed by iteration, which controls time complexity into O(n~(3)). Simulation study is also performed on different overlay topologies generated by 3 different topology-generating methods. The estimation results of theoretical analysis model coincide with simulation results well. Both results show that, capability-centered resource scheduling method works better in overlay topologies with smaller cluster coefficient and bigger average degrees.