Randomized Speed-Ups in Parallel Computation (Classic Reprint) - Tapa blanda

Reseña del editor

Excerpt from Randomized Speed-Ups in Parallel Computation

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 0(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM.

About the Publisher

Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com

This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.