A fully distributed matching algorithm for CSP style programs is proposed in this paper. A CSP style program consists of a collection of asynchronous processes which may need to communicate with one another once in a while. Here, matching means that each process can choose one and only one from a set of its favorite processes to communicate with and that the chosen communication partner also abides by this agreement. To support such a style of communication, the proposed algorithm plays the role of a matchmaker.

        A simulation experiment is conducted for both the proposed algorithm and a recently reported token-based algorithm. The result shows that the proposed one has a shorter average waiting time for the matchmaker to choose a communication partner, but, has a few more messages. Further, the proposed algorithm uses a fully distributed control, and hence, has a more evenly distributed work load for the processes than its counterpart.

Keywords: communicating sequential processes, distributed algorithm, invite-and-bid protocol, matching, nondeterministic communication, synchronization

Received August 3, 1988; revised December 12, 1988.
^*This research was supported by the National Science Council of the Republic of China under the contract NSC76-0408-E007-09.