Combining shared-coin algorithms

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(nlog2n)O(nlog2n) individual work and O(n2logn)O(n2logn) 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)O(1) time in failure-free executions, with one that takes O(logn)O(logn) time in executions where at most n processes fail, and another one that takes O(n3n−f) time in any other execution.