ON RANDOMIZATION IN SEQUENTIAL AND DISTRIBUTED ALGORITHMS

Probabilistic, or randomized, algorithms are fast becoming as commonpl ace as conventional deterministic algorithms. This survey presents fiv e techniques that have been widely used in the design of randomized al gorithms. These techniques are illustrated using 12 randomized algorit hms-both sequential and distributed-that span a wide range of applicat ions, including: primality testing (a classical problem in number theo ry), universal hashing (choosing the hash function dynamically and at random), interactive probabilistic proof systems (a new method of prog ram testing), dining philosophers (a classical problem in distributed computing), and Byzantine agreement (reaching agreement in the presenc e of malicious processors). Included with each algorithm is a discussi on of its correctness and its computational complexity. Several relate d topics of interest are also addressed, including the theory of proba bilistic automata, probabilistic analysis of conventional algorithms, deterministic amplification, and derandomization of randomized algorit hms. Finally, a comprehensive annotated bibliography is given.