Relations between concurrent-write models of parallel computation. (English) Zbl 0652.68065

Fich, Faith E.; Ragde, Prabhakar; Wigderson, Avi

SIAM J. Comput. 17, No. 3, 606-627 (1988).

Shared memory models of parallel computation (e.g., parallel RAMs) that allow simultaneous read/write access are very natural and already widely used for parallel algorithm design. The various models differ from each other in the mechanism by which they resolve write conflicts. To understand the effect of these communication primitives on the power of parallelism, we extensively study the relationship between four such models that appear in the literature, and prove nontrivial separations and simulation results among them.

MSC:

68Q05

Models of computation (Turing machines, etc.) (MSC2010)

Keywords:

lower bounds; parallel random access machines; parallel computation; parallel RAMs; parallel algorithm