Finding OR in a noisy broadcast network

We consider a broadcast network of n processors in which each bit transmitt ed by each processor is received by each other processor via a noisy channe l. Each processor has a binary input, and the problem is to construct a rel iable distributed algorithm to determine whether at least one processor has the input 1. We show that this can be done with O(log* n) bits of communic ation from each processor, under an adversarial noise model. In this model, a processor receives a broadcasted bit correctly with some base probabilit y q. The adversary may choose to correct the values of corrupted messages, but may not corrupt the values of correctly received messages. (C) 2000 Pub lished by Elsevier Science B.V. All rights reserved.