Absfracf -Consider a broadcast network of N + 1 nodes in which each binary digit transmitted by each node is received by each other node via a binary symmetric channel of given transition probability. The errors on these channels are independent over transmitters, receivers, and time. Each node has a binary state, and the problem is to construct a distributed algorithm to find the parity of the set of states with some given reliability. It is shown that this can be done with O(ln(ln N)) bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication.
Gallager REF proposed a distributed algorithm that could compute the parity of the bits at the nodes in a broadcast network with binary symmetric channels with a given accuracy using only O(ln ln N ) bits per node.
Finding Parity in a Simple Broadcast Network
IEEE Trans. Info. Theory
Computer Science