Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
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.
Alain Vaucher, Philippe Schwaller, et al.
AMLD EPFL 2022
Hannaneh Hajishirzi, Julia Hockenmaier, et al.
UAI 2011
Ryan Johnson, Ippokratis Pandis
CIDR 2013
Joxan Jaffar
Journal of the ACM