Exploiting storage redundancy to speed up randomized shared memory simulations

This paper presents and analyses efficient implementations of a so-called direct process on distributed memory machines (DMMs) that yieldsa simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n),a simulation of an n-processor PRAM on an n-processor arbitrary DMM with delay O(log log n/log log log n),an implementation of a static dictionary on an n-processor arbitrary DMM with parallel access time of O(log*n).We further prove a lower bound for executing the above process, showing that our implementations are optimal.