Spreading rumors rapidly despite an adversary

In the collect problem [32], n processors in a shared-memory sys-tem must each learn the values of n registers. We give a randomized algorithm that solves the collect problem in O(n log 3 n) total read and write operations with high probability, even if timing is under the con-trol of a content-oblivious adversary (a slight weakening of the usual adaptive adversary). This improves on both the trivial upper bound of O(n 2) steps and the best previously known bound of O(