@Bibtex-file{Theory/ProbAlgs.bib,
  title =        "Bibliography on Randomization in Sequential and
                 Distributed Algorithms",
  author-1 =     "Rajiv Gupta",
  address-1 =    "GE Corporate R\&D\\ KW-C313, P.O. Box 8\\ Schenectady,
                 NY 12301\\ USA",
  author-2 =     "Scott A. Smolka",
  address-2 =    "Dept. of Computer Science\\ SUNY at Stony Brook\\
                 Stony Brook, NY 11794\\ USA",
  author-3 =     "Shaji Bhasar",
  address-3 =    "Bell Northern Research\\ 35 Davis Drive\\ Res.
                 Triangle Park, NC 27709\\ USA",
  supported =    "no",
  abstract =     "Probabilistic, or randomized, algorithms are fast
                 becoming as commonplace as conventional deterministic
                 algorithms. This \htmladdnormallink{survey}
                 {ftp://cs.sunysb.edu/pub/TechReports/smolka/ProbAlgs.ps.Z}
                 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: {\em
                 primality testing} (a classical problem in number
                 theory), {\em universal hashing} (choosing the hash
                 function dynamically and at random), {\em interactive
                 probabilistic proof systems} (a new method of program
                 testing), {\em dining philosophers} (a classical
                 problem in distributed computing), and {\em 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.",
  readme =       "This is the complete version of the bibtex file from
                 the paper {"}\htmladdnormallink{On Randomization in
                 Sequential and Distributed Algorithms}
                 {ftp://ftp.cs.sunysb.edu/pub/TechReports/smolka/ProbAlgs.ps.Z}{"}
                 by Rajiv Gupta, Scott A. Smolka, and Shaji Bhasar which
                 appeared in Computing Surveys, Vol.\ 26, No.\ 1, March
                 1994 (pp.\ 7-86).",
  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.",
}