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.

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