Deterministic coin tossing with applications to optimal parallel list ranking

Richard Cole; Uzi Vishkin

doi:10.1016/S0019-9958(86)80023-7

Deterministic coin tossing with applications to optimal parallel list ranking

Richard Cole, Uzi Vishkin

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

The following problem is considered: given a linked list of length n, compute the distance from each element of the linked list to the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O(log n) time parallel algorithm using n processors. We present new deterministic parallel algorithms for the problem. Our strongest results are (1) O(log n log* n) time using n/(log n log* n) processors (this algorithm achieves optimal speed-up); (2) O(log n) time using n log^(k)n/log n processors, for any fixed positive integer k. The algorithms apply a novel "random-like" deterministic technique. This technique provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.

Original language	English (US)
Pages (from-to)	32-53
Number of pages	22
Journal	Information and Control
Volume	70
Issue number	1
DOIs	https://doi.org/10.1016/S0019-9958(86)80023-7
State	Published - Jul 1986

ASJC Scopus subject areas

General Engineering

Access to Document

10.1016/S0019-9958(86)80023-7

Cite this

@article{f3d0c047e53c4dcca01acd5b9401b669,

title = "Deterministic coin tossing with applications to optimal parallel list ranking",

abstract = "The following problem is considered: given a linked list of length n, compute the distance from each element of the linked list to the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O(log n) time parallel algorithm using n processors. We present new deterministic parallel algorithms for the problem. Our strongest results are (1) O(log n log* n) time using n/(log n log* n) processors (this algorithm achieves optimal speed-up); (2) O(log n) time using n log(k)n/log n processors, for any fixed positive integer k. The algorithms apply a novel {"}random-like{"} deterministic technique. This technique provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.",

author = "Richard Cole and Uzi Vishkin",

note = "Funding Information: * This research was partially supported by NSF Grant DCR-84-01633 and by an IBM faculty development award. t This research was supported by NSF grants NSF-DCR-8318874 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046 and by the Applied Mathematical Sciences subprogram of the office of Energy Research, U.S. Department of Energy, under Contract DE-AC02-76ER03077.",

year = "1986",

month = jul,

doi = "10.1016/S0019-9958(86)80023-7",

language = "English (US)",

volume = "70",

pages = "32--53",

journal = "Information and Control",

issn = "0019-9958",

publisher = "Elsevier Inc.",

number = "1",

}

TY - JOUR

T1 - Deterministic coin tossing with applications to optimal parallel list ranking

AU - Cole, Richard

AU - Vishkin, Uzi

N1 - Funding Information: * This research was partially supported by NSF Grant DCR-84-01633 and by an IBM faculty development award. t This research was supported by NSF grants NSF-DCR-8318874 and NSF-DCR-8413359, ONR Grant N00014-85-K-0046 and by the Applied Mathematical Sciences subprogram of the office of Energy Research, U.S. Department of Energy, under Contract DE-AC02-76ER03077.

PY - 1986/7

Y1 - 1986/7

N2 - The following problem is considered: given a linked list of length n, compute the distance from each element of the linked list to the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O(log n) time parallel algorithm using n processors. We present new deterministic parallel algorithms for the problem. Our strongest results are (1) O(log n log* n) time using n/(log n log* n) processors (this algorithm achieves optimal speed-up); (2) O(log n) time using n log(k)n/log n processors, for any fixed positive integer k. The algorithms apply a novel "random-like" deterministic technique. This technique provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.

AB - The following problem is considered: given a linked list of length n, compute the distance from each element of the linked list to the end of the list. The problem has two standard deterministic algorithms: a linear time serial algorithm, and an O(log n) time parallel algorithm using n processors. We present new deterministic parallel algorithms for the problem. Our strongest results are (1) O(log n log* n) time using n/(log n log* n) processors (this algorithm achieves optimal speed-up); (2) O(log n) time using n log(k)n/log n processors, for any fixed positive integer k. The algorithms apply a novel "random-like" deterministic technique. This technique provides for a fast and efficient breaking of an apparently symmetric situation in parallel and distributed computation.

UR - http://www.scopus.com/inward/record.url?scp=0022744154&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022744154&partnerID=8YFLogxK

U2 - 10.1016/S0019-9958(86)80023-7

DO - 10.1016/S0019-9958(86)80023-7

M3 - Article

AN - SCOPUS:0022744154

SN - 0019-9958

VL - 70

SP - 32

EP - 53

JO - Information and Control

JF - Information and Control

IS - 1

ER -

Deterministic coin tossing with applications to optimal parallel list ranking

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this