Colloquium Details
Using Computers Without Trusting Them to Compute Correctly
Speaker: Michael Walfish, University of Texas at Austin
Location: Warren Weaver Hall 1302
Date: April 19, 2013, 11:30 a.m.
Host: Denis Zorin
Synopsis:
How can a machine specify a computation to another one and then, without executing the computation, check that the other machine carried it out correctly? And how can this be done without assumptions about the performer (replication, trusted hardware, etc.) or restrictions on the computation? This is the problem of _verified computation_, and it is motivated by the cloud and other third-party computing models. It has long been known that (1) this problem can be solved in theory using complexity-theoretic tools (interactive proofs and probabilistically checkable proofs (PCPs)) coupled with cryptography, and (2) the performance of these solutions is wildly impractical (trillions of CPU-years or more to verify simple computations).
I will describe several implemented systems that challenge the second piece of this folklore. These systems are based on two strands of theory: a PCP-based efficient argument [IKO CCC07] (whose performance we have improved by 20 orders of magnitude) and an interactive proof [GKR STOC08, CMT ITCS12] that we have refined. We have also built a compiler that takes as input a program written in a subset of C, chooses the best available protocol for the computation, and produces executables that implement the protocol entities. These systems apply to a range of computations; a demonstration application is verifiable MapReduce. While the performance of the systems is not ideal, they show that the theoretical machinery could a real tool for building actual systems.
Time permitting, I will talk about other projects in the realm of untrusted computing resources, including a distributed storage system that works even if _all_ of the machines misbehave.
Speaker Bio:
Michael Walfish is an assistant professor in the Computer Science Department at The University of Texas at Austin. His research interests are in systems, security, and networking. His honors include an Air Force Young Investigator Award, an NSF CAREER Award, a Sloan Research Fellowship, a Teaching Excellence Award from the UT College of Natural Sciences, the Intel Early Career Faculty Honor Program, and the UT Society for Teaching Excellence. He received his B.A. from Harvard summa cum laude and his Ph.D. from MIT, both in Computer Science
Notes:
In-person attendance only available to those with active NYU ID cards.