On the Complexity of Distributed Decision Problems,

Abstract

We study the computational complexity of finite versions of the simplest and fundamental problems of distributed decision making and we show that, apart from a few exceptions, such problems are hard (NP-complete, or worse). Some of the problems studied are the well-known team decision problem, the distributed hypothesis testing problem, as well as the problem of designing a communications protocol that guarantees the attainment of a prespecified goal with as little communications as possible. These results indicate the inherent difficulty of distributed decision making, even for very simple problems, with trivial centralized counterparts and suggest that optimally may be an elusive goal of distributed systems. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Aug 01, 1984
Accession Number
ADA147174

Entities

People

  • J. Tsitsiklis
  • M. Athans

Organizations

  • Massachusetts Institute of Technology

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Boundaries
  • Communications Protocols
  • Computational Complexity
  • Detection
  • Distributed Computing
  • Dynamic Programming
  • Guarantees
  • Numbers
  • Observation
  • Optimization
  • Polynomials
  • Probability
  • Probability Distributions
  • Rational Numbers
  • Sensor Networks
  • Signal Processing

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Computer Networking
  • Operations Research
  • Team-Based Human-Centered Cognitive Task Decision Making and Information Performance.