# Accession Number:

## ADA158568

# Title:

## Finding Parity in a Broadcast Network

# Descriptive Note:

# Corporate Author:

## MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

# Personal Author(s):

# Report Date:

## 1985-08-01

# Pagination or Media Count:

## 14.0

# Abstract:

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.

# Descriptors:

# Subject Categories:

- Cybernetics
- Non-Radio Communications