# Synchronous Channel Implementation

> **NOTE:** as per [#79](https://github.com/wetware/ww/issues/79), we are first pursuing a single-producer/single-consumer (SPSC) channel implementation, which we will extend to a MPMC channel in a later effort. Therefore, this note assumes exactly one sender and one concurrent receiver.

## What is `sync.Cond`?

Reference #1 says it best:

>If I had to summarize sync.Cond in one sentence: A channel says “here’s a specific event that occurred;” a sync.Cond says “something happened, idk, you go figure it out.” Thus, sync.Cond is more vague, **which means it’s also more flexible.**

It also hints at how you should use it:

>It’s kind of like a `chan struct{}` paired with a `sync.Mutex`: after you receive from the channel, you lock the mutex, then go investigate what happened.

There are two parts to this:

1. You use `sync.Cond` **in conjunction** with a mutex.
2. `sync.Cond` locks the mutex when it receives a signal, and then hands control to you.

(Note: point #2 is a bit unclear from the phrasing, but that is how it works)

At any rate, ref #1 is worth reading to understand `sync.Cond` in general.

## How does it help us with channel implementation?

If we trace our way through the implementation flowchart for [#79](https://github.com/wetware/ww/issues/79) (below), it becomes clear that there are multiple points at which a goroutine must block **until something has happened**.


Exactly _what_ must happen is, however, dependent on the current state of the flowchart. For example, "is it my turn?" requires checking different state variables than "is the receiver ready?". Moreover, because both the sender and receiver goroutine can modify these state variables, some synchronization is necessary (e.g. a mutex). Thus, at a glance, we have a problem well suited for `sync.Cond`.

## Back-of-napkin implementation

The following is a proof-of-concept implementation of the SPSC channel using `sync.Cond`. To avoid obscuring the high-level mechanics, it includes some simplifying assumptions:

1. There is only one sender and one concurrent receiver.
2. Both goroutines are in the same process (no network calls are involved).
3. The channel is not a Cap'n Proto capability.

Applying this logic to a capnp capability server should be a fairly straightforward matter of:

1. Employing `call.Go()` to ensure that senders & receivers do not block each other.
2. Employing a pair of list structures to implement sender & receiver queues.
3. Employing contexts to cancel out of blocking calls

**Implementation:** https://go.dev/play/p/20Nht77ZgQ_9

## Follow-up thoughts

The concurrency here is already non-trivial, and that complexity is bound to increase with the addition of MPMC semantics. The more I stare at this, the more I think this effort could benefit from a formalized approach. This could take several forms.

At a minimum, we should take the time to enumerate the channel invariants, and convince ourselves -- even if informally -- that they hold. I see roughly two (non-exclusive) approaches we could take:

1. I have a hunch that this channel design is a special case of two-phase commit (2PC). Convincing ourselves of this would help bound the problem.
2. We could formally specify the channel semantics with TLA+ and verify it with the model checker.

There are some marginal behaviors of `sycn.Cond` that I don't fully understand. While I would *expect* the Go devs to avoid (or at least document) any footguns, I would like to actually understand `sync.Cond`'s invariants in some detail. For instance: what happens when a thread calls `Signal()` immediately before `Wait()`, as in the above `Send()` implementation? Is `Send()` re-entrant in these conditions? If so, this would produce a livelock.

### Addendum

A cursory glance at the `sync.Cond` implementation suggests that `Signal()` < `Wait()` does **not** produce re-entrant behavior. The call to `Singal()` notifies threads that have previously registered in a [`runtime.notifyList`](https://cs.opensource.google/go/go/+/master:src/runtime/sema.go;l=461;drc=02d8ebda8398342516a24a3e8435d527ed156cab;bpv=1;bpt=1?q=runtime%2Fsema.go%20&ss=go%2Fgo:src%2Fruntime%2F). So that's nice :slightly_smiling_face:

# References

1. [The Pros of `Cond`s](https://lukechampine.com/cond.html)
1. [How to properly use the conditional variable `sync.Cond` in Golang](https://www.sobyte.net/post/2022-07/go-sync-cond/)