Parallel Algorithms with Processor Failures and Delays

✍ Scribed by Jonathan F. Buss; Paris C. Kanellakis; Prabhakar L. Ragde; Alex Allister Shvartsman

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 367 KB
• Volume: 20
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1996.0003

✦ Synopsis

We study efficient deterministic parallel algorithms on two models: restartable fail-stop CRCW PRAMs and asynchronous PRAMs. In the first model, synchronous processes 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 com-. Ž pleted fixed-size update cycles and o¨erhead ratio completed work amortized over . necessary work and failures . 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 the 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 execu-Ž 2 . tion of each simulated N processor step, with O log N overhead ratio, and