James Aspnes and William Hurwood. Spreading rumors rapidly despite an adversary. Journal of Algorithms 26(2):386–411, February 1998. An earlier version appeared in Fifteenth Annual ACM Symposium on Principles of Distributed Computing, May 1996, pp. 143–151.
In the collect problem, n processors in a shared-memory system must each learn the values of n registers. We give a randomized algorithm that solves the collect problem in O(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 of O(n²) steps and the best previously known bound of O(n3/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 multi-use cooperative collect protocol that is O(log³ n)-competitive in the latency model of Ajtai et al and O(n1/2) log3/2 n)-competitive in the throughput model of Aspnes and Waarts; in both cases we show that the competitive ratios are within a polylogarithmic factor of optimal.
@article(AspnesH1998,
title="Spreading rumors rapidly despite an adversary",
author="James Aspnes and William Hurwood",
journal={Journal of Algorithms},
volume=26,
number=2,
pages={386--411},
month=feb,
year=1998
)