
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Dynamic Job Scheduling Method Based on Expected Probability of Completion of Voting in Volunteer Computing
Yuto MIYAKOSHI Shinya YASUDA Kan WATANABE Masaru FUKUSHI Yasuyuki NOGAMI
Publication
IEICE TRANSACTIONS on Information and Systems
Vol.E98D
No.12
pp.21322140 Publication Date: 2015/12/01 Publicized: 2015/09/15 Online ISSN: 17451361
DOI: 10.1587/transinf.2015PAP0027 Type of Manuscript: Special Section PAPER (Special Section on Parallel and Distributed Computing and Networking) Category: Grid System Keyword: parallel computing, desktop grids, probabilistic method, sabotagetolerance,
Full Text: PDF>>
Summary:
This paper addresses the problem of job scheduling in volunteer computing (VC) systems where each computation job is replicated and allocated to multiple participants (workers) to remove incorrect results by a voting mechanism. In the job scheduling of VC, the number of workers to complete a job is an important factor for the system performance; however, it cannot be fixed because some of the workers may secede in real VC. This is the problem that existing methods have not considered in the job scheduling. We propose a dynamic job scheduling method which considers the expected probability of completion (EPC) for each job based on the probability of worker's secession. The key idea of the proposed method is to allocate jobs so that EPC is always greater than a specified value (SPC). By setting SPC as a reasonable value, the proposed method enables to complete jobs without excess allocation, which leads to the higher performance of VC systems. We assume in this paper that worker's secession probability follows Weibulldistribution which is known to reflect more practical situation. We derive parameters for the distribution using actual trace data and compare the performance of the proposed and the previous method under the Weibulldistribution model, as well as the previous constant probability model. Simulation results show that the performance of the proposed method is up to 5 times higher than that of the existing method especially when the time for completing jobs is restricted, while keeping the error rate lower than a required value.

