Exploiting storage redundancy to speed up randomized shared memory simulations

AbstractAssume that a set U of memory locations is distributed among n memory modules, using some number a of hash functions h1,…,ha, randomly and independently drawn from a high-performance universal class of hash functions. Thus, each memory location has a copies. Consider the task of accessing b out of the a copies for each of given keys x1,…,xn ∈ U, b < a. The paper presents and analyses a simple process executing the above task on distributed memory machines (DMMs) with n processors. Efficient implementations are presented, implying - a simulation of an n-processor PRAM on an n-processor optical crossbar DMM with delay O(log log n),- a simulation as above on an arbitrary-DMM with delay O(log log nlog log log n),- an implementation of a static dictionary on an arbitrary-DMM with parallel access time O(log∗ n + log log nlog a), if a hash functions are used. In particular, an access time of O(log∗ n) can be reached if (log n)1log∗ n hash functions are used.We further prove a lower bound for executing the above process by any so-called simple access protocol, showing that our implementations are optimal