%0 Conference Paper %1 Vishkin:1984:RSP:800057.808686 %A Vishkin, Uzi %B Proceedings of the sixteenth annual ACM symposium on Theory of computing %C New York, NY, USA %D 1984 %I ACM %K algorithm de-bruijn parallel randomized %P 230--239 %R 10.1145/800057.808686 %T Randomized speed-ups in parallel computation %U http://doi.acm.org/10.1145/800057.808686 %X <par>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.</par> <par>We present three randomized parallel algorithms for the problem. One of these algorithms runs almost-surely in time of O(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM.</par> %@ 0-89791-133-4

@inproceedings{Vishkin:1984:RSP:800057.808686, abstract = {<par>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.</par> <par>We present three randomized parallel algorithms for the problem. One of these algorithms runs almost-surely in time of O(n/p + log nlog*n) using p processors on an exclusive-read exclusive-write parallel RAM.</par>}, acmid = {808686}, added-at = {2012-04-25T13:34:49.000+0200}, address = {New York, NY, USA}, author = {Vishkin, Uzi}, biburl = {https://www.bibsonomy.org/bibtex/29f79605dc9b398aba6a7ff5a63ee5f32/ytyoun}, booktitle = {Proceedings of the sixteenth annual ACM symposium on Theory of computing}, doi = {10.1145/800057.808686}, interhash = {a9922929bf59482d48d46eb8d1275ca1}, intrahash = {9f79605dc9b398aba6a7ff5a63ee5f32}, isbn = {0-89791-133-4}, keywords = {algorithm de-bruijn parallel randomized}, numpages = {10}, pages = {230--239}, publisher = {ACM}, series = {STOC '84}, timestamp = {2016-04-18T07:24:21.000+0200}, title = {Randomized speed-ups in parallel computation}, url = {http://doi.acm.org/10.1145/800057.808686}, year = 1984 }