Randomized speed-ups in parallel computation

Publisher Website
Google Scholar
Abstract
The following problem is considered: given a linked list of length n, compute the distance of each element of the linked list from the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O((nlog n)/p + log n) time parallel algorithm using p processors. A known conjecture states that it is impossible to design an O(log n) time deterministic parallel algorithm that uses only n/log n processors. We present three randomized parallel algorithms for the problem. One of these algorithms runs almost-surely in time of O(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM.

This publication has 0 references indexed in Scilit: