Think Stitch


Many-to-One Communication by Interleaving

A process can communicate with more than one process through a channel by using interleaving. It is, in short, many-to-one communication.

An Example of Many-to-One Communication by Interleaving

The Sender Processes

We prepare multiple sender processes. Each sender is assigned to a number k as ID. Each sender simply sends a datum through the channel ch and then terminates.

(define-process (P k)
  (! ch (k) SKIP))

The Receiver Process

The receiver process has only one channel for receiving. The process has a counter to count the number of receives. When the counter is equal to the number of senders, the receiver terminates.

(define-process (Q n)
  (if (= n 0)
      SKIP
      (? ch (x) (Q (- n 1)))))

The System Process

Now, we define the system process by combining the receiver and the senders. We firstly combine senders by interleaving. After that the composition of the senders and the receiver process are combined with the sync-list, which contains only the channel ch.

(define-process SYS
  (par (list ch)
    (Q N)
    (xpar k (interval 0 N) '()
      (P k))))

Simulation

The computation tree of the system process is as follows. The order of the communications is nondeterministic .

Identifying Senders by Process ID

In the above example, only the process ID is sent through the channel. Generally it is impossible to identify the sender from the received data. However, if we add an process id to the channel parameter as above, the receiver process can identify the senders. For example, we can define a channel as follows:

(define-channel ch (pid data) ...)

Using a guard, the receiver can receive data only from the specified senders.

Using a channel which has a process ID of a sender as a parameter is actually the same as using multiple channels for multiple senders. It is a matter of taste which design is adopted. On the other hand, a model using a channel with no process id can be said to be an abstract model.

2013/12/17