Accession Number:

ADA123300

Title:

On the Complexity of Designing Distributed Protocols,

Descriptive Note:

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR INFORMATION AND DECISION SYSTEMS

Report Date:

1982-11-01

Pagination or Media Count:

10.0

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

Subject Categories:

  • Psychology
  • Statistics and Probability
  • Cybernetics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE