Self-testing/correcting protocols
Conference Paper
Overview
Identity
Additional Document Info
View All
Overview
abstract
Springer-Verlag Berlin Heidelberg 1999. In this paper we suggest the notion of self-testing/correcting protocols. The work initiates the merge of distributed computing and the area of program checking introduced by Blum, and specifically employs extended notions from the work of Blum, Luby and Rubinfeld. In this setting, given a protocol P (a collection of programs on a network of n processors) which allegedly implements a distributed function f, a selftester for f is a (simpler) protocol which makes calls to P to estimate the probability that P when executed in a given environment is faulty (i.e., P and f differ in some of the outputs). A self-correcting protocol is another protocol which allows for the computation of f correctly on every input (with high probability) as long as P in the same type of environment is not too faulty. We first consider self-testing/correcting under a basic form of environmental malfunction, that of crash failures, and design a self-tester/corrector pair for protocols implementing the agreement function. Many distributed protocols can be designed on top of this primitive, and can be self tested/corrected whenever it can be. We then consider selftesting/ correcting under gossiping failures, and present a generic selftesting/ correcting pair that is privacy-preserving. The notion is basic in protocols where secrecy is an issue. A self-corrector for P is privacypreserving if it is private (with overwhelming probability) whenever P is private (with overwhelming probability). In the process of our study, we identify the basic components of a protocol self-testing utility library, which allows for the safe bootstrapping of the self-testing/correcting process.
