Limits on the Power of Parallel Random Access Machines
with Weak Forms
of Write Conflict Resolution
Faith E. Fich, Russel Impagliazzo, Bruce Kapron,
Valerie King, Miroslaw Kutylowski
The ROBUST PRAM is a concurrent-read concurrent-write (CRCW) parallel
random access machine in which any value might appear in a memory cell
as a result of a write conflict. This paper addresses the question of
whether a PRAM with such a weak form of write conflict resolution can
compute functions faster than the concurrent-read exclusive-write (CREW)
PRAM.
We prove a lower bound on the time required by the ROBUST PRAM to
compute Boolean functions in terms of the number of different values
each memory cell of the PRAM can contain and the degree of the function
when expressed as a polynomial over a finite field. In the case of 1-bit
memory cells, our lower bound for the problem of computing the OR of $n$
Boolean variables exactly matches Cook, Dwork, and Reischuk's upper
bound on the CREW PRAM We extend our result to obtain a lower bound
depending on the number of processors, for computing Boolean functions
on the ROBUST PRAM, even with memory cells of unbounded size. A
particular consequence is that the ROBUST PRAM with 2^{2^{O(sqrt{log
n})}} processors requires Omega (sqrt{log n}) steps to compute OR.
These results are obtained by defining a class of CRCW PRAMs, the fixed
PRAMs, all of which are at least as powerful as the ROBUST PRAM. We
prove our lower bounds using carefully chosen PRAMs from this class. We
also show the limitations of this technique by describing how, with
$n$-bit memory cells, any PRAM in this class can compute OR and, more
generally, simulate a PRIORITY PRAM in constant time.
Finally, we show that the ROBUST PRAM with 1-bit memory cells can
compute OR in O((\log^* n)^2) steps using O(n/(log^* n)^2) processors
with o(1) probability of error. Thus, adding randomization increases the
computational power of the ROBUST PRAM. This is in contrast to the
situation for the CREW PRAM, where adding randomization can at best
decrease time by a constant factor.