Finding Parity in a Broadcast Network

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 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1985
Accession Number
ADA158568

Entities

People

  • R. G. Gallager

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Bits
  • Contracts
  • Decoding
  • Electrical Engineering
  • Electronics Laboratories
  • Information Processing
  • Information Systems
  • Information Theory
  • Massachusetts
  • Military Research
  • Numbers
  • Permutations
  • Probability
  • Reliability
  • Transmitters
  • Virginia

Fields of Study

  • Computer science

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Computer Networking