Optimal Parallelization of Las Vegas Algorithms

TitleOptimal Parallelization of Las Vegas Algorithms
Publication TypeTechnical Report
Year of Publication1993
AuthorsLuby, M., & Ertel W.
Other Numbers829

Let A be a Las Vegas algorithm, i.e., A is a randomized algorithm that always produces the correct answer when it stops but whose running time is a random variable. In [1] a method was developed for minimizing the expected time required to obtain an answer from A using sequential strategies which simulate A as follows: run A for a fixed amount of time t_1, then run A independently for a fixed amount of time t_2 etc. The simulation stops if A completes its execution during any of the runs.In this paper, we consider parallel simulation strategies for this same problem, i.e., strategies where many sequential strategies are executed independently in parallel using a large number of processors. We present a close to optimal parallel strategy for the case when the distribution of A is known. If the number of processors is below a certain threshold, we show that this parallel strategy achieves almost linear speedup over the optimal sequential strategy. For the more realistic case where the distribution of A is not known, we describe a universal parallel strategy whose expected running time is only a logarithmic factor worse than that of an optimal parallel strategy. Finally, the application of the described parallel strategies to a randomized automated theorem prover confirms the theoretical results and shows that in most cases good speedup can be achieved up to hundreds of processors, even on networks of workstations.

Bibliographic Notes

ICSI Technical Report TR-93-041

Abbreviated Authors

M. Luby and W. Ertel

ICSI Publication Type

Technical Report