Practical Verification of MapReduce Computation Integrity via Partial Re-execution
This addresses the issue of ensuring computation integrity for clients outsourcing big data processing to untrusted cloud providers, though it is an incremental improvement over existing verifiable computation techniques.
The paper tackles the problem of verifying the integrity of MapReduce computations outsourced to untrusted cloud services, presenting V-MR, a framework that uses partial re-execution to detect violations and identify malicious workers with small overhead.
Big data processing is often outsourced to powerful, but untrusted cloud service providers that provide agile and scalable computing resources to weaker clients. However, untrusted cloud services do not ensure the integrity of data and computations while clients have no control over the outsourced computation or no means to check the correctness of the execution. Despite a growing interest and recent progress in verifiable computation, the existing techniques are still not practical enough for big data processing due to high verification overhead. In this paper, we present a solution called V-MR (Verifiable MapReduce), which is a framework that verifies the integrity of MapReduce computation outsourced in the untrusted cloud via partial re-execution. V-MR is practically effective and efficient in that (1) it can detect the violation of MapReduce computation integrity and identify the malicious workers involved in the that produced the incorrect computation. (2) it can reduce the overhead of verification via partial re-execution with carefully selected input data and program code using program analysis. The experiment results of a prototype of V-MR show that V-MR can verify the integrity of MapReduce computation effectively with small overhead for partial re-execution.