Volunteer distributed computations utilize spare processor cycles of personal computers that are connected to the Internet. The related computation integrity concerns are commonly addressed by assigning tasks redundantly. Aside from the additional computational costs, a significant disadvantage of redundancy is its vulnerability to colluding adversaries. This paper presents a tunable redundancy-based task distribution strategy that increases resistance to collusion while significantly decreasing the associated computational costs. Specifically, our strategy guarantees a desired cheating detection probability regardless of the number of copies of a specific task controlled by the adversary. Though not the first distribution scheme with these properties, the proposed method improves upon existing strategies in that it requires fewer computational resources. More importantly, the strategy provides a practical lower bound for the number of redundantly assigned tasks required to achieve a given detection probability

The past few years have seen the development of distributed computing platforms designed to utilize the spare processor cycles of a large number of personal computers attached to the Internet in an effort to generate levels of computing power normally achieved only with expensive supercomputers. Such large scale distributed computations running in untrusted environments raise a number of security concerns, including the potential for intentional or unintentional corruption of computations, and for participants to claim credit for computing that has not been completed. This paper presents two strategies for hardening selected applications that utilize such distributed computations. Specifically, we show that carefully seeding certain tasks with precomputed data can significantly increase resistance to cheating (claiming credit for work not computed) and incorrect results. Similar results are obtained for sequential tasks through a strategy of sharing the computation of N tasks among K>N nodes. In each case, the associated cost is significantly less than the cost of assigning tasks redundantly.