Distributed Control in Computer Networks and Cross-sections of Colored Multidimensional Bodies
Author(s)
Kranakis, Evangelos; Vitanti, Paul M.B.![Thumbnail](/bitstream/handle/1721.1/149113/MIT-LCS-TM-304.pdf.jpg?sequence=3&isAllowed=y)
DownloadMIT-LCS-TM-304.pdf (3.311Mb)
Metadata
Show full item recordAbstract
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. We establish lower bounds on the average number of point-to-point transmissions between any pair of nodes in this 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 process may not, for >=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 occuring in random cross-sections of colored, multidimensional bodies in terms of the total (multidimensional) volume of each color in the whole body.
Date issued
1986-04Series/Report no.
MIT-LCS-TM-304