Title :
Finding parity in a simple broadcast network
Author :
Gallager, Robert G.
Author_Institution :
Lab. for Inf. & Decision Syst., MIT, Cambridge, MA, USA
fDate :
3/1/1988 12:00:00 AM
Abstract :
A broadcast network of N+1 nodes is considered in which each binary digit transmitted by each node is received by every 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
Keywords :
information theory; telecommunication networks; binary symmetric channel; broadcast network; distributed algorithm; parity; telecommunication network; transition probability; Broadcasting; Control systems; Distributed algorithms; Distributed control; Error probability; Information theory; Intelligent networks; Protocols; Telecommunication network reliability; Transmitters;
Journal_Title :
Information Theory, IEEE Transactions on
