Detecting Opportunistic Cheaters in Volunteer Computing

For computationally expensive but parallelizable search problems distributed computing approaches based on volunteer computing can be used. Volunteering users spend their computation time to gain some sort of credit or for the sake of appearing in a ranking. Some of the users may try to gain reward without investing their computation time, i.e. they cheat. Hence, a cheat detection mechanism against such opportunistic cheaters is needed. The simplest approach is the recalculation of all results by multiple users followed by a voting. This simple approach is inefficient since it increases the computational complexity by the factor of the executed recalculations. In this paper we propose a new and efficient approach for cheat detection in search problems using a combination of sample testing and result aggregation. Our approach provides a high probability of detecting a cheating user while reducing the computational complexity using sample testing and the required bandwidth using result aggregation. In a limited range, one can compensate a small available bandwidth with more computations, thus providing a trade-off between bandwidth and computational complexity.