ON RANDOMIZATION IN SEQUENTIAL AND DISTRIBUTED ALGORITHMS

Rajiv Gupta

doi:10.1145/174666.174667

Return

ON RANDOMIZATION IN SEQUENTIAL AND DISTRIBUTED ALGORITHMS

1994-03-01

Rajiv Gupta

Scott A. Smolka

Shaji Bhaskar

DOI：10.1145/174666.174667

Original

Save

View PDF

Abstract

En 中文

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: 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 randomized algorithms. Finally, a comprehensive annotated bibliography is given.

Keywords:

ALGORITHMS

ANALYSIS OF ALGORITHMS

BYZANTINE AGREEMENT

COMPUTATIONAL COMPLEXITY

CSP

DINING PHILOSOPHERS PROBLEM

DISTRIBUTED ALGORITHMS

GRAPH ISOMORPHISM

HASHING

INTERACTIVE PROBABILISTIC PROOF SYSTEMS

LEADER ELECTION

MESSAGE ROUTING

NEAREST-NEIGHBORS PROBLEM

PERFECT HASHING

PRIMALITY TESTING

PROBABILISTIC TECHNIQUES

RANDOMIZED OR PROBABILISTIC ALGORITHMS

RANDOMIZED QUICKSORT

SEQUENTIAL ALGORITHMS

TRANSITIVE TOURNAMENTS

UNIVERSAL HASHING

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.