The complexity of deterministic PRAM simulation on distributed memory machines

In this paper we present lower and upper bounds for the deterministic simulation of a Parallel Random Access Machine (PRAM) withn processors andm variables on a Distributed Memory Machine (DMM) withp 64n processors. The bounds are expressed as a function of the redundancyr of the scheme (i.e., the number of copies used to represent each PRAM variable in the DMM), and become tight for anym polynomial in n and r=\u398(1)