
The crcw pram with dynamic fail-stop errors is a faultprone multiprocessor model for which it is possible to control memory access redundancy while guaranteeing the reliability of efficient algorithms. Concurrent common reads and writes are necessary to handle dynamic faults and in this paper we show how to significantly decrease this concurrency and how to bound it in terms of the number of processor faults. We describe a low concurrency, efficient, and fault-tolerant algorithm for the Write- All primitive: “using ≤ N processors, write 1's into N locations”. This primitive serves as the basis for efficient faulttolerant simulations of algorithms written for fault-free prams on faultprone prams. For any dynamic failure pattern F, our algorithm has total write concurrency ≤¦F¦ and total read concurrency ≤7 ¦F¦log N, where ¦F¦ is the number of processor faults (e.g. no concurrency in a run without failures). Previous algorithms used Ω(N log N) concurrency even in the absence of faults. We also present an optimal fault-tolerant erew pram algorithm for Write-All when all processor faults are initial.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 6 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
