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.

Subject Categories:

  • Cybernetics
  • Non-Radio Communications

Distribution Statement:

APPROVED FOR PUBLIC RELEASE