Francisco Sant'Anna

Structured (Synchronous) Concurrency

@_fsantanna

I have recently learned about Structured Concurrency (SC), which supports nested coroutines with tied lifetimes. There are a number of libraries (Dill, Trio, Effection), and even language mechanisms in Swift and Kotlin.

The similarities with Esterel and derived imperative synchronous languages (ISLs) is noteworthy. However, it seems that no bridges between these worlds (ISLs & SC) have been built. Research in ISLs dates back to the early 80s, and constantly reinforces the idea of lexically-scoped tasks with safe cancellation. I believe the most interesting paper to connect SC with Esterel is Berry’s “Preemption in Concurrent Systems” from 1993, which I discuss further.

While studying the similarities between Esterel and SC I also wondered how they would compare to other concurrency models. I came up with this diagram to highlight two aspects that I find the most relevant to this discussion: the basic paradigm (procedural vs functional) and the scheduling semantics (synchronous vs asynchronous).

The diagram is divided in four quadrants (A,B,C,D), each containing a representative language or mechanism (threads, map-reduce, Esterel, and FRP). The diagram suggests that Esterel and SC (SC libs) are very similar. The gray area in the middle contains flexible mechanisms that could also be adopted in other quadrants.

The basic paradigm considers how tasks or units of concurrency are combined in the code. Quadrants A,C (threads and Esterel) rely on typical procedural commands such as loops and assignments. Quadrants B,D (map-reduce and FRP) rely on expressions and functional combinators.

The scheduling semantics considers how tasks or units of concurrency execute with respect to the others. Under the synchronous model (quadrants C,D), they execute in locksteps or time ticks, and can only advance together. Under the asynchronous model (quadrants A,B), they execute independently, and require explicit primitives to synchronize.

Focusing on quadrant C, and going back to Berry’s paper, follows the first two sentences of his paper:

Process preemption deals with controlling the life and death of concurrent processes. Well-defined preemption mechanisms are essential in control-dominated reactive and real-time programming, and accurate handling of preemption requires a time-dependent model.

Note that “preemption” in this context is the ability to abort a process, and should not be confused with “preemption” as in “preemptive multithreading”.

Now, consider the similarity to Sustrik’s definition of SC:

Structured concurrency means that lifetimes of concurrent functions are cleanly nested. If coroutine foo launches coroutine bar, then bar must finish before foo finishes.

What mostly distinguishes Berry’s quote is the restriction in the last sentence: “preemption requires a time-dependent model”. This restriction is exactly what characterizes quadrant C in the diagram: a synchronous semantics.

Berry’s main goal in the paper is to advocate for orthogonal abortion primitives…

We also want the preemption primitives to be orthogonal to all other primitives, that is, we want no restriction on their use. More precisely, we want to be able to abort or suspend any statement at any time, be it a communication or a computation, and we want to be able to abort a statement for any reason.

…and in the rest of the paper, Berry makes the case for ISLs:

We show that classical time-independent languages can only handle the weaker notion of “may” preemption, instead of the “must” interpretation that is really needed for reactive systems. “Must” preemption requires reasoning about relative timing of events.

Note that time-independent languages (quadrants A,B) cannot guarantee safe points of abortion: the process might be in the middle of an operation, or holding a lock, or just about to receive a rendezvous message. Hence, abortion must always be explicitly coordinated between processes, and thus cannot be an orthogonal construct in the language.

In opposition, time-dependent languages like Esterel rely on the “Synchronous Hypothesis” (SH), which states that

…time is defined externally to programs by the flow of inputs, and that program internal bookkeeping is done in zero-delay with respect to all external time units. The only instructions that take time are those explicitly required to do so, like “await for 30 meter” that lasts exactly 30 meter.

Under the SH, processes are always at safe points because internal bookkeeping, such as rendezvous communication or arbitrary operations, is always atomic and instantaneous. Of course the SH cannot always be satisfied, in which case ISLs are not adequate. However, the SH applies to most reactive applications, such as GUIs, video games, and I/O-bound networked applications.

To conclude, note that SC also advocates for “clean nested lifetimes”, which is analogous to the orthogonal abortion mechanisms of ISLs. Hence, SC must be in quadrant C, and hence the title of the post as “Structured (Synchronous) Concurrency”.

Comment on @_fsantanna.