Limitations of the QRQW and EREW PRAM Models

We consider parallel random access machines (PRAMs) with restricted access to the shared memory resulting from handling congestion of memory requests. We study the (SIMD) QRQW PRAM model where multiple requests are queued and serviced one at a time. We also consider exclusive read exclusive write (EREW) PRAM and its modification obtained by adding a single bus. For the QRQW PRAMs we investigate the case when the machine can measure the duration of a single step. Even for such a (powerful) QRQW PRAM PARITY of n bits (PARITYn ) requires W(log n) time while OR of n bits can be computed deterministically in a constant time. On randomized QRQW PRAM the function PARITYn is still difficult. We prove a lower time bound W( p log n= log log n) for algorithms that succeed with probability 0:5 + ffl (ffl ? 0). These bounds show that implementing concurrent writes may degradate runtime of a CRCW PRAM algorithm. The simple 2-compaction problem is known to be hard for EREW PRAM. The s..