Concurrency is Coordination and Sharing

 

The other day I was watching Rob Pike's presentation on "Concurrency is Not Parallelism" where indeed he makes a good distinction between concurrency and parallelism, but I felt that something was missing. You see, what he calls Concurrency has very little to do with what Andreia and I call Concurrency. As such, I've been trying to distil why that is, and this post addresses some of these ideas.

 

I believe that Concurrency in shared memory can be split into two areas: coordination and sharing.

 

Coordination is when the concurrent algorithm has to deal mostly with how to split the work between the different processes. When I say processes here, I mean the wide sense an execution context, encompasses not just unix processes, but also threads, tasks, virtual threads, green threads, fibers, etc.

Under this umbrella we have techniques like map-reduce, coroutines, fork-join, work-steal, and others.

 

Sharing on the other hand, is all about managing shared resources, whether those are files, sockets, data in memory, or something else.

Techniques on these group have an emphasis on how the resources are shared among the different processes. Examples of these are Locks, concurrent data structures, universal constructions, transactional memory, and others.

 

The abstractions and algorithms that we use to solve problems of the sharing type are usually significantly more complex than the algorithms needed to solve the coordination-like problems. In other words, sharing-type concurrency is harder than coordination-type concurrency.

Take a concurrent data structure, those are hard, and if you want to make them lock-free, then it's even harder. As an example, there are currently no highly scalable tree maps with rebalance, and that's due to the complexity in implementing a correct one!

Designing and implementing a universal construction or a transactional memory is also extremely hard, and even something as simple as a reader-writer lock can be hard to achieve if we want to simultaneously obtain high scalability and starvation-freedom.

 

 

When you hear someone say "Language X is really good for Concurrency!" usually what they really mean is that language X has been well designed to deal with coordination-type concurrent problems, and that's fine, if it wasn't for the fact that those languages make very little effort into dealing with the sharing-type problems.

I'm biased because I see the sharing-type problems as being more important, but let me try to put that aside for a moment. Let's say for a moment that these problems are equally important. Then shouldn't we create abstractions that help us solve both kinds of problems?

Furthermore, a good strategy when solving a problem is to start with the hardest part first, and if the hardest part of designing a language for concurrency is to deal with the sharing-type concurrency types, then shouldn't a language first and foremost provide ways to solve these problems?

As a language designer, completely ignoring sharing-type concurrency just because it's hard, doesn't seem like a good strategy to me.

 

Unfortunately, this is what many recent languages have done, and upcoming languages seem to be on the same path as well.

Take the HyLo language, which I personally find very promising, when you click on the topic of Concurrency in their site, all they describe is the structured concurrency approach, which is great to solve the coordination-type problems, but there is no mention on how they propose to solve the sharing-type problems.

 

Is it acceptable to just disregard sharing-type problems altogether?

Sure. Languages are tools, and it's ok to specialize a tool for a specific purpose. We can use different tools for different purposes.

But it's misleading to say that a language is good for concurrency and then only solve half the problem.

 

Some languages provide a good coverage on both sides of the fence, like Java.

Java has good abstractions to deal with the sharing-type problems: atomics and a memory model, mutual exclusion locks, stamped-locks, reader-writer locks, and scalable concurrent data structures. On the other hand, Java also has good abstractions to deal with coordination-type problems: fork-join, threads and thread pools, tasks (virtual threads), and even reactive programming approaches as non-standard libraries.

Perhaps more importantly, the Java folks carefully chose which abstractions from both sides play well with each other. And this, I would argue, is a very important detail when designing a language, because as I showed on a previous post, not all concurrency abstractions work well with each other.

With project Loom, the Java folks went to great lengths to ensure that Virtual Threads can safely and efficiently call blocking code, including using locks.

 

 

But what exactly are the coordination-type problems and the sharing-type problems?

And as a developer, should you care about both equally?

 

Examples of coordination-type problems are things with web-server like behavior, with thousands or millions of independent small requests, but no mutable data. Abstractions like tasks, structured concurrency, coroutines, and others on the left side of the schematic, are great to solve these kind of problems.

Another example, are embarrassingly parallel problems, the kind that are great to use with map-reduce. And I guess we can place things like "AI training" mostly in this category too.

 

As for sharing-type problems, it's basically anything where data is or may be shared among multiple execution contexts (processes, threads, or tasks). For example, implementing a Database Management System (DBMS) typically implies a concurrency control as one of its core components to manage access to the records in the database.

Another example is Operating Systems (OS) which require sharing resources in the system, typically though locks.

If your application needs to share mutable data among the execution contexts, then you have sharing-type problems, and therefore, you need sharing-type concurrency abstractions to deal with those.

 

Which kind of applications do you care about? Web servers? AI? DBMS? OS? Something else?

Focusing on just a small subset of these doesn't look like a good strategy. A good language should help the developer achieve its goals for a large variety of applications.

And the really hard problems are the ones which require concurrency abstractions from both sides. Applications which need a lot of coordination and sharing of data. For those types of applications, we need a language that provides good concurrency abstractions from both sides of the fence.

 

As a side note, perhaps it's no accident that Java has good sharing-type abstractions, as Oracle was originally (and still is?) a database company, and at some point had its own operating system (Solaris). In other words, the culture at Oracle has a strong tradition of dealing with sharing-type concurrency.

 

 

In summary, yes concurrency is not the same parallelism, but concurrency is not only about coordination-type problems and coordination-type abstractions. Managing the sharing of resources is a big part of concurrency, in fact, it's the part of concurrency where I spend most of my time and effort, it's the part of concurrency that is the hardest, and it's the part that is the most in need of great abstractions to work on, so please let's not ignore it.

 

Concurrency is coordination and sharing.