James Aspnes, Hagit Attiya, and Keren Censor. Combining shared coin algorithms. Journal of Parallel and Distributed Computing 70(3):317–322, March 2010.
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.
@article{AspnesAC2010,
author = {James Aspnes and Hagit Attiya and Keren Censor},
title = {Combining shared coin algorithms},
month=mar,
year = 2010,
journal = {Journal of Parallel and Distributed Computing},
volume = 70,
number = 3,
pages = {317--322}
}