Deterministic Coin Tossing With Applications to Optimal Parallel List Ranking (Classic Reprint) - Softcover

Inhaltsangabe

This book presents new deterministic parallel algorithms for list ranking a problem commonly encountered when designing parallel algorithms. The bulk of the work on the subject to date has developed deterministic algorithms based on either linear-time serial algorithms, or O(log n) time parallel algorithms using n processors. This book makes significant headway, presenting new algorithms that achieve optimal speed-up for various processor configurations. The author provides a new deterministic coin tossing technique for breaking symmetric situations in a random-like fashion. This technique is applied to the list-ranking problem to devise an O(log n time algorithm using n/(log n) processors. Additionally, this book presents algorithms that achieve optimal speed-up for all practical purposes, as well as an algorithm that uses n processors to achieve a runtime of O(log n) time, disproving a longstanding conjecture in the field. The author's insights into deterministic parallel algorithms and their applications to the list-ranking problem are significant, and this book will be of great interest to researchers and practitioners working in parallel computing and algorithm design.

Die Inhaltsangabe kann sich auf eine andere Ausgabe dieses Titels beziehen.