Randomized Speed-Ups in Parallel Computation (Classic Reprint)
Price not available for France
You can still browse on Amazon. Try another country above.
Book Details
Author(s)
Uzi Vishkin
Publisher
Forgotten Books
ISBN / ASIN
1332092985
ISBN-13
9781332092987
Marketplace
France 🇫🇷
Ratings & Reviews
No reviews yet — be the first!
No reviews yet.
Description
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.
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.
