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

Vishkin, Uzi

Couverture souple

ISBN 10 : 1332871224 ISBN 13 : 9781332871223

Editeur : Forgotten Books, 2018

Synopsis

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.

Détails de l'édition

• Éditeur: Forgotten Books
• Date d'édition: 2018
• Langue: anglais
• ISBN 10: 1332871224
• ISBN 13: 9781332871223
• Reliure: Broché
• Nombre de pages: 27
• Coordonnées du fabricant: Copytech (UK) Ltd, Trading as Printondemand-worldwide.com; gpsr@podww.com; ; 9 Culley Court; Orton Southgate; Peterborough; Cambridgeshire; PE2 6WA; Royaume-Uni
• Personne responsable: Easy Access System Europe Oü, 16879218; +358405003575; gpsr.requests@easproject.com; ; Mustamäe tee 50; Tallinn; 10621; Estonie