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)


Idea for the derivation of a communication protocol


Service specification in the form of a Petri net


Idea for the derivation of a communication protocol

Here is an example:

Original Service Specifiction With swimlanes
service spec swimlanes
Transformation principle Final result
transformation 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)

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.


Idea for the derivation of a communication protocol


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.

taxi system sequenceTypical behavior

sub-activitiesother cases

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