Paper Info
Title
Self-Testing/Correcting Protocols (Extended Abstract)
Abstract
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 self-tester 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 privacy-preserving 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.
Year
DOI
Venue
1999
10.1007/3-540-48169-9_19
DISC
Keywords
DocType
ISBN
generic selftesting,high probability,self-correcting protocol,extended abstract,protocol self-testing,basic form,basic component,extended notion,corrector pair,correcting protocols,overwhelming probability,protocol p
Conference
3-540-66531-5
Citations 
PageRank 
References 
2
0.42
17
Authors
3
Name
Order
Citations
PageRank
Matthew K. Franklin1959119.11
Juan A. Garay22785222.49
Moti Yung3120801152.41