DETERMINISTIC SIMULATIONS OF PRAMS ON BOUNDED DEGREE NETWORKS

The problem of simulating a PRAM with n processors and memory size m g reater-than-or-equal-to n on an n-node bounded degree network is consi dered. A deterministic algorithm is presented that simulates an arbitr ary 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 O MEGA(n1+epsilon) less-than-or-equal-to m less-than-or-equal-to O(2(log n)alpha) for some positive real constants epsilon and alpha.