The probabilistic method yields deterministic parallel algorithms
R. Motwani, Joseph Seffi Naor, Moni Naor · 1989
A method is provided for converting randomized parallel algorithms into deterministic parallel algorithms. The approach is based on a parallel implementation of the method of conditional probabilities. Results obtained by applying the method to the set balancing problem, lattice approximation, edge-coloring graphs, random sampling, and combinatorial constructions are presented. The general form in which the method of conditional probabilities is applied sequentially is described. The reason why this form does not lend itself to parallelization are discussed. The general form of the case for which the method of conditional probabilities can be applied in the parallel context is given.>