In the collect problem [32], n processors in a shared-memory system must each learn the values of n registers.We give a randomized algorithm that solves the coMect problem in O(n log3 n) total read and write operations with high probability, even if timing is under the control of a contentoblivious adversary (a slight weakening of the usual adap tive adversary).This improves on both the trivial upper bound of O(n2) steps and the best previously known bound of 0(n3/2 log n) steps, and is close to the lower bound of Q(rz log ta) steps.Furthermore, we show how this algorithm can be used to obtain a multi-use cooperative collect protocol that is O(log3 n)-competitive in the latency model of Ajtai et rd.[3] and O(nl /2 logsiz n)-competitive in the throughput model of Aspnes and Waarts [10]; in both cases we show that the competitive ratios are within a polylogarithmic factor of optimal.

We consider a dynamic fault diagnosis problem: there are n processors, to be tested in a series of rounds. In every testing round we use a directed matching to have some processors report on the status (good or faulty) of other processors. Also, in each round up to t processors may break down, and we may direct that up to t processors are repaired. We show that it is possible to limit the number of faulty processors to O(t log2 t), even if the system is run indefinitely. We present an adversary which shows that this bound is optimal.

Consider a set of n processors that can communicate with each other. Assume that each processor can be either "good" or "faulty". Also assume that the processors can test each other. We consider how to use parallel testing rounds to identify the faulty processors, given an upper bound t on their number. We prove that 4 rounds are necessary and sufficient when 2/spl radic/(2n)/spl les/0.03n (for n sufficiently large). Furthermore, at least 5 rounds are necessary when t/spl ges/0.49n (for n sufficiently large), and 10 rounds are sufficient when t<0.5n (for all n). (It is well known that no general solution is possible when t/spl ges/0.5n).