Abstract
Randomness is a critical resource in many computational scenarios, enabling solutions where deterministic ones are elusive or even provably impossible. However, the randomized solutions to these tasks assume access to a source of unbiased, independent coins. Physical sources of randomness, on the other hand, are rarely unbiased and independent although they do seem to exhibit somewhat imperfect randomness. This gap in modeling questions the relevance of current randomized solutions to computational tasks. Indeed, there has been substantial investigation of this issue in complexity theory in the context of the applications to efficient algorithms and cryptography.
In this paper, we seek to determine whether imperfect randomness, modeled appropriately, is “good enough” for distributed algorithms. Namely can we do with imperfect randomness all that we can do with perfect randomness, and with comparable efficiency ? We answer this question in the affirmative, for the problem of Byzantine agreement. We construct protocols for Byzantine agreement in a variety of scenarios (synchronous or asynchronous networks, with or without private channels), in which the players have imperfect randomness. Our solutions are essentially as efficient as the best known randomized agreement protocols, despite the defects in the randomness.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barak, B., Impagliazzo, R., Wigderson, A.: Extracting randomness using few independent sources. In: FOCS, pp. 384–393 (2004)
Ben-Or, M.: Another advantage of free choice: Completely asynchronous agreement protocols (extended abstract). In: PODC, pp. 27–30 (1983)
Ben-Or, M., Pavlov, E.: Byzantine agreement in the full-information non-adaptive model (unpublished manuscript)
Bracha, G.: An asynchronous [(n-1)/3]-resilient consensus protocol. In: PODC, pp. 154–162 (1984)
Canetti, R., Rabin, T.: Fast asynchronous byzantine agreement with optimal resilience. In: STOC, pp. 42–51 (1993)
Chor, B., Coan, B.A.: A simple and efficient randomized byzantine agreement algorithm. IEEE Trans. Software Eng. 11(6), 531–539 (1985)
Chor, B., Goldreich, O.: Unbiased bits from sources of weak randomness and probabilistic communication complexity. In: FOCS, pp. 429–442 (1985)
Dodis, Y., Oliveira, R.: On extracting private randomness over a public channel. In: Arora, S., Jansen, K., Rolim, J.D.P., Sahai, A. (eds.) RANDOM 2003 and APPROX 2003. LNCS, vol. 2764, pp. 252–263. Springer, Heidelberg (2003)
Dodis, Y., Ong, S.J., Manoj, P., Sahai, A.: On the (im)possibility of cryptography with imperfect randomness. In: FOCS, pp. 196–205 (2004)
Dodis, Y., Spencer, J.: On the (non)universality of the one-time pad. In: FOCS, p. 376 (2002)
Dwork, C., Shmoys, D.B., Stockmeyer, L.J.: Flipping persuasively in constant time. SIAM J. Comput. 19(3), 472–499 (1990)
Elias, P.: The efficient construction of an unbiased random sequence. Ann. Math. Statist. 43(3), 865–870 (1972)
Feldman, P.: Asynchronous byzantine agreement in expected constant number of rounds (unpublished manuscript)
Feldman, P., Micali, S.: An optimal probabilistic protocol for synchronous byzantine agreement. SIAM J. Comput. 26(4), 873–933 (1997)
Fischer, M.J., Lynch, N.A., Paterson, M.: Impossibility of distributed consensus with one faulty process. In: PODS, pp. 1–7 (1983)
Garay, J.A., Moses, Y.: Fully polynomial byzantine agreement for > processors in + 1 rounds. SIAM J. Comput. 27(1), 247–290 (1998)
Goldwasser, S., Vaikuntanathan, V.: Distributed computing with imperfect randomness part ıı (manuscript) (in preparation)
Pease, M., Shostak, R., Lamport, L.: Reaching agreement in the presence of faults. Journal of the ACM 27, 228–234 (1980)
Rabin, M.O.: Randomized byzantine generals. In: FOCS, pp. 403–409 (1983)
Raz, R.: Extractors with weak random seeds. In: STOC (to appear, 2005)
Santha, M., Vazirani, U.V.: Generating quasi-random sequences from slightly-random sources. In: FOCS, Singer Island, pp. 434–440 (1984)
Vazirani, U.V.: Towards a strong communication complexity theory or generating quasi-random sequences from two communicating slightly-random sources (extended abstract). In: STOC, pp. 366–378 (1985)
von Neumann, J.: Various techniques for use in connection with random digits. In: von Neumann’s Collected Works, vol. 5, pp. 768–770. Pergamon, Oxford (1963)
Zuckerman, D.: General weak random sources. In: FOCS 1990, pp. 534–543 (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Goldwasser, S., Sudan, M., Vaikuntanathan, V. (2005). Distributed Computing with Imperfect Randomness. In: Fraigniaud, P. (eds) Distributed Computing. DISC 2005. Lecture Notes in Computer Science, vol 3724. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11561927_22
Download citation
DOI: https://doi.org/10.1007/11561927_22
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-29163-3
Online ISBN: 978-3-540-32075-3
eBook Packages: Computer ScienceComputer Science (R0)