Finding OR in a noisy broadcast network
We consider a broadcast network of n processors in which each bit transmitted by each processor is received by each other processor via a noisy channel. Each processor has a binary input, and the problem is to construct a reliable 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 communication from each processor, under an adversarial noise model. In this model, a processor receives a broadcasted bit correctly with some base probability q. The adversary may choose to correct the values of corrupted messages, but may not corrupt the values of correctly received messages. (C) 2000 Published by Elsevier Science B.V. All rights reserved.
distributed algorithms noisy computation agreement