XCHANs: Notes on a New Channel Type


New 05Oct2023 – updated 18Sep2025 (Overflow buffer). This paper is in group Publications.

This note is a restoration and update of XCHANs: Notes on a New Channel Type.

See the still existing CPA 2012 page.

XCHANs: Notes on a New Channel Type

Øyvind Teig. Autronica Fire and Security (AFS) (A UTC Fire and Security company) – https://www.autronicafire.no

Keys: Channels, synchronous, asynchronous, buffers, overflow, flow control, CSP.
In: Presented at: Communicating Process Architectures 2012 (CPA-2012), at Abertay University in Dundee, Scotland (26-29 Aug. 2012)

Proceedings: Communicating Process Architectures 2012 (CPA-2012). Proceedings of the 34th WoTUG Technical Meeting (pages 155-170). P.H. Welch et al. (Eds.) Open Channel Publishing Ltd., 2012. ISBN 978-0-9565409-5-9 © 2012 The authors and Open Channel Publishing
Ltd (Dissolved company, therefore url from Wayback Engine) – All rights reserved.

Abstract
This paper proposes a new channel type, XCHAN, for communicating messages between a sender and receiver. Sending on an XCHAN is asynchronous, with the sending process informed as to its success. XCHANs may be buffered, in which case a successful send means the message has got into the buffer. A successful send to an unbuffered XCHAN means the receiving process has the message. In either case, a failed send means the message has been discarded. If sending on an XCHAN fails, a built-in feedback channel (the x-channel, which has conventional channel semantics) will signal to the sender when the channel is ready for input (i.e., the next send will succeed). This x-channel may be used in a select or ALT by the sender side (only input guards are needed), so that the sender may passively wait for this notification whilst servicing other events. When the x-channel signal is taken, the sender should send as soon as possible – but it is free to send something other than the message originally attempted (e.g. some freshly arrived data). The paper compares the use of XCHAN with the use of output guards in select/ALT statements. XCHAN usage should follow a design pattern, which is also described. Since the XCHAN never blocks, its use contributes towards deadlock-avoidance. The XCHAN offers one solution to the problem of overflow handling associated with a fast producer and slow consumer in message passing systems. The claim is that availability of XCHANs for channel based systems gives the designer and programmer another means to simplify and increase quality.

Prologue: This paper had a prologue in a blog note I wrote in the spring of 2012, «034 – Output guard vs. «channel ready» channel.» See, https://oyvteig.blogspot.com/2011/12/034-output-guard-vs-channel-ready.html. The XCHAN suggestion would in practice also encapsulate the semantics of the «knock-come» pattern, as seen in 009 – The «knock-come» deadlock free pattern and also discussed in several other notes here. The internal ChanSched is also shown in the paper.

An added description (for myself 11 years on..): The listening side of an XCHAN waits on the channel just as a standard CHAN, in an ALT/select or in an input statement. The sender side is a user or internal process/task that acts as a «driver» to do the semantics of an overflow. It also just outputs just as on a standard CHAN. However, the sender also needs to listen to an extra channel, the x-channel. The runtime system handles the internal behaviour of the sending channel and also sends on x-channel, since it would know if any process/task in fact has taken the input or not. If none has taken the input, this is called a «failed send» (even if it’s perfectly normal!) and the sender is given a «return» on the x-channel (in the original paper’s semantics). The sender handles this any way it wants to. Alternatively the sender process/task may be part of bundle which is called XCHAN and which would have buffered or unbuffered sender tasks hidden internally, just like in the below model. So XCHAN = x-channel + CHAN + optional hidden handler process/task.

Value-added: once you have read and understood XCHANs, the «Selective choice ‘feathering’ with XCHANs» paper of CPA 2013 might be of interest. There, «this semantics may be used to avoid having to send (and receive) messages that have been seen as uninteresting. We call this scheme feathering, a kind of low level implicit subscriber mechanism.» It is inspired from Tony Hoare‘s lecture from 2003, «Concurrent programs wait faster» (here), which I was lucky enough to attend. See Publications.

An occam Model of XCHANs

Fringe at CPA-2013 (the year after). See the still existing CPA 2013 page.

Observe that the semantics of the internal feedback x-channel is different in this model than in my original paper. See next chapter.

Peter H. WELCH, School of Computing, University of Kent, UK

Names of XCHAN Implementations

See the still existing CPA 2013 page.

Øyvind TEIG, Autronica Fire and Security AS, Trondheim, Norway

Abstract (orig here ). Two names for possible XCHAN implementations are suggested. The original presentation (Teig, CPA-2012) describes the «classic» scheme where the xchan-ready channel is used only if the original sending fails. The occam-pi model (Welch, CPA-2013 fringe) uses the «pre-confirmed» scheme, where a signal on xchan-ready is a necessary precondition to any communication. It is believed that «feathering» (Teig, CPA-2013) seems to be possible only with the classic scheme.

Overflow buffer

The standard overflow buffer (overflowbuffer) is obsoleted with XCHAN. Still this is an important SW component in the kind of systems we have here. It gives CHAN a dimension with optional overflow feedback. I discovered that I didn’t have a separate chapter on it in my blog notes, thus making one here. Here is the description from the paper:

5.1 A Channel-Ready-Channel in Traditional occam

Fig.2 -Example of an overflow buffer (OBUF)

An “intelligent buffer” could be a composite process that takes input on one channel and sends out on another. It could potentially receive more than it can send, filling up an internal buffer that eventually could overflow. Since we do not have output guards, it must be prompted for output by an additional process. This is a classical occam idiom.

The figure is rewritten from an earlier paper [CPA-2006]. The composite overflow buffer OBUF consists of BUF and OUT. The channel-ready-channel between OUT and BUF is c5, and it must be ALTed with c2 in BUF. This pattern has been used extensively in occam.
BUF knows when sending on c4 that it will not block. What we see here is in fact a buffered channel from c2 to c6 with minimum capacity 2. A ring buffer could be added in BUF, and overflow handled by throwing away messages and inserting an overflow message in the buffer, so that it may be seen by the receiving end.

Other notes

See search for XCHAN here. In particular: Lecture NTNU: Becoming textual: attempting to model ‘XCHAN’ with CSPm (even if I didn’t succeed).