CheR: Cheating resilience in the cloud via smart resource allocation

Cloud computing offers unprecedented ways to split and offload the workload of parallel algorithms to remote computing nodes. However, such remote parties can potentially misbehave, for instance by providing fake computation results in order to save resources. In turn, these erroneous partial results can affect the timeliness and correctness of the overall outcome of the algorithm. The widely successful cloud approach increases the economic feasibility of leveraging computational redundancy to enforce some degree of assurance about the results. However, naïve solutions that dumbly replicate the same computation over several sets of nodes are not cost-efficient. In this paper, we provide several contributions as for the distribution of workload over (heterogeneous) cloud nodes. In particular, we first formalize the problem of computing a parallel function over a set of nodes; later, we introduce CheR (for Cheating Resilience), a novel approach based upon modelling the assignment of input elements to cloud nodes as a linear integer programming problem aimed at minimizing cost while being resilient against misbehaving nodes. Further, we describe the CheR approach in different scenarios and highlight the novelty with respect to other state-of-the-art solutions. Finally, we present and discuss some experimental results showing the viability and quality of our proposal. © 2014 Springer International Publishing Switzerland.