Finding Parity in a Broadcast Network

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 note 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. This problem was first formulated by A. E1 Gamal (see Chapter III, Section 3.10) and is of interest because it is one of the simplest distributed algorithm problems involving noise.