We initiate an investigation of general fault-tolerant distributed com
putation in the full-information model. In the full information model
no restrictions are made on the computational power of the faulty part
ies or the information available to them. (Namely, the faulty players
may be infinitely powerful and there are no private channels connectin
g pairs of honest players). Previous work in this model has concentrat
ed on the particular problem of simulating a single bounded-bias globa
l coin ip (e.g., Ben-Or and Linial [Randomness and Computation, S. Mic
ali, ed., JAI Press, Greenwich, CT, 1989, pp. 91-115] and Alon and Nao
r [SIAM J. Comput., 22 (1993), pp. 403-417]). We widen the scope of in
vestigation to the general question of how well arbitrary fault-tolera
nt computations can be performed in this model. The results we obtain
should be considered as first steps in this direction. We present effi
cient two-party protocols for fault-tolerant computation of any bivari
ate function. We prove that the advantage of a dishonest player in the
se protocols is the minimum one possible (up to polylogarithmic factor
s). We also present efficient m-party fault-tolerant protocols for sam
pling a general distribution (m greater than or equal to 2). Such an a
lgorithm seems an important building block towards the design of effic
ient multiparty protocols for fault-tolerant computation of multivaria
te functions.