EXPLOITING STORAGE REDUNDANCY TO SPEED-UP RANDOMIZED SHARED-MEMORY SIMULATIONS

Assume that a set U of memory locations is distributed among n memory modules, using some number a of hash functions h(1),...,h(a), randomly and independently drawn from a highperformance universal class of has h functions. Thus, each memory location has a copies. Consider the tas k of accessing b out of the a copies for each of given keys x(1),...,x (n) epsilon 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 simul ation of an n-processor PRAM on an n-processor optical crossbar DMM wi th delay O(log log n), a simulation as above on an arbitrary-DMM with delay O(log log n/log log log n), an implementation of a static dictio nary on an arbitrary-DMM with parallel access time O(logn + log log n /log a), if a hash functions are used. In particular, an access time o f O(log n) can be reached if (log n)(1/log)*(n) hash functions are us ed. We further prove a lower bound for executing the above process by any so-called simple access protocol, showing that our implementations are optimal.