Finding Parity in a Broadcast Network
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS
Pagination or Media Count:
Consider a broadcast network of N nodes in which each binary digit transmitted by each node is received by each other node via a binary symmetric channel whose crossover probability is 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 Oln ln N bits of communication from each node. Communicating all the node states to one node can be accomplished with only marginally more communication.
- Non-Radio Communications