Prediction of Parallel Speed-ups for Las Vegas Algorithms

Charlotte Truchet, Florian Richoux, Philippe Codognet

We propose a probabilistic model for the parallel execution of Las Vegas algorithms, i.e., randomized algorithms whose runtime might vary from one execution to another, even with t…