Efficient simulations of small shared memories on bounded degree networks

The problem of simulating a parallel random-access machine (PRAM) with n processors and memory size m ≥ n on an n-node bounded degree network (BDN) is considered. Since many of the more efficient PRAM algorithms use an amount of shared memory not much larger than the number of processors, the case in which m = o(n^{1 + ε}) is considered, and a deterministic solution to the simulation problem is presented. For m = n(log n)^O(1) the running time of O(log n log log n) is within a factor of O(log log n) of the lower bound imposed by the diameter of the network.