×

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

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)
PDFBibTeX XMLCite
Full Text: DOI