Separation and lower bounds for ROM and nondeterministic models of parallel computation (Q1098633)

The paper contains a collection of separation results between variants of the CRCW-PRAM model of parallel computation having a shared memory of size m where m is relatively small. The variants differ in the way they handle write conflicts: In a COMMON(m) all processors attempting to write into the same location write the same value, in an ARBITRARY(m) an arbitrary processor succeeds, and in a PRIORITY(m) the one with minimum index. Furthermore, the input \((x_ 1,...,x_ n)\) may be in a shared read-only memory (variant with ROM) or it may be distributed such that processor P(i) knows only \(x_ i\) (variant without ROM). It is shown that with respect to the computation of relatively simple functions there are tight \(\Omega\) (log n/log(m\(+1))\) gaps between a COMMON(m) with ROM and n a processors \((a<2)\) and an ARBITRARY(1) (with or without ROM) and between an ARBITRARY(m) with ROM and a PRIORITY(1) (with or without ROM). In addition to these separation results a lower bound of \(\Omega\) (log log n) and an upper bound of \(O(n^{1/3})\) is proved for the nondeterministic computation of the parity function on a PRIORITY(1) with ROM and a tight lower bound of \(\Omega\) (\(\sqrt{n})\) for the nondeterministic computation on a PRIORITY(1) without ROM. The paper is worth reading mainly because of the quite sophisticated lower bound proofs (which might have been improved by the choice of a more suggestive notation).