Bibliography on Randomization in Sequential and Distributed Algorithms

[   About   |  Browse   |   Statistics   ]

Number of references:	414	Last update:	June 1, 1994
Number of online publications:	0	Supported:	no
Most recent reference:	1994

Search the bibliography

Information on the Bibliography

Authors:

Rajiv Gupta
GE Corporate R&D
KW-C313, P.O. Box 8
Schenectady, NY 12301
USA

Scott A. Smolka
Dept. of Computer Science
SUNY at Stony Brook
Stony Brook, NY 11794
USA

Shaji Bhasar
Bell Northern Research
35 Davis Drive
Res. Triangle Park, NC 27709
USA

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 probabilistic algorithms. These techniques are illustrated using twelve probabilistic 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 probabilistic algorithms. Finally, a comprehensive annotated bibliography is given.

Keywords:

Randomized Algorithms, Sequential and Distributed Algorithms; Computational Complexity; Randomized Quicksort; Primality Testing; Transitive Tournaments; Hashing; Perfect Hashing; Universal Hashing; Nearest Neighbors Problem; Interactive Probabilistic Proof Systems; Graph Isomorphism; Dining Philosophers Problem; CSP; Leader Election; Message Routing; Byzantine Agreement.

Author Comments:

This is the complete version of the bibtex file from the paper "On Randomization in Sequential and Distributed Algorithms" by Rajiv Gupta, Scott A. Smolka, and Shaji Bhasar which appeared in Computing Surveys, Vol. 26, No. 1, March 1994 (pp. 7-86).

Browsing the bibliography

• Original source:

  ftp://ftp.cs.sunysb.edu... (Format: bibtex, compressed)

  Other sites:

  ftp://ftp.cs.sunysb.edu... (Format: postscript, compressed)
  

Bibliographic Statistics

Types:

inproceedings(202), article(173), book(19), techreport(9), incollection(5), manual(2), phdthesis(2), mastersthesis(1), misc(1)

Fields:

note(414), year(414), title(413), author(412), pages(354), booktitle(207), journal(173), volume(172), month(159), number(108), address(100), publisher(55), editor(14), institution(9), type(7), page(4), school(3), series(3), chapter(2), key(2), organization(2), howpublished(1)

Distribution of publication dates:

Please direct comments regarding the bibliography collection to <liinwwwa@ira.uka.de>. This page is part of the Computer Science Bibliography Collection. Copyright © 1994-2004, Alf-Christian Achilles. All Rights Reserved.