Rajiv Gupta
GE Corporate R&D KW-C313, P.O. Box 8 Schenectady, NY 12301 USA
Scott A. Smolka
Dept. of Computer Science SUNY at Stony Brook Stony Brook, NY 11794 USA
Shaji Bhasar
Bell Northern Research 35 Davis Drive Res. Triangle Park, NC 27709 USA
Abstract:
Probabilistic, or randomized, algorithms are fast becoming as commonplace as conventional deterministic algorithms. This survey presents five techniques that have been widely used in the design of probabilistic algorithms. These techniques are illustrated using twelve probabilistic algorithms — both sequential and distributed — that span a wide range of applications, including: primality testing (a classical problem in number theory), universal hashing (choosing the hash function dynamically and at random), interactive probabilistic proof systems (a new method of program testing), dining philosophers (a classical problem in distributed computing), and byzantine agreement (reaching agreement in the presence of malicious processors). Included with each algorithm is a discussion of its correctness and its computational complexity. Several related topics of interest are also addressed, including the theory of probabilistic automata, probabilistic analysis of conventional algorithms, deterministic amplification, and derandomization of probabilistic algorithms. Finally, a comprehensive annotated bibliography is given.
This is the complete version of the bibtex file from the paper "On Randomization in Sequential and Distributed Algorithms" by Rajiv Gupta, Scott A. Smolka, and Shaji Bhasar which appeared in Computing Surveys, Vol. 26, No. 1, March 1994 (pp. 7-86).
