On Randomization in Sequential and Distributed Algorithms

I returned, and saw under the sun, that the race is not to the swift, nor the battle to the strong, nezther yet bread to the wise, nor yet riches to men of understanding, nor yet favor to men of skdl; but tzme and chance happeneth to them all. Chaos umpu-e sits, And by decision more embrods the fray By which he reigns: next him high arbiter Chance governs all. EcclesLastes (King James Version) Paradwe Lost, John Milton 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 randomized algorithms. These techniques are illustrated using 12 randomized algorithms—both sequential and distributed—that span a wide range of applications, including: prLmalLty testing (a classical problem in number theory), universal hashing (choosing the hash function dynamically and at random), irzteractwe probabdwtLc proof systems (a new method of program testing), dining philosophers (a classical problem in distributed computing), and B.yzanttne 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 randomized algorithms. Finally, a comprehensive annotated bibliography is given