Accession Number:

ADA172224

Title:

Distributed Control in Computer Networks and Cross-Sections of Colored Multidimensional Bodies.

Descriptive Note:

Interim research rept.,

Corporate Author:

MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE

Personal Author(s):

Report Date:

1986-04-01

Pagination or Media Count:

19.0

Abstract:

The number of messages to match a pair of processes in a multiprocessor network with mobile processes is a measure for the cost of setting up temporary communication between processes. The authors establish lower bounds on the average number of point-to-point transmissions between any pair of nodes in the context. The present analysis allows for the possibility of multiple transmissions as opposed to a single one between any two nodes, and also for the possibility of multiple queries as opposed to the two, i.e. post and a single query considered before. Applications of the results include lower bounds on the number of messages for distributed s-matching, that is, matching a group of s processes, and distributed s-mutual exclusion, that is, s-1 processes may enter a critical section simultaneously, but s processes may not, for s or 2. The idea of the proof of the combinatorial result needed for this analysis is further extended to obtain a lower bound on the average number of colors occurring in random cross-sections of colored, multidimensional bodies in terms of the total multidimensional volume of each color in the whole body. Author

Subject Categories:

  • Numerical Mathematics
  • Computer Hardware
  • Computer Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE