Fich, Faith E.; Wigderson, Avi Toward understanding exclusive read. (English) Zbl 0697.68056 SIAM J. Comput. 19, No. 4, 718-727 (1990). 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. Cited in 2 Documents MSC: 68Q05 Models of computation (Turing machines, etc.) (MSC2010) 68N25 Theory of operating systems Keywords:shared memory parallel computation; lower bounds; decision trees; EROW PRAM; CROW PRAM PDFBibTeX XMLCite \textit{F. E. Fich} and \textit{A. Wigderson}, SIAM J. Comput. 19, No. 4, 718--727 (1990; Zbl 0697.68056) Full Text: DOI