Access Restriction

Author Gupta, Rajiv ♦ Smolka, Scott A. ♦ Bhaskar, Shaji
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©1994
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Byzantine agreement ♦ CSP ♦ Analysis of algorithms ♦ Computational complexity ♦ 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
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 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), 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.
ISSN 03600300
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 1994-03-01
Publisher Place New York
e-ISSN 15577341
Journal ACM Computing Surveys (CSUR)
Volume Number 26
Issue Number 1
Page Count 80
Starting Page 7
Ending Page 86

Open content in new tab

   Open content in new tab
Source: ACM Digital Library