Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Branch: master
Fetching contributors…

Cannot retrieve contributors at this time

168 lines (128 sloc) 6.239 kB

Interaction Design

(Note: “Interaction design”, in this context, means interaction between processes. It is not to be confused with the field of Interaction Design, which is concerned with human-computer interaction.)

I’ve been had! I was told that programming with concurrency in Erlang was simple and safe —  that the days of race conditions were over. But guess what? My Erlang program just went and misbehaved — I have processes hanging around which ought to have stopped, and sometimes things happens out of order! Who told you that now? While Erlang does give you certain guarantees and a quite well-thought-through set of building blocks for concurrent programming, it doesn’t solve all of your problems — a bit of thought and careful design is still required.

But that’s rubbish! I chose Erlang specifically for avoiding to deal with race conditions.

And for a lot of things, you don’t.

What Erlang does is to raise the threshold of when you have to worry and begin to think, so that —  by not having to deal with low-level stuff like issues related to shared state, and doing inter-process signalling and processing correctly and efficiently, and doing asynchronous communication without drowning in complexity, and cleaning up properly when things go wrong —  you can focus on the concurrency problems that actually relate to what you’re trying to do.

So no silver bullet?

Nope. You can easily have race conditions in Erlang.

But the good news is that such race conditions will only involve actual and explicit inter-process activities. Processes only communicate when they intend to, and not accidentally through shared mutable state.

That brings down the number of sources of potential race conditions a lot.

Okay, so the potential problems and causes are only where I might expect them to be. I guess that’s an improvement.

(I had programmed multi-threaded Java applications for a few years before I learned of the Java Memory Model (http://www.cs.umd.edu/~pugh/java/memoryModel/jsr133.pdf; http://java.dzone.com/articles/multithreading-and-java-memory.
Apparently you can’t assume anything unless it is explicitly guaranteed.)

Apparently not. You need to know your building blocks — doubly so when concurrency is in the picture.

The Givens

The primary inter-process communication primitive in Erlang is of course message passing.

Is there anything I need to know about it, in the context of avoiding race conditions and similar surprises?

What would you need to know in e.g. Java?

I’d need to know which causal guarantees the language provides. Which “happens-before” relations I can rely on.

Right. As for events within the same process, these are ordered according to that process’s progress.

That’s pretty standard.

Yes. As for inter-process communication: Compared to most other languages, things are mostly simpler in Erlang — because data immutability means that there’s no read-write or write-write races. Not at the language level, at least.

Why “mostly simpler,” then? Is there something that makes it harder?

Yes: distribution. Most other languages don’t have to worry about different parts of the program running on different machines —  transparently.

No, that is true. So, what guarantees are we given for message passing?

This one: If one process P sends message A to another process Q, before it sends message B to Q, then A will appear before B in Q’s inbox.

That’s it?

That’s it. Just a process-pair-wise message ordering guarantee. Plus, of course, the intra-process event ordering, and the fact that the sending of a message happens-before the reception of that same message.

But surely…​ some kind of triangle inequality must apply?

How do you mean?

That if P sends a message A to R, and then sends a message B to Q which on reception will send B' to R, then R will observe that A comes before B'?

No, sorry. We can’t assume that.

But why not? It sounds like a reasonable thing to assume.

It has mainly to do with distribution.

Consider the case where the three processes P, Q and R reside on different nods NP, NQ and NR.
These nodes are pair-wise connected through a network link.
Assume furthermore that the link NP→NR is very busy.

Ah. Then, because the NP→NQ and NQ→NR links are less busy, the message which goes via Q may overtake the one which is sent directly.

Yes. So the only way to ensure that A is received before B' is to not send B' before the reception of A has been acknowledged.

So, to sum up…​

  1. Events within a process are ordered according to the evaluation order of Erlang.

  2. The sending of a message happens-before the reception of that same message.

  3. The reception (in the inbox) of two messages from the same process are related with happens-before if the sending of the two messages are related with happens-before.

And “happens-before” is a transitive relationship, meaning that if A happens-before B, and B happens-before C, then A happens-before C.

Note, by the way, that the evaluation order is undefined in some cases. This is not usually a problem, however.

Getting Process Interaction Right

Now that we know what we can rely on, how do we then attack the problem of avoiding race conditions?

Jump to Line
Something went wrong with that request. Please try again.