Achieving Dynamic Workload Balancing for P2P Volunteer Computing

This paper argues that the decentralization feature of Peer-to-Peer (P2P) overlay is more suitable for Volunteer Computing (VC), compared to the centralized master/worker structure in terms of performance bottleneck and single point of failure. Based on the P2P overlay Chord, this paper focused on the design of a workload balancing protocol to coordinate VC. The goal of the protocol was to maximize overall speed-up against the heterogeneity and churn of volunteers. The roles of a facilitator and volunteers (peers) were defined, the key components were designed, including job, result and container. Distributed workload balancing algorithms were proposed to direct the workflow of the key roles for joining and leaving, job search and distribution and result collection. Criteria and metrics were proposed to evaluate the algorithms in regards to the effectiveness against churn and the overall speed-up against number of volunteers. Simulations were devised and completed upon the N-Queen Problem to measure these qualities. Conclusions confirmed that the results were on the right track.