ON SYNCHRONOUS PARALLEL COMPUTATIONS WITH INDEPENDENT PROBABILISTIC CHOICE.

Published

Journal Article

This paper introduces probabilistic choice to synchronous parallel machine models; in particular parallel RAMs. The power of probabilistic choice in parallel computations is illustrated by parallelizing some known probabilistic sequential algorithms. The computational complexity of time, space, and processor bounded probabilistic parallel RAMs is characterized in terms of the computational complexity of probabilistic sequential RAMs. It is shown that parallelism uniformly speeds up time bounded probabilistic sequential RAM computations by nearly a quadratic factor. It is also shown that probabilistic choice can be eliminated from parallel computations by introducing nonuniformity.

Full Text

Duke Authors

Cited Authors

  • Reif, JH

Published Date

  • January 1, 1984

Published In

Volume / Issue

  • 13 / 1

Start / End Page

  • 46 - 56

International Standard Serial Number (ISSN)

  • 0097-5397

Digital Object Identifier (DOI)

  • 10.1137/0213004

Citation Source

  • Scopus