Deterministic simulations of prams on bounded degree networks

The problem of simulating a PRAM with n processors and memory size m ≥ n on an n-node bounded degree network is considered. A deterministic algorithm is presented that simulates an arbitrary PRAM step in O(log n log m)/log log n) time in the worst case on an expander-based network. By extending a previously established lower bound, it is shown that the proposed simulation is optimal whenever Ω(n^1+ε) ≤ m ≤ O(2^{(log n)(α)} ) for some positive real constants ε and α.