# An Insight on PRAM Computational Bounds

We make two contributions to the theory of PRAM computation, focusing on
the problem of computing the Boolean OR (to which most
basic problems can be reconducted).
First we critically discuss the ideal PRAM model generally adopted to
prove parallel time bounds, and introduce the natural definition
of simple PRAM. We prove that log(base 2) n
steps are needed to compute the OR of n bits in the CREW variant of
this model, and that this bound is tight.
This implies that some acclaimed "surprising" results in PRAM theory
depend strictly on the properties of the model, and not on the
computed function. As a second contribution we show how to simplify
the most advanced known lower bound proof for computing 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 without discussion.