[BGW88] Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation

Authors: Michael Ben-Or, Shafi Goldwasser, Avi Wigderson | Venue: STOC 1988 | Source

Abstract

Every function of $n$ inputs can be efficiently computed by a complete network of $n$ processors in such a way that:

If no faults occur, no set of size $t < n /2$ of players gets any additional information (other than the function value),
Even if Byzantine faults are allowed, no set of size $t < n /3$ can either disrupt the computation or get additional information.

Furthermore, the above bounds on $t$ are tight!

BibTeX

@inproceedings{BGW88,
  author    = {Michael Ben-Or and Shafi Goldwasser and Avi Wigderson},
  title     = {Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation},
  booktitle = {Proceedings of the 20th Annual ACM Symposium on Theory of Computing (STOC 1988)},
  pages     = {1--10},
  year      = {1988}
}