One, Two, Three \dots Infinity: Lower Bounds for Parallel Computation

In this paper we compare the power of the two most commonly used concurrent-write models of parallel computation, the COMMON PRAM and the PRIORITY PRAM. These models differ in the way they resolve write conflicts. If several processors want to write into the same shared memory cell at the same time, in the COMMON model they have to write the same value. In the PRIORITY model, they may attempt to write different values; the processor with smallest index succeeds.

Authors

• Faith Ellen
• Friedhelm Meyer auf der Heide
• Prabhakar Ragde
• Avi Wigderson

Keywords

No keywords are indexed for this paper.