AntiCheetah: Trustworthy computing in an outsourced (cheating) environment

The increasing need for performing expensive computations has motivated outsourced computing, as in crowdsourced applications leveraging worker cloud nodes. However, these outsourced computing nodes can potentially misbehave or fail. Exploiting the redundancy of nodes can help guaranteeing correctness and availability of results. This entails that reliable distributed computing can be achieved at the expense of convenience. In this paper, we provide a solution for a generic class of problems that distribute a parallel computation over a set of nodes where trustworthiness of the outsourced computation is important. In particular, we discuss AntiCheetah, an approach modeling the assignment of input elements to cloud nodes as a multi-round system. AntiCheetah is resilient to node cheating, even in scenarios where smart cheaters return the same fake values. To this end, cost-efficient redundancy is used to detect and correct anomalies. Furthermore, we discuss the benefits and pitfalls of the proposed approach over different scenarios, especially with respect to cheaters' behavior. Extensive experimental results are analyzed, showing the effectiveness and viability of our approach.