Deadlocks in non-hierarchical CSP

It is well-known that programs with shared mutable state protected by locks are prone to deadlocks, but it is less known that programs without shared mutable state, based either on Communicating Sequential Processes (CSP) or based on an actor model can deadlock, too, despite them not using locks at all. They deadlock in a different way, known as communication deadlock.

See, the formal definition of a deadlock is not directly tied to locks. The set of processes (threads/coroutines/actors) is in a deadlock when each one is waiting for the next one in a loop. We’ll see a concrete example soon, but first I need to apologize for not highlighting this issue before.

The stage

During KotlinConf 2018 I gave a talk titled “Kotlin Coroutines in Practice” (video and slides) in which I’ve shown the importance of structured concurrency to build reliable software in practice and gave a glimpse of some advanced concepts of CSP programming style as implemented in library. In that section of my talk lies a problem. If you write all the code from my presentation verbatim, you are bound to get into a deadlock. Somehow I fell into this trap, thinking it is safe in my case, but no. So let us dissect it.

To start, note that all CSP-like architectures (including actor model) are safe if an application is structured as a data processing pipeline, where incoming messages enter into the system, get processed by different coroutines in sequence, and sent to the outside world at the end. More broadly, the code is trivially deadlock-free as long as it has a hierarchy (or DAG — directed acyclic graph) of coroutines, where higher-level coroutines only send messages to lower-level ones, but not vice versa, and each coroutine receives all incoming messages in one place, reacting to them by sending messages downstream.

However, during my presentation I’ve sketched an architecture with a data processing loop (see my presentation for the explanation of the problem that is being solved). The “Downloader” coroutine is sending locations for download to the pool of “Workers” and is receiving the resulting contents back from them:

The architecture in my presentation is based on three channels: , , and . The body of the downloader coroutine has the following communication logic:

while (true) {
select<Unit> {
references.onReceive { ref -> // (1)
loc = ref.resolveLocation()
locations.send(loc) // (2)
contents.onReceive { (loc, content) -> ... } // (3)

Downloader receives from the channel (1), resolves references to locations and sends them to the channel (2). It also processes results from workers by receiving from channel (3) to update its state. On the other side workers have the following code:

for (loc in locations) {                             // (4)
val content = downloadContent(loc)
contents.send(LocContent(loc, content)) // (5)

They receive from channel (4) and send downloaded contents to the channel (5).

It is hard to follow the logic even in two communicating pieces of code, but in CSP there is a handy way to visualize it. We can represent our system with Communicating Finite State Machines (CFSM). The states correspond to suspension points and transitions to communications:

Channel names are abbreviated on the above diagram for brevity, receive operation is abbreviated to , and send to . Downloader’s statement in its main loop corresponds to the state D₀ where it can receive from channel at (1) (shown as ) or from channel at (3) (shown as ). When it receives from , it goes to state D₁, where it waits to send to channel at (2) (shown as ).

Deadlock demo

I’ve filled in the missing pieces in the code from presentation with mock data classes, added function so that it completes in 10 ms (see the code here) and the main function that just continuously sends requests to downloader’s channel (here) and runs everything with a 3 second timeout using 4 workers. So there is a complete project that can be run. The correctly working code should process ~1000 requests in those 3 seconds. You can either clone it from a Github or run a single-file version in Kotlin playground here.

When you run this code you see that it processes only 4 requests (it is the number of workers defined in the code) and hangs, timing out after 3 seconds. Moreover, it does so consistently without any randomness whatsoever. It is deterministic, because it is run in a single-threaded context.

In order to convince you (and myself) that it is an inherent behavior of this kind of CSP code and not some bug of Kotlin implementation, I also rewrote the same code line-by-line in Go (see here or run in Go playground here, don’t blame me for Kotlinish style of code). Go runtime has a simple deadlock detector that immediately tells the situation for what it is: all goroutines are asleep — deadlock!¹ But what did actually happen?

All workers had completed their initial work and are in state W₁ trying to send to channel at (5) back to downloader but it is a rendezvous channel and downloader is not receiving from it right now. Downloader is in state D₁ trying to send to channel at (2), but workers are not receiving from it — they are all trying to send. A deadlock indeed — every coroutine is waiting.

Solutions that do not work

It might seem that the problem is in expression. It is easy to get rid of it here. Instead of having downloader process incoming messages from and channels via , we can rewrite downloader using an actor pattern as a coroutine that has a single channel for incoming messages (check the code here or try in it playground here):

for (msg in mailbox) {
when (msg) {
is Reference -> ...
is LocContent -> ...

However, actor-based approach does not avoid the deadlock either and this code hangs as quickly as the original one. You can notice that its communication state-machine is the same.

Another candidates to blame are rendezvous channels — channels without a buffer, since they suspend on trying to send to them without receiver on the other side. But even if we add buffers for both and , it is still not going to solve the problem. It will become less likely and will take more time to appear (see changes here, playground here). The larger the buffers, the less likely the problem is going to show up, but there is nothing to fundamentally prevent a deadlock situation from happening. Senders still suspend and deadlock when buffers are full².

Unlimited-capacity channels

A definite deadlock-prevention solution is to use buffer with capacity on at least one channel affected by communication deadlock. You can see the code with unlimited channels here and check it out in playground here to verify that it seems to work properly³.

However, by removing the limit on the channel buffer we forfeit the lucrative property of CPS programming style — automatic back-pressure propagation. If the receiver of messages from the channel is slower than the sender, then sender is suspended on full buffer to slow down automatically. With unlimited-capacity channels this is not going to happen and the task of managing back-pressure lies solely on the shoulders of application developer. Failing to manage back-pressure the system may eventually run out of memory, collecting more and more messages in its buffers.

In our case, making channels unlimited would completely remove back-pressure management for incoming references, since downloader would quickly send all of them to the channel even when all workers are already busy. Using unlimited capacity for channel is safer as it only affects the final processing of downloaded contents. However, with unlimited capacity we are at risk that downloader gets overwhelmed by the incoming and never gets to process downloaded . This observation brings us close to the first fully working approach.

Solutions that do work

Let us flip the order of cases in expression in downloader coroutine so that channel get checked first, i.e. so that messages (downloads completed by worker pool) have priority over messages in channel:

select<Unit> {
contents.onReceive { ... }
references.onReceive {

locations.send(loc) // (2)

By itself it does not fix the problem (you can verify the code in playground here), but it gives one useful property — downloader would try to send to channel at (2) only if no worker was suspended trying to send to channel at some moment of time before that. Now, it is enough to give channel capacity of at least one to ensure that there is at least one worker that can send its contents at (5) and start receiving from again at (4), allowing downloader to proceed, too:

val contents = Channel<LocContent>(1)

The working code is here, playground version is here. Notice, how it processes more downloads in those 3 seconds than the previous “solution” with unlimited channel. Moreover, with channel processing having highest priority, it is now safe to have unlimited capacity for channel. It will never keep more messages in its buffer than the number of workers plus one (why plus one? this is left as an exercise for the reader to show).

There is also an alternative solution that does not use buffered channels at all and works perfectly with channels of any capacity. It doubles down on to avoid suspending downloader on , folding this sending operation into a . It is actually the simplest one to represent and analyze in CFSM model, but I will not go into details now, leaving it for some future story. You can take a look at the corresponding code here and run it in playground here.


Communication loops (non DAG patterns) can and will cause communication deadlocks with channels of limited capacity, unless some deadlock-prevention strategy is used. If you encounter deadlock in your application, do not try to work around it with buffered channels before you understand what is going on or you risk sweeping the problem under the rug.

Feel free to share more working solutions to this particular communication loop deadlock in the comments to this story. The code both in Kotlin and in other CSP/actor runtimes is welcome (give a link, don’t paste the code into the comments, please).


I’d like to express my gratitude to Alexey Semin who had reported this problem via this github issue and Alexander Gorynin who contacted me in the Kotlin Slack. Also thanks to Simon Wirtz and Sean McQuillan for useful comments on the draft of this post.

UPDATE: The future roadmap

One question you may ask after reading this story: What is the future of channels in Kotlin? They will definitely stay, but they should be considered as “low-level primitives”, building block of higher-level, less error-prone constructs. Read more in the series of posts about Kotlin flows:


¹ ^ Go deadlock detector is much simpler than deadlock-detectors that are typically available for lock-based code (there is one built into JVM, for example). It only detects situation where the progress had stalled globally in the whole application and cannot detect local deadlock in a part of a larger system. Moreover, it is not an accidental oversight — precise local deadlock detector is impossible to implement for this kind of CSP system runtime where channels themselves are regular objects that can be sent anywhere.

² ^ In Go statement is making a non-deterministic choice (similarly to function in Kotlin), so with buffers in Go the problem reproduces with lower probability, creating a false sense of safety.

³ ^ Using unlimited capacity is the deadlock-prevention approach that actor-based Akka framework is taking. It gives actors mailboxes with unlimited capacity by default.

^ Moreover, unlimited capacity can create arbitrary delays between successful sending of request and its completion.

^ You can also get invite and take part in discussions at If you’ve read this story, then channel is the one you want to join.

Project Lead for the Kotlin Programming Language @JetBrains

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store