On the power of concurrent-write PRAMs with read-only memory

AbstractWe study the complexity of concurrent-read concurrent-write PRAM models in which inputs are given in read-only memory accessible by all processors, and show that the method of write-conflict resolution can affect the power of such models. Specifically, we give a problem which the Priority model can solve in O(1) steps while the Arbitrary model requires Ω(log(nm)log log(nm)) steps, when both models have m cells of shared memory. In a similar fashion, we demonstrate an Ω(log log(nm)) separation between the Arbitrary and Common models, when both have n processors and m cells of shared memory