.png){kind=icon}
.png){kind=icon}
Return
Combining shared-coin algorithms
.png){kind=icon}
PRE
AI
DOI：10.1016/j.jpdc.2009.08.005.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper shows that shared-coin algorithms can be combined to optimize several complexity measures, even in the presence of a strong adversary. By combining shared coins of Bracha and Rachman (1991) [10] and of Aspnes and Waarts (1996) [7], this yields a shared-coin algorithm, and hence, a randomized consensus algorithm, with O(n log(2) n) individual work and O(n(2) log n) total work, using single-writer registers. This improves upon each of the above shared coins (where the former has a high cost for individual work, while the latter reduces it but pays in the total work), and is currently the best for this model. Another application is to prove a construction of Saks, Shavit, and Woll (1991) [16], which combines a shared-coin algorithm that takes O(1) time in failure-free executions, with one that takes O(log n) time in executions where at most root n processes fail, and another one that takes O(n(3)/n-f) time in any other execution. (C) 2009 Elsevier Inc. All rights reserved.
Keywords:
Distributed computing
Shared memory
Randomized algorithms
Consensus
Shared coins
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
IF:
4
Papers:
3.8K
Citations:
4.8K