Computer Science – Distributed – Parallel – and Cluster Computing
Scientific paper
2012-02-07
Computer Science
Distributed, Parallel, and Cluster Computing
17 pages, 6 figures, 3 tables
Scientific paper
As the cloud computing paradigm has gained prominence, the need for verifiable computation has grown increasingly urgent. The concept of verifiable computation enables a weak client to outsource difficult computations to a powerful, but untrusted, server. Protocols for verifiable computation aim to provide the client with a guarantee that the server performed the requested computations correctly, without requiring the client to perform the computations herself. By design, these protocols impose a minimal computational burden on the client. However, existing protocols require the server to perform a large amount of extra bookkeeping in order to enable a client to easily verify the results. Verifiable computation has thus remained a theoretical curiosity, and protocols for it have not been implemented in real cloud computing systems. Our goal is to leverage GPUs to reduce the server-side slowdown for verifiable computation. To this end, we identify abundant data parallelism in a state-of-the-art general-purpose protocol for verifiable computation, originally due to Goldwasser, Kalai, and Rothblum, and recently extended by Cormode, Mitzenmacher, and Thaler. We implement this protocol on the GPU, obtaining 40-120x server-side speedups relative to a state-of-the-art sequential implementation. For benchmark problems, our implementation reduces the slowdown of the server to factors of 100-500x relative to the original computations requested by the client. Furthermore, we reduce the already small runtime of the client by 100x. Similarly, we obtain 20-50x server-side and client-side speedups for related protocols targeted at specific streaming problems. We believe our results demonstrate the immediate practicality of using GPUs for verifiable computation, and more generally that protocols for verifiable computation have become sufficiently mature to deploy in real cloud computing systems.
Mitzenmacher Michael
Pfister Hanspeter
Roberts Mike
Thaler Justin
No associations
LandOfFree
Verifiable Computation with Massively Parallel Interactive Proofs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Verifiable Computation with Massively Parallel Interactive Proofs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Verifiable Computation with Massively Parallel Interactive Proofs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-578853