James Aspnes, Hagit Attiya, and Keren Censor. Combining shared coin algorithms. Accepted to Journal of Parallel and Distributed Computing.
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 and of Aspnes and Waarts, this yields a shared coin algorithm, and hence, a randomized consensus algorithm, with O(n log² n) individual work and O(n² 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, which combines a shared coin algorithm that takes O(1) time in failure-free executions, with one that takes (log n) time in executions where at most √n process fail, and another one O((n³)/(n-f)) time in any other execution.
@unpublished{AspnesAC2008coins,
author = {James Aspnes and Hagit Attiya and Keren Censor},
title = {Combining shared coin algorithms},
month=dec,
year = 2008,
note = {Accepted to \emph{Journal of Parallel and Distributed Computing}}
}