Verifying Massively Data Parallel Multi-Stage Computations

Data parallel, multi-stage computations occurring on a massive scale are difficult to verify. With the recent ad-vent of various parallel computing platforms [2, 4], and the resultant increased availability and accessibility of significant computational resources at a relatively eco-nomical price, more and more users are going to take advantage of the computational resources offered by the cloud [1]. It is also natural to assume that users are going to want some level of assurance about the correctness of the results of their computation. We attempt to form a generalized data flow model which captures the seman-tics of such massively parallel systems. We introduce a verification mechanism which is based on collecting commitments to the input and output data at each stage of the computation and then redundantly computing th