×

zbMATH — the first resource for mathematics

Deterministic coin tossing with applications to optimal parallel list ranking. (English) Zbl 0612.68044
The following problem is considered: given a linked list of length n, compute the distance from each element of the linked list to the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O(log n) time parallel algorithm using n processors. We present new deterministic parallel algorithms for the problem. Our strongest results are (1) O(log n log\({}^*n)\) time using n/(log n log\({}^*n)\) processors (this algorithm achieves optimal speed- up); (2) O(log n) time using n log\({}^{(k)}n/\log n\) processors, for any fixed positive integer k. The algorithms apply a novel ”random-like” deterministic technique. This technique provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.

MSC:
68Q25 Analysis of algorithms and problem complexity
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
PDF BibTeX XML Cite
Full Text: DOI