Book Cover B = mC2

Business Strategy in a Multidimensional World


Automata, State, Actions, and Interactions

The p-calculus web page ...  

I created the pi-calculus metamodel for the WS-CHOR working group.

Lucian Wischik web page, check also this link (Web services and pi-calculus)

A good article was referenced on the WS-CHOR mailing list: "A pi-calculus model of a Spanish fish market", Julian Padget, Russell Bradford

The ubiquity of TCP/IP and the Internet has enabled many systems to communicate with their environment with great ease. Such interactive systems are actually becoming the norm. Surprisingly, most of the work to model these categories of systems has started fairly recently when compared to the theory of sequential algorithmic processes  (l-calculus) which is the foundation of all programming languages. Actually the first steps of l-calculus can be traced back to the 1600s with the work of Mathematician and Philosopher, Blaise Pascal, who designed and built the first (mechanical) calculator.

The l-calculus theory is about modelling systems which have no or little interactions with their environment. On the contrary, the p-calculus theory developed by Robin Milner in the late 1980s is about modelling concurrent communicating systems. This theory also takes into account the notion of "mobility" which can either be physical or, as in the case of B2B, virtual (movement of links between systems). I think we can actually relate the mobility to the notion of "change": change of business partner, business document format, capabilities, etc � any modification of an existing relationship between two companies may be associated with mobility.

As a side note, p-calculus is the foundation of two of the main Process Markup Languages: BPML from the BPMI consortium and XLANG (now BPEL4WS) from Microsoft, which we will study at the end of this chapter.

At a high level, a company can be considered to be a very large automaton whose logical state consists of gigabytes or terabytes of data, and physical state is made of the raw materials, manufactured goods, people and money under its control. Its state is strictly bounded in the sense that it is owned and accessible in its entirety from the corporation, but hidden from any other corporation. A company can change its state by initiating an action (ship an order, pay a supplier, �). When another corporation wants to change or query this state it is done via an interaction. Interactions usually trigger some internal actions based on business rules, which enable the corporation to ultimately be in a state which is consistent with the one of its business partners.

The company�s actions, when executed, transition from one state to another. Interactions and actions, when assembled together, form the enterprise business processes. Both the number of actions and states can be large for any given corporation. However, they are both finite.

Let�s look in more details at an automaton. The classical theory, as the starting point of Milner�s theory,  specifies that an automation over a set of actions Act has four ingredients:

  •  A set of states Q = {q0, q1, �}

  • A start state q0

  • A set of transitions which are triplets (q,a,q') members of Q x Act x Q

  • A subset F of Q called the accepting states

In theory a business is deterministic, thus will obey the rule that for each pair of state and action (q,a) there is at most one transition (q,a,q').

 An automaton can be represented with a directed graph as shown below. States are represented in circles (q0, q1�) transitions are represented as arrows (t = q0 .c. q1 ) and accepting states are represented with a double circle:

This model can be extended to introduce the notion of events and conditions, which may act as a guard to an action. Actions may be automatic; when one reaches a state qi an action "a" occurs without any other pre-conditions. In other cases, a "condition" may decide whether action "a" or "b" will happen, again automatically. Lastly, an event, sometimes combined with a condition, may trigger an action (Event Condition Action model), which in turn will transition the automaton from a state to another.

When the number of potential states is large this diagram becomes impractical and is often replaced by an activity diagram, just like the UML activity diagram. This diagram is drawn from a different perspective. It does not show the specific states the automaton may take but rather the controlled succession of activities (that is, actions) that may occur within a corporation. State-transition or activity diagrams are often referred to as a processes or a sequential processes.

When two corporations are engaging in B2B activities, they are each running their (internal) sequential process concurrently. These two processes must interact to reflect commitments, transfer of economic resources, and many other aspects of the business activity shared between the two business partners.

This causes the actions of a given corporation to be divided into two different sets: those which are externally observable and those which are internal.

At this point the automaton A (that is, the corporation) is considered as a black box and the externally observable actions can be represented with the following notation (in this case only two of them):


a and b are called
labeled ports. Each complementary pair (b, b) of ports represents a means of interaction between two automata. These are the points of synchronization between the automata.

This graph is called a flowgraph. While the transition graph depicts the dynamic properties of a system, a flowgraph depicts the structure of the system, in other words the relationships between its components. An automaton can have any number of labelled ports, and a port may bear any number of arcs directed to any number of automata.

If we look at a global picture we see that the two automata A and B are running with no particular dependence except that any action b from B must be synchronized with an action from B from A:

The synchronization is represented by a shared transition between their state-transition graphs. This notion of shared transition was first introduced by Carl-Adam Petri in his theory of Automata. The corresponding graphs have been known as Petri nets.

Let�s draw some conclusions from this very short exposure to the p-calculus theory. First and foremost, there is no need to expose the details of the processes to model their interactions. It is enough to focus on the externally observable actions. Nothing prevents a corporation from exposing as much of its internal actions as it wishes (sometimes to obey regulatory requirements such as the ones in the aerospace or pharmaceutical industry, or yet to comply with standards such as ISO 9000), but it is completely separate from the specification of interactions. These internal actions do not become external once they are exposed, they remain internal since they are not part of the interaction. This is the ultimate goal: providing a shared view of the interactions regardless of the actions that lead to any particular interaction. Most companies consider their internal actions as their core assets and therefore are very reluctant to expose them.

Second, interactions are solely supported by the actions of the two concurrent automata involved. In particular, interactions do not require a third automaton which role would be to manage them, unless chosen by design (such as a broker, or a market place between buyers and suppliers in typical B2B topologies).

Last, a set of enterprise information systems can be viewed as a communicating and mobile automata. Inside a corporation, they can be aggregated to form a single logical automaton. Once we reach the boundary of a corporation, automata may no longer be composed since corporations do not share any state but rather synchronize their respective states when they communicate.

The p-calculus theory is far more elaborate than what was presented in this section. Our goal here was to introduce a few concepts that will be helpful in building the big picture and position PMLs and ebXML together.

Somebody wrote an extension to this article: