Previous [1] [2] [3] [4] [5]

Journal of Inforamtion Science and Engineering, Vol.5 No.1, pp.35-49 (January 1989)
Distributed Matching for
Communicating Sequential Processes*

Jau-Yueh Wang and Shing-Tsaan Huang
Institute of Computer Science
National Tsing-Hua University
Hsinchu, Taiwan, R.O.C.

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.