Technical Report CS0682

Authors: O. Goldreich, S. Goldwasser, N. Linial
Abstract: We initiate an investigation of general fault-tolerant distributed computation in the {\em full-information} model. In the full information model no restrictions are made on the computational power of the faulty parties or the information available to them. (Namely, the faulty players may be infinitely powerful and there are no private channels connecting pairs of honest players). Previous works, in this model, have concentrated on the particular problem of simulating a single bounded-bias global coin flip (e.g., Ben-Or and Linial [4] and Alon and Naor [1]). We widen the scope of investigation to the general question of how well can arbitrary fault-tolerant computations be performed in this model. The results we obtain should be considered as first steps in this direction. We present efficient two-party protocols for fault-tolerant computation of any two-argument function. We prove that the influence of dishonest players in these protocols is the minimum one possible (up to polylogarithmic factors). We also present efficient $m$-party fault-tolerant protocols for sampling a general distribution $(m \geq 2)$.We present efficient $m$-party protocols for computation of any $m$-argument function, and prove for these protocols that for ``most'' functions, the influence of any $t$ dishonest players on the outcome of the protocol is the minimum one possible (up to polylogarithmic factors).
CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (, rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1991
To the main CS technical reports page

Computer science department, Technion