Parallel Algorithms with Processor Failures and Delays
Abstract
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 O(log sq N) overhead ratio.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1991
- Accession Number
- ADA242764
Entities
People
- Alex A. Shvartsman
- Jonathan F. Buss
- Paris C. Kanellakis
- Prabhakar L. Radge
Organizations
- Brown University