TOWARDS DISTRIBUTED PROTOCOL SELF-TESTING/CORRECTING

Juan A. Garay, IBM T.J. Watson Research Center

Building on theory of {\em program result checkers} of Blum, Blum, Lubby and Rubinfeld introduced the notion of {\em self-testing/correcting programs}: Given a program $P$ which allegedly computes a function $f$, a self-tester for $f$ is a (simpler) program which makes calls to $P$ to estimate the probability that $P$ is faulty (i.e., $P$ and $f$ differ). A self-correcting program is another program which allows for the computation of $f$ correctly on every input (with high probability) as long as $P$ is not too faulty.

In this exploratory work, we propose an extension of the above notion to [\em distributed protocols} - a collection of programs, one for each node in a network of processors. In such an environment, the task of estimating the behavior of a given protocol is made harder by the fact that other things can go wrong during the execution of the protocol, such as processor failures, messages being lost, etc.

We consider the design of self-testing/correcting pairs for distributed agreement in a network susceptible to benign processor failures. We also consider the self-testing/correcting of protocols with the added requirement of privacy. (A protocol is $t$-private if any set of $t$ players cannot compute after the protocol more than they could jointly compute solely from their set of private inputs and outputs.)

(With Matt Franklin, Alain Mayer, and Moti Yung.)