About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of the ACM
Paper
Parallel Hashing: An Efficient Implementation of Shared Memory
Abstract
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. © 1988, ACM. All rights reserved.