Parallel Algorithms with Processor Failures and Delays
BROWN UNIV PROVIDENCE RI DEPT OF COMPUTER SCIENCE
Pagination or Media Count:
We study efficient deterministic parallel algorithms on two models restartable fail-stop CRCW PRAMs and strongly asynchronous PRAMs. In the first model, synchronous processors are subject to arbitrary stop failures and restarts determined by an on-line adversary and involving loss of private but not shared memory the complexity measures are completed work where processors are charged for completed fixed-size update cycles and overhead ratio completed work amortized over necessary work and failure. In the second model, the result of the computation is a serialization of the actions of the processors determined by an on-line adversary the complexity measure is total work number of steps taken by all processors. Despite their differences the two models share key algorithmic techniques. We present new algorithms for the Write-All problem in which P processors write ones into an array of size N for these two models. These algorithms can be used to implement a simulation strategy for any N processor PRAM on a restartable fail-stop P processor CRCW PRAM such that it guarantees a terminating execution of each simulated N processor step, with Olog sq N overhead ratio.
- Computer Hardware