Distributed match-making (Q1107317)

There are many different issues in distributed control, e.g., name server, mutual exclusion, replicated data management, etc. In this paper, the coordination of interrelated processes (and nodes) is considered as the ``heart'' of distributed control and a simple theoretical problem, distributed match-making is proposed as the generic paradigm of studying distributed control. Intuitively, the distributed match-making problem is to assign a rendezvous (node) for each pair of nodes in the network. Two complexity measures are defined: communication complexity and storage complexity. Communication represents the average number of messages that need to be sent in order for a pair of nodes to make a match (i.e., both of them send messages to their rendezvous) and storage represents the average (or worst-case) amount of cache memory needed in a node for storing match-making messages. We want to minimize communication as well as storage. An interesting relation between the communication and the distributedness (i.e., how distributed the rendezvous are in the network) of a distributed match-making strategy is obtained. It is shown that communication increases as distributedness increases. A nice trade-off between communication and storage is presented. The result implies that it is impossible to minimize both communication and storage at the same time. These complexity results give theoretical limitations to the efficiency of solutions for many practical problems in this area. As an example, the coordination problems in practical distributed control issues such as name server, mutual exclusion and replicated data management are formalized as distributed match-making problems. Simple (optimal and nearly optimal) algorithms for distributed match-making in networks with various topologies are also exhibited. Several future research issues such as probabilistic algorithms, hashing method, and fault-tolerance are discussed at the conclusion of the paper. With many simple mathematical proofs and examples, the paper is very easy to read.