Optimal spot-checking to minimize the computation time in volunteer computing
Kan Watanabe, Masaru Fukushi, Susumu Horiguchi · Proceedings - IEEE International Parallel and Distributed Processing Symposium · 2008
This paper proposes an optimization technique for spot- checking to minimize the computation time of volunteer computing (VC) systems with malicious participants who return erroneous results. Credibility based voting with spot-checking is one of the most promising approaches to guaranteeing the computational correctness ofVC systems. There is an optimal value for the spot-check rate; that is, the increase of the spot-check rate reduces the necessary redundancy for voting, which in turn increases the computation time due to the spot-checking itself. From this tradeoff, the estimation of the optimal spot-check rate is therefore the major concern to minimize the computation time required for the credibility based voting. The key idea is to represent the mathematical expectation of the computation time as a function of the spot-check rate to obtain an estimate of the optimal spot-check rate before the computation. It is shown by Monte Carlo simulations that the proposed technique can always obtain an approximate estimate of the optimal spot-check rate and minimize the computation time with an uncertainty of 1 %.