Distributed Match-Making for Processes in Computer Networks * Preliminary Version

In the very large multiprocessor systems and, on a grander scale, computer networks now emerging, processe s are not tied to fixed processors but run on processors taken from a pool of processors. Processors are release d when a process dies, migrates or when the process crashes. In distributed operating systems using the servic e concept, processes can be clients asking for a service, servers giving a service or both. Establishing communication between a process asking for a service and a process giving that service, without centralize d control in a distributed environment with mobile processes, constitutes the problem of distributed match-making. Logically, such a match-making phase precedes routing in store-and-forward computer networks o f this type. Algorithms for distributed match-making are developed and their complexity is investigated i n terms of message passes and in terms of storage needed. The theoretical limitations of distributed match-making are established, and the techniques are applied to several network topologies.