Communicating Sequential Processes
A formal language for describing concurrent systems.
- Processes
- Traces
- Events
- Chains
- References
Processes
A process represents the behaviour pattern of an object. It consists of an alphabet, which is the set of the possible atomic events an object can engage on. There is no distinction between events originated by the user of the object or by the object itself.
The alphabet of process is denoted as and the set of traces of is denoted as . Two processes are considered independent if their alphabets are disjoint.
A process can be defined in terms of itself, like .
A process can be defined as a function that takes an event and results in a process, and where its domain must be a subset of the alphabet. The function may return to represent termination.
Two processes are equal if their event choices are the same and each resulting process is the same. The processes and are the same if .
If two objects define the same process, then they are considered equal, therefore there exists only one object that defines a process. A more formal definition for a process such as is . Given a function that maps an event to a process, the unique-type definition can be generalized as , where the second argument to is the process itself, in order to support recursion.
Operators
The prefix operator () takes an event and a process and describes the process that engages in a given event and then behaves like the subsequent process, for example . Notice that is equivalent to .
The choice operator () takes two prefix applications (its not an operation on processes) and describes a process that has a choice over what event to engage on, for example . Notice that . The events on the involved prefixes must be different, as is considered invalid.
The alphabet of the resulting process consists of the prefix events and the alphabets of the involved processes: .
There exists a shorthand to define choices over a set. Given , the shorthand evaluates to . If the set of choices is the empty set, the resulting process is the broken process. Given , if where for all , then .
A process is a subset of process if they share the same alphabets and the traces of can all be consumed by . This is denoted as: . Of course, . If two processes are subsets of each other, then they must be equal: . The subset operation is transitive: . Finally, a process is always the superset of its broken process: .
Given a variable that is either or , the process behaves like if , and like otherwise. This operator obeys the following laws:
Given a boolean expression and a process , the process is the machine that restarts while is : .
Process Mapping (or Change of Symbol)
Given a function that maps the alphabet (takes the alphabet of a process and returns a new set of the same size), a process , and an event , then represents the process that engages in (the actual function application) whenever engages in . The function must be injective, so that makes functional sense.
It follows that . The traces of the mapped process are . Notice the mapping function always preserves the broken process, as in that case it would map over an empty list of choices: .
Notice that process mapping distributes over the composition operator: . When it comes to consuming a trace , then .
Given the choices shorthand definition of a process non-recursive process: .
For example, consider and . In that case, .
Given a sequential process , then must hold.
Given an arbitrary interleaving , .
A process defined by mapping diverges when its original process diverges. Given and , .
The failures of a mapped process are defined as . The refusals of a mapped process are defined as .
Concealing a mapped process is defined as .
Process Labelling
Labelling is a mapping technique to add prefix to all the events of a process. Its useful when constructing groups of processes, and where we need to make sure that they are independent (that their alphabets are disjoint). Process labelled with is denoted as . The prefix is added before every event, separated by a period.
For any prefix , there exists a function . The labelled process is equivalent to . Notice labelling changes the alphabet: .
For example, consider . In that case, .
Concealment
Concealment creates a new process that behaves like the new process but with certain events being hidden. This operation reduces the alphabet of a process and may introduce non-determinism. Concealing an infinite sequence of consecutive events leads to divergence.
This operation is defined as if , and as otherwise. Given the choice shorthand definition , concealing such process with expands to if , otherwise it expands to where , which introduces non-determinism.
The alphabet of a concealed process is . The traces of a concealed process are defined as . The following laws apply: and .
Given a concealed process, its divergences consist its original divergences plus the new ones potentially created by the concealment operation:
The alphabet of a concealed process is defined as .
The failures of a concealed process are defined as:
Subordination
Given , is a slave or subordinate process of if , as each action of can occur if permits it, while can freely engage on events of its own (where ). If we want to conceal communication between master and subordinate, then we can use the notation . Its alphabet is .
The subordinated process can be given a name in which case the master will communicate with it using a compound channel name, while the subordinated process will communicate with its master through a normal channel pair name. The benefit is that all communication between the master and the subordinate can’t be detected from outside as the new subordinate name acts as a local variable for the master.
For example, . Also consider . In this case, there is no way can communicate with as it doesn’t know about its existance or about its name, .
- Only the master process can make a choice for the subordinate:
- The order in which subordinate processes are declared doesn’t matter:
- The master may communicate with other processes, and such communication is left outside the subordination:
Communication from the master to the slave looks like this: . Conversely, communication from the slave to the master: .
Communication
Communication between processes is done using events that sets values on channels. This is described by the pair where and or the triplet which includes the process as a prefix (a compound channel name). Notice that for any . A channel used by only to send events is an output channel of . A channel used by only to receive events is an input channel of .
Communication is unidirectional and only between two processes. Communication between two processes can only happen if both processes engage in the communication: one listens on a channel while the other one sends a message through that channel.
The set of all values that process can communicate on a channel is the alphabet of the channel: . Given a compound channel name, . Communication event pairs must be part of the alphabet of a process. For two processes to communicate over a channel , they need to share the same alphabet on such channel: . Given and communicate over channel , all the possible communication events are inside .
Given proces , the event sends value over channel . For this to be valid, . This event is defined as . The communication message can be a more complex expression: . The event to wait for a value on a channel is , where takes the value of the received message. This is defined as a choice over all the valid communication events of that channel: . A process can wait in more than one channel using the choice operator: .
Variables
is the process that sets to . Its defined as . It follows that and that . The assignment operator can be used with multiple variables: but keep in mind that as in the first case may depend on the new value of . With regards to the conditional operator: .
Given a process , is the set of all variables that can be assigned within , and is the set of all the variables that can access. Of course, all variables that can be set can be accessed: . Both sets are subsets of .
No variable assigned in a process can be accessed by another concurrent process, so given and , then .
Deterministic Processes
A deterministic process is a tuple consisting of two sets: an alphabet and a set of traces. These laws must be satisfied for a deterministic process to be valid:
- : the empty trace is valid on every process
- : if a trace is valid in a process, then any prefix of the trace is also valid in the process
- : all traces consist of elements of the alphabet
A process is deterministic if it can’t refuse any event in which it can engage: .
Deterministic processes can unambiguously pick between events whenever there is a choice. These processes obey an extra law: given then, .
The process that results by making a process consume a trace is a process with the same alphabet, and with all traces whose prefixes were consumed. Given process and , then . Of course, , and given a function definition, assuming .
The choice prefix shorthand notation works like this: given an alphabet , a set of choices , and a function that maps over the set of traces, then .
The process mapping operation using a function is defined as .
Special Processes
Every alphabet has a broken process that never engages in any event. Given alphabet , the broken process is . Processes with different alphabets are always considered to be different, so given alphabets and , if , then . The traces of the broken object are defined as .
Every alphabet has a run process that can always engage, at any given point, in any event of its alphabet. Given alphabet , the run process is , or alternatively , and it follows that . Notice that the run process behaves like a restart process: .
Given alphabet , the process does nothing and terminates successfully: . A process can terminate successfully by behaving like . Notice . Its traces are .
Concealing the broken process results in the broken process: .
Properties
A process is cyclic if in all circumstances it can go back to its original state. Given process , then . The broken process is a simple example.
A process is free from deadlocks if none of its traces lead to the broken object: .
Non-deterministic Processes
A non-deterministic process is defined as a triplet that stands for the process alphabet, its failures, as a relation where , and a set of divergences where and . The following laws must hold: