Parallel hashing
Anna R. Karlin, Eli Upfal · Journal of the ACM · 1988
A central issue in the theory of parallel computation is the gap between the ideal models that utilize shared memory and the feasible models that consist of a bounded-degree network of processors sharing no common memory.This problem has been widely studied.Here a tight bound for the probabilistic complexity of this problem is established.The solution in this paper is based on a probabilistic scheme for implementing shared memory on a bounded-degree network of processors.This scheme, which we term parallel has/zing, enables n processors to store and retrieve an arbitrary set of n data items in O(logn) parallel steps.The items' locations are specified by a function chosen randomly from a small class of universal hash functions.A hash function in this class has a small description and can therefore be efficiently distributed among the processors.A deterministic lower bound for the point-to-point communication model is also presented.