ELG 7187C - Deriving protocols for communication services and distributed workflow applications

Note: on overview of the issues discussed here is given in the Powerpoint slides on "Deriving component designs".

The problem

Assumption: We assume that the system is composed out of a number of components (which may communicate through message passing). Each component can perform certain local actions.

Problem: Given a global service specification which defines the order in which the local actions at the different components should be exercuted, we want to find a communication protocol that defines the behavior of the protocol entities executing on each component. Such an entity is assumed to be able to control the local actions through rendezvous communication with some application software, and communicate with the entities on the other system components by the exchange of messages. We therefore want to find an algorithm that takes as input the local actions and the global service specification, and produces as output the set of messages for communication between the protocol entities, and the entity behaviors which define the order of (local) execution of sending and receiving of messages and the execution of local actions.

We consider in the following cases with different languages used for defining the global behavior specification, starting with the most simple form: Labelled transition systems

Service specification in the form of a Labelled Transition System (LTS)

Assumptions

• Each state is associated with one of the components.
• The interactions of the outgoing transitions of a state are associated with the component associated with that state.

Idea for the derivation of a communication protocol

• Each entity is in an active or passive mode. In the passive mode, it waits for a "nextState" message. When it receives one, it goes into the active mode and performs the local action associated with one of the transitions leaving from the indicated next state. Then it sends a "nextState" message to the component associated with the next state of that transition, and goes back into the passive mode (Note: If the next state is associated with the same component, then it is not necessary to send a message). The entity associated with the initial state of the service specification is initially in the active mode.

Limitations

• There is no concurrency
• The choice between different actions is always done by a single node.
  • If an actions of a transitions from a given state should be associated with different components, then the service specification could be re-written by introducing replacing this transition by an intermediate transition (without any action) to a new state associated with the component of that action, and a transition with that action from this intermediate state to the next state of the original transition.

Service specification in the form of a Petri net

Assumptions

• We assume that each transition of the Petri net is a local action of some component.
• We assume that the service specification is a free-choice Petri net (that is, if a place has more than one outgoing arrow, each of these arrow leads to a transition for which this arrow is the only incoming arrow).
  • Note: If a place has several outgoing edges and it contains a token, then the place does the choice of the alternatives (it selects the transition that will consume the token).

Idea for the derivation of a communication protocol

• Step 1: Arrange a layout by swimlanes (as in Activity Diagrams), one for each system component, such that each swimlane contains exactly those transitions associated with the corresponding component of the swimlane.
  • For each Petri net place, associate it with one of the swimlanes. This should be done in such a way to minimize the number of Petri net edges that cross the swimlane boundaries.
• Step 2: Introduce "nextPlace" messages.
• Give a unique identifier to all Petri net places.
• Replace any edge that crosses a swimlane boundary as follows:
  • For an edge from a transition T in swimlane Lt to a place P in swimlane Lp, replace the transition in Lt by an edge to an intermediate place and an edge leading to a message sending action that sends a "nextPlace" message to Lp with the parameter containing the identification of P.
  • For an edge from a place P in swimlane Lp to a transition T in swimlane Lt, replace the transition in Lp by a transition with an action that waits for a "nextPlace" message from Lp where the parameter contains the identification of P followed by an edge to an intermediate place and an edge to the transition T.

Here is an example:

Original Service Specifiction	With swimlanes

Transformation principle	Final result

Notes: This is the same idea which is presented in Slide 36 of the Powerpoint slides on "Deriving component designs". If the Petri net is not a free-choice Petri net, the problem of making choices between different transitions is much more difficult.

Different kinds of choices (application perspective)

• Local choice: The choice is done by one component. Example: Free-choice Petri net (see above).
• Non-local choice: The components involved in the different alternatives negotiate the choice to be performed - mutual exclusion of the alternatives must be assured. A simple mutual exclusion protocol is the circulating token (the component having the token may chose an alternative - if it does not initiate any alternative, it will pass the token to the next component of the virtual ring).
• Competing initiatives (non-local initiatives): An initiative for an alternative may be taken by one component without consulting the others. In this case, a resolution between competing initiatives arriving simultaneously must be performed during the early stages of the competing actions. This case is handled with priorities by Gouda's approach discussed earlier. It is necessary that the lower priority could undo all actions ("abort the transaction") when it is interrupted by a high-priority alternative. Note: Often there are natural priorities between alternatives, for instance, an alternative to cancel an ongoing operation.
• Mixed initiatives with common goals: Like competing initiatives, but all initiatives have the same goal (they are not competing). An example is the initiation for termination of a telephone call (which can be taken simulataneously by both parties).

Service specification in the form of a LTS with concurrency (like UML State diagrams with hierarchical states containing concurrent behaviors)

When I wrote the first paper on "protocol derivation from service specifications" in 1986, the idea of hierarchical state charts were just published. I was rather inspired by the notation introduced in the LOTOS specification language which was developed during that timeframe. This notation used LTS semantics for communication (rendezvous) and had operators for defining state machine sequencing as well as concurrency. Our approach to protocol derivation was later extended and improved (see historical perspective below). The easiest reading is probably the paper by Khendek (Reference: (F. Khendek, G. v. Bochmann and C. Kant, New results on deriving protocol specifications from services specifications, Proc. SIGCOMM'89, July 1989, in Computer Communications Review Vol.19 no.4, pp. 136-145) ) which deals with the following sequencing operators: (strict) sequence, choice of alternatives (local choice), concurrency, regular recursion for constructing state machines. The slides of this Concordia tutorial (the last section on "Deriving protocol specifications from service specifications") give some overview of the issues involved.

Assumptions

• Well-structured introduction of concurrency, like in hierarchical UML state machines.
• Strict sequencing: This means, if there is a sequencing of a sub-behavior A followed by sub-behavior B (where both sub-behaviors may include parallel activities performed by different system components), then all activities that are part of A must have finished before any activity belonging to B may start.

Idea for the derivation of a communication protocol

• Each time, there is (strict) sequencing between two sub-behaviors A and B, we introduce a "flow message" from each of the components that is involved in a terminating action for one of the parallel activities of A to each of the components that is involved in the initiating action of one of the parallel activities of B.
• The messages must include some information about choices that have been done in order to inform all components that have to know about which branch of the specification is currently executed. Note: This issue becomes more complicated when recursive procedure calls are allowed in the specification language (see papers by Kant and Nakata in the historical perspective).

Limitations

• Only local choice is supported explicitly. But non-local choice may be easily included, using one of the approaches mentioned above.
• No weak sequencing considered (this is discussed below).

Historical perspective

The idea of deriving a protocol from a service specification was first presented in [G. v. Bochmann and R. Gotzhein, Deriving protocol specifications from service specifications, Proc. ACM SIGCOMM Symposium, 1986, pp. 148-156]. In this paper it was assumed that the service specification is written in some process algebra language including the following operators: stop, action prefix, alternatives, independent parallelism, and process names. << for details, you may look at the ACM journal paper . This paper also considers the passing of parameter values between the different sites involved in the protocol. >>  Without parallelism, this corresponds to the LTS formalism, for which protocol derivation was described in a paper by Saleh. 

More powerful specification languages have been considered: LOTOS has in particular the process call operator (which is similar to a procedure call with return) and in the case of recursion, one has to be sure that the different protocol entities are synchronized concerning the depth of the calling stack  << for details, see paper by Kant >>. This problem is more elegantly handled in a paper by Nakata  (A. Nakata, T. Higashino and K. Taniguchi, Protocol Synthesis from Context-Free Processes using Event Structures, in Proc. of 5th Int'l Conf. on Real-Time Computing Systems and Applications (RTCSA'98), Hiroshima, Japan, IEEE Computer Society Press, pp.173-180, Oct. 1998) , where all the exchanged messages contain information about the calling stack and the current point of executio of the process that sends the message. Nakata first analyses the temporal ordering (causal relationship) between the different actions performed by the different protocol entities and derives from this analysis the minimum number of message that must be exchanged.

Another operator of LOTOS, the "disrupt" operator, written [>, is quite difficult to implement correctly (according to LOTOS semantics) in a distributed environment, and I do not think that its semantics is reasonable for designing service specifications for distributed systems (i.e. it should not be used in this form). 

Protocol synthesis can also be handled in the context of Petri nets, as described in the paper by Yamaguchi ( H. Yamaguchi, K. El-Fakih, G. v. Bochmann and T. Higashino, A Petri net based method for deriving distributed specifications with optimal allocation of resources, Proc. of Int. Conf. on Software Eng. Applied to Networking and Parallel/Distr. Computing (SNPD'00), May 2000, Reims, France, pp.19-26.). In fact, this paper considers some extension of Petri nets with input/output service interaction points,  "registers" (variables that can be updated during Petri net transitions) and enabling predicates for transitions. In this sense, this modeling language is similar to Colored Petri nets, and we currently work on a paper to generalize these ideas to general colored Petri nets.

Service specifications with weak sequencing - and trying to find a compositional notation for global behaviors consisting of collaborations (sub-behaviors)

In 2006, I started the consideration of weak sequencing for the derivation of component behaviors in collaboration with Rolv Braek and Humberto Castejon from the University of Trondheim in Norway. At the same time, we considered hierarchical descriptions for the global behaviors, where a sub-behavior may involve several parties (as was already done in the original paper from 1986). However, now we used a different notation to describe the global behavior, namely UML collaborations, activity diagrams and sequence diagrams.

A recent paper ( H. N. Castejòn, G. v. Bochmann and R. Braek, On the realizability of collaborative services, Journal of Software and Systems Modeling, Vol. 10 (12 October 2011), pp. 1-21.) presents the example of a Tele-medecine system to demonstrate the use of these UML notations for defining the global behavior. This paper also explains the problems of designing the component behaviors due to non-local choices, weak sequencing and the resulting race conditions. The paper also gives some guidelines for designing global behaviors for which the design of component behavior is more simple.

Some further slides: Here are examples of hierarchical global specifications in the form of High-level MSCs ( Ex1 and Ex2 ). An example of race conditions

Here is an example of a taxi system. A manager assigns the taxis to the clients. There are three parties involved: clients, taxis, and the manager. For the high-level description of the behavior, the notation of Activity diagrams is used, while each sub-collaboration is defined in terms of a sequence diagram.

Typical behavior

The first sequence diagram above shows the typical behavior of a client using a taxi. The other three sequence diagrams show problem cases that may occur. In the first case, there is a problem with non-local choice (the manager assigns at the same time as the client withdraws), the second diagram shows a race condition between two messages received by the client (coming from different sources), and the third diagram is again a case of non-local choice where the taxi is assigned at the same time as the taxi picks up another client (C2) on the street.

An approach to deriving component behaviors in this context is described in my paper "Deriving component designs from global requirements" A (Proc. Intern. Workshop on Model Based Architecting and Construction of Embedded Systems (ACES), Toulouse, Sept. 2008) . The main conclusions of this paper are also presented in the Powerpoint slides on "Deriving component designs" (Slides 33 - 48). The main point of this paper (which is also mentioned in our recent paper ) is that one can perform this derivation of the component behaviors in a hierarchical manner if one knows for each sub-behavior the roles that participate, the roles that initiate the behavior, and the roles that have a last action to be perform, i.e. a terminating action (where the notion of initiation and termination is based on the partial order within that sub-behavior: an action is initiating if there is no other actions that is earlier in the partial order; it is terminating if there is no action that is later in the partial order). Compared to what was described in the earlier papers, we propose here the following precautions to deal with the race conditions due to weak sequencing:

1. Using a receive buffer pool from which received messages are requested by the local behavior when the behavior is ready to consume these messages (a specific message or one of several alternatives).
2. Introduce a so-called choice indication message for propagating the decision of a choice correctly.
3. Introduce counter parameters in flow messages (flow messages are those that look after strong sequencing or data flow) to indicate how often certain loops have been executed.

The 2008 paper deals with a restricted form of global control flow (well-formed activity diagrams - similar to hierarchical state machines with concurrency).

To deal with competing initiatives (a kind of non-local choice), the idea of Gouda's design method can be adapted to this context (more details to be explained in class).

A tool for performing the derivation of component designs from global requirements was build by Fedwa Laamarti where the global requirements and specifications of the distributed components are given in the form of UML Activity diagrams (Master thesis). An experiment involving this tool and the translation of the resulting component activity diagrams into BPEL was performed by Mustafa Nasser using the IBM Rational Software Architect for translating the activity diagrams into BPEL specifications, and using the IBM Websphere execution environment for running the BPEL processes. We found that a receive buffer, as mentioned under point (1) above was provided by the Websphere environment. However, a new solution had to be found for handling correctly the counter parameters involved in flow messages within loops (see conference paper for more details - Transforming dynamic behavior specifications from Activity Diagrams to BPEL ( M. N. M. Faleh and G. v. Bochmann )  Proc. IEEE 6th Intern. Symp. on Service-Oriented System Engineering, Irvine, Calif., Dec. 2011).

In the context of weak sequencing, it appears that one is mainly concerned with partial orders (as described in an old paper by Lamport). My former PhD student, Toqeer Israr, defined the semantics of our ordering operators using partial orders, and used these definitions to extend the global specification formalism to include performance (delay) properties (see conference paper or thesis). On a related topic, I was recently involved in some work on testing automata where each transition consists of several activities that are related to one another by a partial order. See paper on Partial-Order IOA testing C (Note: this paper allows partial order among the interactions that are part of the same "transition", but between transitions (that is, within a state) there is strong synchronization)

Last update: March 15, 2013; revised November 6, 2014