×

Toward understanding exclusive read. (English) Zbl 0697.68056

Summary: The ability of many processors to simultaneously read from the same cell of shared memory can give additional power to a parallel random access machine. A natural Boolean function of n variables is described, and it is shown that the expected running time of any probabilistic EROW PRAM computing this function is in \(\Omega\) (\(\sqrt{\log n})\), although it can be computed by a CROW PRAM in O(log log n) steps.

MSC:

68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68N25 Theory of operating systems
PDFBibTeX XMLCite
Full Text: DOI