An efficient write-all algorithm for fail-stop PRAM without initialized memory (Q1208446): Difference between revisions

The aim of this paper is to bridge the gap between realizable parallel computers and the parallel random access machines [\textit{S. Fortune} and \textit{J. Wyllie}, Parallelism in random access machines, Proc. 10th ACM Symp. on Theory of Computing, 114-118 (1978)], with their unrealistic features of broad bandwidth memory access, processor synchrony and freedom from faults. The author eliminates the assumption that any amount of clear initial memory is available and presents fault-tolerant algorithms that can be used to simulate parallel random access machines using contaminated memory.