Towards a theory of nearly constant time parallel algorithms

TitleTowards a theory of nearly constant time parallel algorithms
Publication TypeConference Papers
Year of Publication1991
AuthorsGil J, Matias Y, Vishkin U
Conference NameFoundations of Computer Science, 1991. Proceedings., 32nd Annual Symposium on
Date Published1991/10//
Keywordscomputational complexity, Estimation, nearly constant time parallel algorithms, Parallel algorithms, positive numbers, randomization, running time, superfast optimal algorithms

It is demonstrated that randomization is an extremely powerful tool for designing very fast and efficient parallel algorithms. Specifically, a running time of O(lg* n) (nearly-constant), with high probability, is achieved using n/lg* n (optimal speedup) processors for a wide range of fundamental problems. Also given is a constant time algorithm which, using n processors, approximates the sum of n positive numbers to within an error which is smaller than the sum by an order of magnitude. A variety of known and new techniques are used. New techniques, which are of independent interest, include estimation of the size of a set in constant time for several settings, and ways for deriving superfast optimal algorithms from superfast nonoptimal ones