Spreading Rumors Rapidly Despite an Adversary

In thecollect problem(M. Saks, N. Shavit, and H. Woll,in“Proceedings of the 2nd ACM–SIAM Symposium on Discrete Algorithms, 1991),nprocessors in a shared-memory system must each learn the values ofnregisters. We give a randomized algorithm that solves the collect problem inO(n log³ n) total read and write operations with high probability, even if timing is under the control of a content-oblivious adversary (a slight weakening of the usual adaptive adversary). This improves on both the trivial upper bound ofO(n²) steps and the best previously known bound ofO(n^3/2 log n) steps, and is close to the lower bound of Ω(n log n) steps. Furthermore, we show how this algorithm can be used to obtain a multiuse cooperative collect protocol that isO(log³ n)-competitive in the latency model of Ajtaiet al.(“Proceedings of the 33rd IEEE Symposium on Foundations of Computer Science,” 1994); andO(n^1/2 log^3/2 n)-competitive in the throughput model of Aspnes and Waarts (“Proceedings of the 28th ACM Symposium on Theory of Computing,” 1996). In both cases the competitive ratios are within a polylogarithmic factor of optimal.