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 [6], 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.

http://i.stanford.edu/pub/cstr/reports/cs/tr/88/1240/CS-TR-88-1240.pdf