Efficient parallel algorithms on restartable fail-stop processors
Paris Christos Kanellakis, Alex Allister Shvartsman · 1991
We study efficient deterministic executions of parallel algorithms on restartable fail-stop CRCW PRAMs.We allow the PRAM processors to be subject to arbitrary stop failures and restarts, that are determined by an on-lineThe lower bound also applies to the expected completed work of randomized algorithms that are subject to on-line adversaries.Finally, we desribe a simple on-line adversary that causes inefficiency in many randomized algorithms.