We make two contributions to the theory of PRAM computation, focusing
on the problem of computing the Boolean OR (to which most basic proble
ms can be reconducted). First we critically discuss the ideal PRAM mod
el generally adopted to prove parallel time bounds, and introduce the
natural definition of simple PRAM. We prove that log(2) n steps are ne
eded to compute the OR of n bits in the CREW variant of this model, an
d that this bound is tight. This implies that some acclaimed ''surpris
ing'' results in PRAM theory depend strictly on the properties of the
model, and not on the computed function. As a second contribution we s
how how to simplify the most advanced known lower bound proof for comp
uting the OR. The new proof scheme does not introduce new results, but
is aimed to enhancing the comprehension of this difficult subject We
also justify a ''full information'' functioning, generally adopted wit
hout discussion. (C) 1997 Elsevier Science B.V.