This paper is concerned with the relative power of the two most popular concurrent-write models of parallel computation, the
PRIORITY PRAM [G], and the COMMON PRAM [K]. Improving the trivial and seemingly optimal
O(log
n) simulation, we show that one step of a PRIORITY machine can be simulated by
O(log
n/(log log
n)) steps of a COMMON machine with the same number of processors (and more memory). We further prove that this is optimal,
if processor communication is restricted in a natural way.
Key words Parallel random access machines - Write-conflict resolution - Lower bounds
Communicated by Jeffrey Scott Vitter.
Support for this research was provided by NSF Grants MCS-8402676 and MCS-8120790, DARPA Contract No. N00039-84-C-0089, an
IBM Faculty Development Award, and an NSERC postgraduate scholarship.