On the Complexity of Designing Distributed Protocols,

Abstract

We study the complexity of two problems of distributed computation and decision-making. We show that deciding whether two distant agents can arrive at compatible decisions without any communication one agent has three or more alternatives. We also show that minimizing the amount of communication necessary for the distributed computation of a function, when two distant computers receive each a part of the input, is NP-complete. This proves a conjecture due to A. Yao. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 01, 1982
Accession Number
ADA123300

Entities

People

  • Christos H. Papadimitriou
  • John Tsitsiklis

Organizations

  • Massachusetts Institute of Technology

Tags

DTIC Thesaurus Topics

  • Computations
  • Computers
  • Computing Devices
  • Mathematical Analysis

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Computer Networking
  • Graph Algorithms and Convex Optimization.
  • Operations Research