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.