Optimal spot-checking for delayed attack on desktop grid systems

This paper deals with an optimization problem of spot-checking to ensure reliability of Desktop Grid (DG) systems, in which some unreliable nodes (saboteurs) may perform delayed attack. In the delayed attack, saboteurs return correct results in the initial stage, and then start to return incorrect results afterward. The current sabotage-tolerance methods such as check-by-voting do not work well for the delayed attack, because they assume that sabotaging style does not change with time. As a counter measure to the delayed attack, this paper proposes a combined method of spot-checking and check-by-voting. Even if saboteurs start to return incorrect results in the delayed attack, spot-checking can detect such sabotaging and eliminate incorrect results. There is an optimal value for the spot-check rate q; that is, larger q reduces error rate of computations, which in turn decreases the throughput of the DG systems due to the spot-checking itself. Thus, we also propose a formula of estimating the minimal q that decreases the error rate to a given value or lower, regardless of the unknown parameters such as the period of the initial stage and sabotaging frequency. Simulation results show that obtained spot-check rate q by our formula is almost the same as the optimal value and is enough large to decrease the error rate less than the required level.