@gdmcbain

Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking

, and . Information and Control 70 (1): 32--53 (July 1986)

Abstract

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.

Links and resources

DOI:
10.1016/s0019-9958(86)80023-7
URL:
BibTeX key:
Cole1986Deterministic
search on:

Comments and Reviews  
(0)

There is no review or comment yet. You can write one!

Tags


Cite this publication