Wednesday, August 23, 2006

Concurrency is easy

We understand concurrency

A deep understanding of concurrency is hard-wired into our brains. We react to stimulation extremely quickly, in a part of the brain called the amygdala, without this reaction system we would die. Conscious thought is just too slow, by the time the thought "hit the brakes" has formed itself, we have already done it.

On a motorway, I mentally track the positions of dozens, or hundreds of cars, this is done without conscious thought. If I couldn't do this I would probably be dead.

The world is parallel

If we wish to write programs that behave as other objects behave in the real world then these programs will have a concurrent structure.

This is why we should program in a concurrent programming language

And yet most often we program real-world applications in sequential programming languages. This is uncessarily difficult.

By programming in a language what was designed for programming concurrent applications (like Erlang) concurrent programming becomes a lot easier.

Erlang programs model how we think and interact

We don't have shared memory. I have my memory, you have yours, we have two brains, one each, they are not joined together. To change your memory I send you a message, I talk or wave my arms. You listen, you see, your memory changes, but without asking you a question or observing your response I do not know that you have received my messages.

This is how it is with Erlang processes. Erlang processes have no shared memory. Each processes has its own memory. To change the memory of some other process you must send it a message and hope that it receives and understands the message.

To confirm that another process has received your message and changed its memory, you must ask it (by sending it a message). This is exactly how we interact.

Sue: "Hi Bill, my telephone number is 45 67 89 12"

Sue: "Did you hear me?"

Bill: "sure, your number is 45 67 89 12"

These interaction patterns well-know to us, from birth onwards we learn to interact with the world by observing it and by sending it messages and observing the responses.

People function as independent entities that communicate by sending messages

That's how Erlang processes work, and that's how we work so it's very easy to understand an Erlang program.

Erlang programs are made up of lots of little processes all chattering away to each other - just like people.

An Erlang program is made up of dozens, possible thousands or even hundreds of thousands of small processes - all these processes operate independently. They communicate with each other by sending messages. Each process has a private memory. They behave like a huge room of people all chattering away to each other.

This makes Erlang program inherently easy to manage and scale. Suppose we have ten people (processes) and they have too much work to do, what can we do? get more people. How can we manage these groups of people, easy just shout instructions at them (broadcasting).

Erlang processes don't have shared memory, so there is no need to lock the memory while it is being used. Where there are locks, there are keys, and when there are keys the keys will one day get lost and what happens when you loose a key? - you panic.

Distributed software systems with locks and keys always go wrong.

If somebody dies other people will notice

I I'm in a room and suddenly keel over and die, somebody will probably notice, well at least I hope so. Erlang processes are just like people, they can on occasions die. Unlike people when they die they shout out in their last breath exactly what they have died from.

Imagine a room full of people, suddenly one person will keel over and die and just as they die, they say "I'm dying of a heart attack" or "I'm dying of an exploded gastric wobbledgog". That's what Erlang processes do. One process might die saying.

"I'm dying because I was asked to divide by zero", another might say

"I'm dying because because I was asked what the last element in an empty list was"


Now in our room full of people we might imagine there are specially assigned people whose job it is to clear away the bodies. Let's imagine two people Jane and John. If Jane dies then John will fix any problems associated with Jane's death. If Jane dies then John will fix the problems. Jane and John are linked together with an invisible agreement which says that if one of them dies the other will fix up any problems caused by the death.

That's is how error detection in Erlang works, processes can be linked together. If one of the processes dies, the other process gets an error message saying why the first process dies.

That's basically it.

That's how Erlang programs work.

What we've learnt so far

Erlang programs are made of lots of processes. These processes can send messages to each other.

These message may or may not be received and understood. If you want to know if a message was received and understood you must send the process a message and wait for a reply.

Pairs of processes can be linked together. If one processes in a linked pair dies the other process in the pair will be sent a message containing the reason why the first process died.

This simple model of programming is part of a model I call Concurrency Oriented Programming. You can read more about this here.

20 comments:

Anonymous said...

Thank you. That was a very simple and intuitive explanation of concurrency. I have been looking for such an explanation. I would have been happy if it was half good as this.

Anonymous said...

I agree with vamsee, this is a very nice explanation. I am currently trying to learn Erlang and the whole concurrency paradigm; this post is very helpfull to me. Thank you Joe and I hope you will keep on blogging in this way. I have read some of your papers and presentations and I always found them enlighting

BTW, I come from a good old smalltalk training background. ST too has message passing. Do you know if there are major differences between a concurrency oriented programming model and an object oreinted programming model in smalltalk?

Anonymous said...

This is probably the clearest explanation of a complicated topic that I've seen in a long time. Too often people are busy trying to impress everyone with their intelligence by spouting off cryptic ideas that rest on a temple of assumptions about the readers skill level. What a great post. Will you teach me some Maths now? :)

Anonymous said...

One of your premises is obviuosly wrong:

We don't have shared memory. I have my memory, you have yours, we have two brains, one each, they are not joined together.

The premise that the above statement is based on - is that we are not internally concurrent. The earlier statements in your blog entry say that we are. The actuality is that all of our individual (i.e. internal) processes are concurrent and share memory. Even including our main conscious "thinking" process.

It is our interaction between individuals that doesn't always share memeory and even here we do share memory - many examples (dairies, libaraies, system processes, etc) - in various ways.

Anonymous said...

All these processes with no shared memory sounds heavyweight.

Anonymous said...

Thanks for the informative post, you've made me interested in Erlang.

How extensive are Erlang libraries compared to say, Ruby or Python? I'm using Twisted Python at the moment for some asynchrous network stuff, and it could be a fun project to learn Erlang with.

whim said...

Even though concurrent systems and OO systems both use the term "message passing" they are very different. In OO invoking a method also implies a passing of control. Before the method is called, the caller (calling routine) is executing but the callee (called routine) is not. When a method is called on another object, the caller blocks (stops executing) until the method returns, and instead the callee executes. After the method returns, then the callee is no longer executing, but the caller resumes executing.

In concurrent programming, both the sender of the message and the receiver are potentially executing (concurrently, just like people). Either the caller or the callee can block, but they do that explicitly, not as a side effect of a message send (although if a process is blocked waiting on a message, then receipt of that message will unblock it implicitly).

Jonathan Allen said...

What is so facinating about message passing between processes? I used to do that all the time using TCP, Message Queues, or database files.

An all appearances, Erlang's answer to concurrency is to side-step the issue by taking away half our tools. Don't get me wrong, message passing between processes is useful. But sometimes the right answer is to share data in a more direct fashion.

Looking over Mr. Armstrong's thesis, I have even more doubts about "Concurrency Oriented Programming".

So far, everything he talks about could have been done back in 1998 using MS Message Queues. In fact, I did build a system in 2001 with all the characteristics of COPL (as outlined on page 22) using Visual Basic.

And my system was a bit more flexible. I didn't have to send messages to a specific process; I could send it to a type of process. I could have N processes running on M machines listening to a given queue, while guaranteeing that only one would pick up and process a given message.

Anonymous said...

karl b: It is easy to implement message passing in object oriented languages, but the problem I see with 100% MP concurrency in object oriented languages is that each thread is resource heavy (I don't know about smalltalk specifically). Becuase the threads are heavy, it is impractical to have a thread for every object. Definetly, however, use message passing in OO where it makes sense. It often makes better sense than shared state.

For a language neutral reference on concurrency, I highly recommend "Concepts, Techniques, and Models of Computer Programming" by Peter Van Roy and Seif Haridi.

Ralph Dratman said...

Good explanation of Erlang. Thank you. However, biological concurrency doesn't work anything like what you describe. Neurons don't scream anything intelligible when they die, as far as I know. And they can't, to my knowledge, broadcast anything beyond the group of other neurons to which they are already connected. And neurons apparently do not send whole complex messages around anyway; presumably only brain subsystems (such as the retina) can do that.

Anonymous said...

This is the start of a method to teach anyone a program language. Well done!

Peter Arrenbrecht said...

@Anonymous: It may sound heavyweight, but Erlang processes are at the runtime-level, not the OS level. They are very cheap. And the duplication of data depends on how you structure your servers and their communication patterns. A did a test recently spawning some 20000 Erlang processes which all had to report back a number of times and then die. A matter of 1-2 seconds on my PowerPC iMac.

Anonymous said...

Good evening Joe,

I've noticed that my point regarding your premise about shared memory didn't make the comments. I wonder why?

Though your article is interesting - it still misses the point that concurrency in the real world uses shared memory in some instances and doesn't use shared memory in other instances.

If you want to argue (debate) the point that concurrency doesn't use shared memory in the real world then please be more careful in your choice of examples. As it stands your article has some interest but the particulars you've used lessens the relevance of your view in how concurrency should be handles in programming languages.

regards

Bruce Rennie

Anonymous said...

There is a difference between "shared memory" and "shared memories".

Anonymous said...

@Bruce Rennie / ralph / etc.:

RELAX, it's JUST a metaphor. It's an introduction to what Erlang is and why concurrent programming is a good tool to have... THAT'S ALL.

I thought it was a great article that I would recommend to someone interested in Erlang. I'll make sure to warn them about the inaccuracies regarding neuron behavior and other completely irrelevant nitpicks...

Larry Kyrala said...

Interesting article. But is concurrency really easy? I'm skeptical... as Marvin Minsky says "In general, we are least aware of what our minds do best."

For a certain class of problems, I agree, Erlang's approach is much easier than locking semaphores... but I don't think it addresses all parallel programming problems or concerns.

One example of a very difficult parallel programming problem is from distributed simulation literature where researchers have been working on large-scale message-based systems for over 20 years. Some of the problems in that domain are really hard (e.g. google "Global Virtual Time").

Anonymous said...

Well written article. I've been interested in Erlang since I'd heard of it but unsure why. This article explains it well.

For 20+ years I developed software on Tandem NonStop systems, a loose-coupled, shared nothing, message-based OS. No wonder this makes sense to me. It's a damed shame that Compaq bought Tandem, HP bought Compaq and great technologies like Tandem (and DEC) are all but dead.

Anonymous said...

It was very interesting for me to read the blog. Thank you for it. I like such themes and anything that is connected to this matter. I definitely want to read more soon.

Anonymous said...

Who knows where to download XRumer 5.0 Palladium?
Help, please. All recommend this program to effectively advertise on the Internet, this is the best program!

Anonymous said...

Доброго времен суток,

Самая стабильная [url=http://popplers.ru/]адалт партнерка[/url] [b]Popplers.ru[/b] предлагает Вам сотрудничество на выгодных условиях. Мы покупаем ваш ру трафик по выгодным ценам. Владельцам сайтов, вебмагазинов и веб мастерам мы предоставляем выгодные условия, отзывчивую поддержку и проффесиональный подход в нелегком бизнесе рунета.
отличная возможность надежно заработать, выгодная рефферальная программа, направьте ваш ру трафик в нужное русло, в русло прибыли которое принесет вам [url=http://popplers.ru/]Партнерская программа[/url] [b]Popplers.ru[/b] . Вывод средств в WebMoney или PayPal, возможность срочных выплат в любой день недели, персональный подход к каждому партнеру.

Наши тарифы за 1k:

DoorWays - 6у.е.
Popunder - 5у.е.
CJ - 5 у.е.
Clickunder - 4 у.е.

Ждем Вас в нашей программе!

Support: 498994074