Distributed Control in Computer Networks and Cross-Sections of Colored Multidimensional Bodies.
Interim research rept.,
MASSACHUSETTS INST OF TECH CAMBRIDGE LAB FOR COMPUTER SCIENCE
Pagination or Media Count:
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
- Numerical Mathematics
- Computer Hardware
- Computer Systems