Report Number: CS-TR-88-1240
Institution: Stanford University, Department of Computer Science
Title: On Separat1ng the EREW and CREW PRAM Models
Author: Gafni, E.
Author: Naor, J.
Author: Ragde, P.
Date: December 1988
Abstract: In , Snir proposed the Selection Problem (searching in a
sorted table) to show that the CREW PRAM is strictly more
powerful than the EREW PRAM. This problem defines a partial
function, that is, one that is defined only on a restricted
set of inputs. Recognizing whether an arbitrary input belongs
to this restricted set is hard for both CREW and EREW PRAMs.
The existence of a total function that exhibits the power of
the CREW model over the EREW model was an open problem. Here
we solve this problem by generalizing the Selection problem
to a Decision Tree problem which is defined on a full domain
and to which Snir's lower bound applies.