INFORMATION BROADCASTING BY EXCLUSIVE-READ PRAMS

We consider the problem of copying information stored initially in a single memory cell by Exclusive Read Exclusive Write Parallel Random Access Machines (EREW PRAMs). We prove lower bounds for this problem and present algorithms matching them tightly (in many cases up to an additive constant). The bounds presented depend on the number of cells used and size of information copied. The lower bounds apply also to functions where a change of a single argument influences the output in many memory locations.