x-to-y channel, anyone?

[Larry Dickson <tjoccam@xxxxxxxxxxx>]

Hi Peter and occam-com folks,

Before I wander off and reinvent stuff on my own, I'd like feedback on my (probably trivial?) notion of a queue-based x-to-y channel (where x and y can be one or many (independently)). Peter said all those four kinds of channels were mutexes, and I thought queues, but did not have my thoughts organized at CPA2018. Here is stuff I passed to Peter a month ago, but got no reply, probably due to his legal stuff.

A channel starts out empty, and maintains a queue count which starts at zero. A number of sender and receiver processes may communicate through the channel (the number may be unbounded or not). A process arrives when its code reaches the point of communicating through the channel. When a sender arrives, the queue count is increased by one; when a receiver arrives, the queue count is decreased by one. This always results in a change in the absolute value of the queue count. If the absolute value decreases, a communication takes place between the arriving process and the lead process of the queue in the opposite direction. If the absolute value increases, the arriving process is put at the end of the queue and blocks. Note that there need only be one queue; the queue count tells whether it is a sender queue or receiver queue.

If there is only one sender, the queue count cannot rise above +1;  if there is only one receiver, the queue count cannot fall below -1. This means that this setup allows one-to-one, many-to-one, one-to-many, and many-to-many channels. Bounds on the queue count can be enforced that are smaller than the number of senders or receivers, in which case an arrival may fail (like a NAK in TCP connect attempt).

Implementation may be centrally static or quasi-dynamic or both. Centrally static means there is room in the channel for maintenance of the queue, so that the queue count limit is finite. (A one-to-one channel is an example of this.) Either the number of senders and the number of receivers is constrained to be less than or equal to the queue count, or the case of failed arrival must be handled. Quasi-dynamic means that the queue is maintained using space in each queued process (like a timer queue in Transputer occam). Though each process can remain static, there need be no limit on the number of processes in the queue (again like a timer queue), and no failed arrival need be handled. A combination of them is possible, where a static queue is maintained up to a certain length and then the quasi-dynamic approach takes over. That requires circular in-channel queue and also avoids failed arrivals, but makes dequeueing more complicated, and may be called for if the queue count is almost always bounded but on rare occasions may get longer.

In one-to-one and many-to-one cases, a standard input ALT is possible. I believe it will also work in the other cases, since ready-to-communicate is deterministic and the ALT would just amount to a loop within this commitment.

(Added since then) I thought about it, and to do an input ALT in the one-to-many or many-to-many cases would would probably want two queues. This is because between the matchup of an input and an output and the actual communication between that input and that output there might be a long time lapse due to ALTs which lose. The same could happen because of a long communication. Stuff that comes in from other processes while this is underway would go to a second "inner" queue, thus allowing the process queue to progress.

Larry Dickson