Action Relations: Basic Design Concepts for Behaviour Modelling and Refinement

This thesis presents basic design concepts, design methods and a basic design language for distributed system behaviours. This language is based on two basic concepts: the action concept and the causality relation concept. Our methods focus on behaviour refinement, which consists of replacing an abstract behaviour by a more concrete behaviour, such that the concrete behaviour conforms to the abstract behaviour. An important idea underlying this thesis is that an effective design methodology should be based on a properly chosen and precisely defined set of basic design concepts. Properly chosen design concepts represent essential system conceptions (mental images) that are derived from the real world and allow a designer to conceive and structure the essential characteristics of a system. The set of basic design concepts and their combination rules is called a basic design model. We explain how a design methodology supported by design notations and automated tools depends on the basic design model. We introduce and motivate a limited set of basic design concepts that are necessary to design distributed systems. These concepts are structured into two related conceptual domains: the entity domain and the behaviour domain. This thesis focuses on the behaviour domain, which consists of the action concept, the interaction concept and the concept of causality relation. Therefore, we elaborate the action and interaction concepts in more detail and give a formal definition of these concepts. The elaboration of the causality relation concept comprises the main part of this thesis. In order to enable a systematic and modular development of the causality relation concept, we identify the important characteristics of relations between actions and structure these characteristics in an abstraction hierarchy. An action models the essential characteristics of a unit of activity that is performed by a single entity. We consider the following characteristics of an activity as essential: the result that is established by the activity, the moment at which the activity is finished and makes its total result available, and the location at which this result is made available. These characteristics are modelled by means of the information, time and location attributes of an action, respectively. We consider an interaction as a refinement of an action, which models how an activity is performed through the cooperation of multiple entities. A causality relation defines one or more alternative conditions for the occurrence of an action in terms of how this action depends on the occurrences or non-occurrences of other actions. An action occurrence is caused by (or depends on) only one of its alternative conditions, although multiple of these conditions can be satisfied at the same time. We consider the uncertainty or probability that an action occurs when one (or more) of its alternative conditions are satisfied as an important concept in the design of relations between activities. This concept is represented by the probability attribute, which defines, for each alternative 390 Summary condition of an action, the probability that the action occurs when this condition is satisfied. We distinguish three types of probability attributes: (i) the uncertainty attribute supports two uncertainty values: must and may, (ii) the integral probability attribute quantifies these uncertainty values, such that the must value corresponds to probability value 1, and the may value corresponds to a probability value in the range (0..1), and (iii) the stochastic probability attribute uses the time attribute of an action as a stochastic variable, such that a probability distribution function defines for the time period in which the action is allowed to occur, the probability that the action actually occurs. We start with an initial definition of the causality relation concept that supports the design of temporal ordering relations between actions, including the uncertainty attribute. Four elementary causality conditions are defined: the start condition, the enabling condition, the disabling condition and the synchronization condition. These elementary conditions can be composed into more complex causality conditions using the conjunction (and-) and disjunction (or-) operators. The disjunction operator is used to define multiple alternative causality conditions for an action. The uncertainty attribute defines, for each of these alternative conditions, whether the action must or may occur when this condition is satisfied. The initial definition of the causality relation concept is extended with the information, location and time attribute. This extension supports the design of the following type of constraints for each of these attributes: (i) the range of possible values that can be established in an action, (ii) how the value of an action depends on the values established in other actions, and (iii) how the occurrence of an action depends on the values established in other actions. Constraints involving different attribute types are also allowed, e.g., the time and location value established in an action may be referred to as information values by another action. The integral and stochastic probability attribute can be used instead of the uncertainty attribute to quantify the uncertainty of action occurrences. Two interpretations of these probability attributes are distinguished: (i) the simple interpretation defines for each alternative condition of an action the probability that the action occurs when this condition is satisfied, and (ii) the extended interpretation defines for each alternative condition of an action the probability that the occurrence of the action is caused by this condition once this condition enables the action. The extended interpretation allows one to model the probability of individual actions in, e.g., choice, disabling and interleaving relations. In order to define the formal semantics of causality relations, a so called execution model is introduced. In this model, a behaviour is defined by enumerating all possible executions of this behaviour. An execution represents the outcome of a possible run of a system that performs a specified behaviour. This outcome comprises the actions that have occurred, the information, time and location values that have been established in these actions, and how action occurrences are related in the particular execution. An execution also gets one or more probability values, which represent the probability that this execution is the outcome of a system run. In this respect, a behaviour is considered an experiment and an execution is considered a possible outcome of this experiment. The sum of the probability of all possible executions of a behaviour is equal to 1. Based on the basic design language, we present an integrated set of methods to perform behaviour refinement. These methods support two basic types of behaviour refinement: 391 causality refinement, in which causality relations between abstract actions are replaced by causality relations involving their corresponding concrete actions and some inserted actions, and action refinement, in which an abstract action is replaced by an activity involving multiple concrete actions and their causality relations. The methods are based on the assessment of the conformance relation between the abstract behaviour and the concrete behaviour that is obtained from the abstract behaviour by means of causality refinement or action refinement. This assessment involves the determination of the abstraction of the concrete behaviour and the comparison of this abstraction with the original abstract behaviour. Rules to perform the abstraction and comparison operations have been developed. In this thesis we extend the basic design language with the causality-oriented structuring technique defined in [16]. This technique allows one to structure a complex behaviour in terms of simpler sub-behaviours and their relationships. In order to model (infinitely) repetitive behaviours, this technique is extended with the means to (dynamically) create multiple instances of a single sub-behaviour (type) definition, including the means to refer unambiguously to each individual behaviour instance. The ideas presented in this thesis are applied to two case studies. We apply our behaviour refinement method to the design of a system that supports a client-server interaction. At the highest abstraction level we assume that direct interactions between the client application and the server application are possible. At a lower abstraction level we implement these interactions using a federation of remote traders, which communicate via a common communication infrastructure. We also apply our basic design language to the modelling of the behaviour of the OSI Connection-oriented Transport Service. This case study also includes the modelling of timing and probability characteristics imposed by the QoS parameters of the transport service.