Self-testing/correcting protocols Conference Paper uri icon

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.

published proceedings

  • Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

author list (cited authors)

  • Franklin, M., Garay, J. A., & Yung, M

complete list of authors

  • Franklin, M||Garay, JA||Yung, M

publication date

  • January 1999