EREW

EREW, or Exclusive Read Exclusive Write, is a memory-access discipline used in the PRAM family of theoretical parallel computation models. It defines how a set of processors can access a shared global memory in a parallel step.

In an EREW PRAM, no memory cell may be accessed by more than one processor in a single step. Reads and writes are exclusive: at most one processor can read from a given cell and at most one processor can write to a given cell during the same time unit. Processors perform computations on private registers and synchronize through shared memory, but simultaneous access to the same location is forbidden.

EREW is the most restrictive widely studied PRAM variant, and it serves as a baseline for analyzing parallel algorithms. It is contrasted with CREW (Concurrent Read Exclusive Write), where multiple processors may read the same memory cell concurrently but writing remains exclusive, and CRCW (Concurrent Read Concurrent Write), where concurrent reads and writes are allowed under some conflict-resolution rules. These differences influence the design and analysis of parallel algorithms, with some problems requiring more steps on EREW than on CREW or CRCW.

The model is primarily a theoretical tool used in complexity theory and the study of parallel algorithms. It abstracts away hardware details such as caches and memory-coherence mechanisms to focus on fundamental limits of parallelism and coordination. While PRAM models like EREW provide insights, they do not directly map to real-world machines; they help researchers understand how memory access constraints impact achievable speedups in parallel computation.