Concurrency theory is the theory of systems which may communicate with one another.
If you've ever written and debugged a computer program, you're used to the process of studying a written representation of a system and working out what the behaviour of the system will be. If your system consists of several parts which sometimes work independently but sometimes have to communicate with one another, it's much harder. You need to allow for all the different orders in which things might happen. Problems which may arise include your system deadlocking, every time or (harder to fix!) very occasionally.
In order to study such systems, we need a concise way of describing the concurrency aspects of a system. One way is the Calculus of Communicating Systems, CCS. In this notation, for example,
For example, a.0 describes a system which can do action a and then become the system 0. The system 0 can then never do anything at all. So the behaviour of a.0 is that it can just do one action a, and then stop.
Usually we use this non-determinism when there's something about the system that we are choosing not to model. For example, perhaps the system behaves as P if the user presses button 1, and as Q if the user presses button 2, but we don't want to model the user and the buttons just now.
One feature of this notation which may seem surprising is that there's nothing to stop a system definition referring to itself. For example, consider the system A defined by
A = a.A
Well, it's of the form a.P (where in this case P = A), so it can certainly do an action a, and become A. Then what can A do? Well, A = a.A, so it can do an action a and become A... We can carry on with this argument as long as we like, so this process A can carry on doing a actions for ever. Since we often want to model systems which keep going for ever (traffic lights, air traffic control systems, telephone systems, infinitely good jugglers...) this ability to describe infinite behaviour is very useful.
Be a member n get paid for Reading mails.
0 comments:
Post a Comment