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.