A design model for open distributed processing systems

Marten van Sinderen1, LuísFerreira Pires1, Chris A.Vissers1, 2,Joost-PieterKatoen1

(1) Tele-Informatics and Open Systems Group, University of Twente(2) Telematics Research Centre

PO Box 217, 7500 AE Enschede, The Netherlands

e-mail: {sinderen, pires, vissers, katoen}@cs.utwente.nl

Abstract

This paper proposes design concepts that allow the conception, understanding and devel-opment of complex technical structures for open distributed systems. The proposed con-cepts are related to, and partially motivated by, the present work on Open DistributedProcessing (ODP). As opposed to the current ODP approach, the concepts are aimed atsupporting a design trajectory with several, related abstraction levels. Simple examples areused to illustrate the proposed concepts.

Keywords: ODP systems; Design methodologies; Design concepts; Entity domain; Behav-iour domain; Structuring techniques.

1Introduction

The growing interest in distributed system applications has motivated the standardizationwork on Open Distributed Processing (ODP) by ISO/IEC and CCITT ([3], [4]). The mainpurpose of this standardization work is to allow the support of applications on a heterogeneouscollection of systems, permitting these systems to be arbitrarily distributed. Application end-users may have great benefits from standards for open distributed systems, including:•manufacturer and vendor independence: distributed systems can be composed fromproducts offered by different, usually competing, manufacturers. This is the usual interpre-tation of the termopenness;•crossing organizational boundaries: distributed systems may be spread across a number ofautonomous management or control authorities. This enables the sharing and integration ofresources and applications beyond the boundaries of the local organization; and•economy of scale: standards development is a common effort in which many manufacturersmay participate. The adoption of standards by many manufacturers may increase theproduction of systems derived from these standards and consequently may decrease theirprice.The design and implementation of a distributed system is a complex undertaking, and so isthe development of standards for open distributed systems. Even more because the potentialbenefit of manufacturer independence requires that standards are precise and unambiguous

prescriptions for implementations, formulated at a suitable abstraction level. They should be areference for the implementation of conformant systems, while leaving maximum implemen-tation freedom to the individual manufacturers.In order to meet these requirements and to be able to produce standards fast enough to keepup with the end-users’ needs and expectations, it is necessary to have an effective environmentfor producing, i.e. designing, standards. Such an environment can be called a design culture([20]). An important example of such a design culture is the Open Systems Interconnection(OSI) environment, which led to the OSI Reference Model (OSI-RM) and associated serviceand protocol standards.A design culture for producing standards must be commonly agreed upon, as opposed todesign cultures adopted by industrial companies, whose competitiveness in part depends onthe secrecy of their design culture. An important aspect of standardization work is thereforethe establishment of a design culture which is appropriate to the application area at hand.Naturally, this work should precede as much as possible the production of the detailed tech-nical standards. The OSI community, for example, initially focused on the development of theOSI-RM, which defines the key concepts necessary to define OSI services and protocols1.The first standard to be produced by the ODP community is a Basic Reference Model forODP (ODP-RM) ([8], [19]). The purpose of this standard is to provide a coordinating frame-work for the elaboration of standards for ODP systems. We believe that such a frameworkshould be defined as a common design environment, appropriate to the ODP application area,like the OSI-RM has been defined for the OSI application area. The ODP-RM should howeverbe more comprehensive with respect to a design environment than the OSI-RM could be at thetime of its conception. Indeed, it is possible to recognize the following distinctive elements ofa design culture in the current version of the ODP-RM:•framework of abstractions (Part 1 and Part 3 of [7]);•design model (Part 2 and Part 3 of [7]); and•architectural semantics (Part 4 of [7]).This paper discusses a number of demands for an effective design culture, based on the OSIexperience and on the experience with the development and use of Formal Description Tech-niques (FDTs) in the context of OSI. We conclude that the current version of the ODP-RMdoes not fully satisfy these demands, which implies that this reference model has to beimproved. This paper also presents a design model consisting of a set of elementary designconcepts that can be used as general purpose building bricks for the composition of designsand explicitly acknowledging the demands for an effective design culture. This design modelis more general purpose than the one described in the ODP-RM and should be considered ascomplementary, rather than opposite to the ODP design model.The presentation of our design model in this paper is carried out at a conceptual level,appealing to the designers’ intuition. In this way we avoid any biasing with respect to specificFDTs. This paper also presents a possible basis for a formal semantics of the design model.Furthermore we evaluate the suitability of this design model to support a design methodologyfor ODP systems. An example is used to illustrate some aspects of this model.The remaining of this paper is organized as follows: Section 2 presents some generaldemands for a design environment, and briefly discusses the support to these demands alreadyprovided by the ODP standardization, Section 3 presents the entity domain and the behaviour1.Other elements of the OSI design culture were developed later, e.g. service conventions, formal descriptiontechniques, and architectural semantics.2

domain, from which the elements of our design model are defined, Section 4 introduces fiveabstraction levels at which ODP systems should be considered, Section 5 presents a collectionof concepts that allow for behaviour definitions, Section 6 introduces behaviour structuringmechanisms, Section 7 discusses the application of entity and behaviour domains in a frame-work for design and implementation, Section 8 illustrates our design model with an exampleof the design of a simplified system to support multi-media (audio and video) informationexchange and Section 9 presents some concluding remarks.

2Demands for a Design Environment

A number of demands for an effective design environment for ODP systems, primarilybased on our OSI and FDT experience, are presented below in terms of rules. The extent towhich these demands have been satisfied by the current version of the ODP-RM is indicated.Rule 1:Design complexity calls for the use of a design methodology

There are many ways to arrive at the same design, and there are many alternative composi-tions of a design that reflect the same functionality. Yet, in both cases, one option is oftenpreferred above the others. Therefore, especially if a design (process) is complex, designersshould have a set of judgement criteria and procedures at their disposal which guides them intaking well-considered design decisions. These criteria and procedures may be based onsubjective value judgements, rational techniques, consensus, or heuristics ([13]).

A set of related criteria and procedures, such that the design process as a whole is coveredinstead of some isolated parts of it, is called adesign methodology. A design methodologyenables designers to systematically deal with all concerns, requirements and constraintsinvolved in the design of complex systems. It should allow to distinguish, order, and catego-rize concerns and handle categories of concerns in a step by step fashion. In each step onlyone category of concerns is dealt with according to some predefined design goal whilepreserving the design goals achieved in previous steps. By limiting design freedom, designmethodologies may speed up the design process, control its quality, and ensure the consis-tency among designs.

The design gap to be bridged by ODP is very wide, ranging from enterprise requirementsto engineering solutions. The involved complexity calls for the adoption of a design method-ology. Nevertheless, the ODP work, so far, tries to be methodology-independent. Theprobable reason for this is that the ODP community comprises many different communities(among others tele-communication, software engineering, and data base communities), eachwith their own methodology, which they are reluctant to dispose of or to compromise.Rule 2:A design methodology is effectively supported by a set of properly related abstraction

levelsAbstractions in system design ignore those characteristics of a system which are irrelevantfor a specific purpose. Hence, a set of abstractions can be effectively used as the basis of adesign methodology, provided the abstractions are chosen in accordance to the design goals ofthe methodology. The ordering and the step by step handling of categories of design concernscalls for a set ofrelated abstractionlevels. The relationship between these levels should besuch that at each next abstraction level the design goals achieved at previous abstraction levelsare preserved. Abstraction levels are then hierarchically related.

3

The use of abstraction levels is attractive for various reasons. First, it supports a bootstrap-ping approach to design, i.e. it allows short design gaps between designs at adjacent abstrac-tion levels, and thus enables easier validation of intermediate designs and leads to short repaircycles. Second, it supports an easier mapping of application requirements to technologicalrequirements, since the former can be properly represented at higher abstraction levels and thelatter at lower ones. Third, in case formal methods are used, the relation between adjacentabstraction levels can be formalized as an implementation relation, facilitating the develop-ment of (semi-)automatic design support tools (e.g. for validation and transformation).

The ODP-RM identifies a set of different views of the system, calledviewpoints. However,we observe that the ODP viewpoints are not properly related. Although there are some rela-tions and commonalities between the different viewpoints there seems to be no explicitconsistency relation between them. These explicit relations are indispensable from adesigner’s point of view. For example, the requirements in the enterprise viewpoint are visibleas environment constraints (quality of service, dependability, and so on) in the computationalviewpoint, but it is unclear how the choices made at the computational viewpoint are influ-enced by the enterprise viewpoint. Another problem is how different viewpoint descriptionscan be considered in combination, forming a single reference for implementation.

The establishment of hierarchical relationships between viewpoints is a possible solution tothe problems above. Although in principle hierarchical relationships can only be establishedfor certain aspects of viewpoints, according to the definition of viewpoint in the current ODPwork, viewpoints can not be considered as related abstraction levels. However a tendency ofconsidering viewpoints as abstraction levels can be observed, such as in recent versions of (thenon-prescriptive) Part 1 of [7].

Rule 3:Abstraction levels should address the common behaviour of a system and its environ-ment, the role of the system in this common behaviour, and the decomposition of thisroleFuture users of a system under design are first of all interested in the total behaviour thatresults from using the system. This behaviour allows the reflection of application require-ments with respect to the system at the highest abstraction level.

A proper design concept that supports this abstraction is the concept ofservice. The serviceconcept has a long history in the OSI-RM, although it has often been misinterpreted, andtherefore sometimes used ineffectively. A service should correspond to the shared boundary ofa system and its environment. The service behaviour defines the common behaviour of asystem and its environment in terms of integrated interactions (service primitives in OSIterminology). An integrated interaction is defined independent from the possible individualresponsibilities of the system and its environment; they should be considered asactions, ratherthan interactions.

Here lies the difference with the concept ofservice provider, another concept that is used inthe OSI-RM. A service provider embodies the responsibility of the system in the commonbehaviour defined by the corresponding service. A service provider can be defined as a singleentity of behaviour, in terms of its contributions tointeractions with the environment. Theservice provider, therefore, can be considered as a component of the decomposition of theservice. The service provider behaviour defines the role of the system in the common behav-iour of a system and its environment. Another concept defined in the OSI-RM is that ofprotocol, which defines the internal structure, or decomposition, of a service provider in termsof a composition of protocol entities and a lower level service.

4

It follows that the concepts of service, service provider, and protocol, support the definitionof a system at three subsequent abstraction levels. These levels can be used iteratively in adesign methodology.

The way in which the concepts of service, service provider and protocol relate to view-points is not explicitly defined. For example in some cases a service-protocol relationship isconsidered between models of the computational and engineering viewpoints, but such a rela-tionship is an intuitive interpretation, not supported by the ODP-RM.Rule 4:A design model must suit the purpose of its application area

A design model consists of a set of elementary design (or architectural) concepts which canbe used as general purpose building bricks for the composition of designs. Obviously, a designmodel should suit the purpose of the application area at hand. Despite its triviality, thisrequirement is often compromised by the unconditional adoption of modelling or specificationtechniques with preconceived limitations.

A common source of problems comes from considering a design and its specification as thesame entities, whereas they should be considered as distinct entities. A design is an abstrac-tion of a technical object, as conceived by a designer. A specification is only the representationof a design, albeit the only thing that allows others to look at the design. Hence, in case a spec-ification language has severe limitations in its expressive power, design concepts supported bythis specification language are merely approximations of the design concepts appropriate tothe application area ([22]).

Design concepts play a central role in a design culture: they determine how designs can becomposed, understood and manipulated, and therefore should influence the development ofmodelling techniques, design methods and specification languages. However it is not easy todetermine whether a set of design concepts is appropriate. Often heuristics are involved:design concepts should be appealing to the designer, allow him to conveniently address, at thecorrect level of abstraction, all design concerns relevant to the application area. In addition,they should observe qualitative architectural principles such as generality, orthogonality andparsimony.

The ODP-RM defines a large number of design concepts, including elementary designconcepts (basic modelling concepts in ODP terminology). A subset of these design conceptsstem from an object-oriented modelling approach and not primarily from needs of the applica-tion area. Consequently, the relationship between these concepts and the elementary designconcepts is not always clear. This lack of clarity does not imply that the object-orientedparadigm is unsuitable for ODP; it might be useful to express these concepts. However, theconcepts should be motivated from the designer point of view, tailored to the application area.Rule 5:A specification language should accommodate the design model

A design culture should only adopt a specification language if this language allows astraightforward and intuitive representation of the design concepts, and compositions thereof,as defined by the design model. If a language is introduced, however, with little regard of thisrequirement, one easily runs the risk of only considering the characteristics of systems in thelight of the design model imposed by the chosen language. As a result, design conceptsbecome obscured by preconceived language limitations and designers may even be forced totake improper design decisions.

A defined unique mapping between the elementary design concepts of the design modeland constructs of a specification language representing these concepts is calledarchitecturalsemantics. The architectural semantics of a specification language allows the interpretation of

5

a specification in terms of the interpretation of constructs corresponding to elementary designconcepts.

Available standard specification languages for open distributed systems show severe limita-tions in the representation of design concepts. It is then important to acknowledge such limita-tions and find ways to compensate for them. Enhancements should follow from carefulconsideration of the design concepts adopted, and not concentrate purely on manipulation ofthe semantic models of these languages.

A specification language should be applicable at each of the abstraction levels used in adesign methodology. In particular, a specification language should permitdescription as wellasprescription. Observable behaviour for example can be considered as a description,whereas behaviour that is defined in terms of an explicit internal structure can be consideredas a prescription. The former is of interest to the future user, the latter to the implementor ofthe system. In both cases, behaviour can be considered as behaviour that can be interpreted bydesigners. This changes the concept of observability: designers prescribe the behaviour of asystem, making it possible for implementors to use this prescription in order to construct thesystem. As a result, actions and interactions are to be considered in a single framework, fromwhich designers can make implementation decisions explicit.

3Entity Domain and Behaviour Domain

In most approaches towards the design of distributed systems one can recognize the exist-ence of the following architectural concepts (see [5], for example):

•(functional) entity, which is a logical or physical component of the system•action, which is an abstraction of an activity performed by an entity•interaction, which is an action shared by two or more entities

•action point, which is the logical location for the execution of an action

•interaction point, which is the logical location for the interaction between entities.Considering these architectural concepts we can identify two distinct domains for systemdescription:

•theentity domain, in which the actors of behaviour, i.e. the entities, are defined, and•thebehaviour domain, in which the behaviours of the entities are defined.

The entity domain considers aspects related to the structure of entities. These aspectsinvolve the identification of the entities represented in the design, and their interconnection.An entity is delimited by interaction points and contains action points. Interaction points areshared by two or more entities, forming the common means of interaction of these entities.Each action point, however, can only belong to a single entity.

The behaviour domain considers aspects related to actions and interactions, and the rela-tionships between them, which characterize behaviour. These relationships are calledcausality relations. Behaviours, especially complex ones, have to be structured in terms ofbehaviour compositions. We consider behaviours from a prescriptive point of view, i.e. theyshould be interpreted by the implementor as prescriptions of functional entities on how tobuild them.

There is a mapping from the behaviour domain onto the entity domain, such that behav-iours are assigned to functional entities, and actions and interactions are assigned to action

6

points and interaction points. The composition of the behaviours assigned to entities has to becompatible with this combination of entities. This implies that interactions between entitiescan only occur at common interaction points, i.e. through which these entities are intercon-nected.Figure 1 depicts the aspects considered by the entity and behaviour domains.Entity DomainFunctional EntitiesAction PointsInteraction PointsEntity CompositionmappingBehaviour DomainActionsInteractionsCausality RelationsBehaviour StructuringFigure 1: Entity and Behaviour DomainsMost design cultures lack the identification of entity and behaviour domains and concen-trate on only one of these domains, while to our belief attention should be drawn to both. Forexample, in the elaboration of a design at a certain abstraction level one needs to define theentity structure as well as the behaviour assigned to each specific entity.Figure 2 illustrates the entity domain and the behaviour domain and their relations for anarbitrary combination of entitiesF1,F2,F3 andF4. Behaviours B1, B2,B3andB4 are assignedtoF1,F2,F3 andF4, respectively.ip1,ip2,ip3 andip4 are interaction points, andap1 andap2are action points. The composition of behavioursB1, B2,B3andB4 should represent thecomposition of entitiesF1,F2,F3 andF4. For example, interactions shared byB1 andB3canonly occur at the interaction pointip2.Entity Domainip1ip2Behaviour DomainF1ap1ip3F4F2ip4representscompositionof entitiesCompositionBehaviourB1BehaviourB2BehaviourB3BehaviourB4F3ap2Figure 2: Example in Entity and Behaviour Domains7

4Five Related Abstraction Levels

Considering an arbitrary open distributed system, there are many possible alternativechoices for the selection of abstraction levels. However, since we aim at applying theseabstraction levels to system development, we have identified abstraction levels by definingtheir relative position in the total design trajectory and their global design goals. In an instanceof a design process, where initially the system of interest does not exist and has to be built,these abstraction levels can be traversed from the higher abstraction levels to the lower, suchthat increasingly more details of the system are considered.

The identification of abstraction levels is most conveniently performed in the entitydomain. The abstraction levels are therefore characterized by (compositions of) entities.

4.1System Embedded in its Environment

Objective: definition of the application environment in which the system has to operate, interms of entities of this environment and their cooperation. This abstraction level is useful todetermine the activities of the (bounded) environment which should be supported by thedistributed system and to determine which degree of support should be achieved.

This abstraction level is especially helpful when a system has to be designed from scratch,and has to be incorporated in an environment with the goal of supporting or enhancing somefunction of that environment. Effective applications of the system generally require that insuch a case also the design of some activities of the environment has to be reconsidered.Examples can be found in the area of Computer Supported Cooperative Work (CSCW), wheresocio-technical systems are designed consisting of a computer system and a work organizationin which the system is embedded ([1]).

It appears that little experience exists in the development of models at this abstraction level.Possible reasons for that are (i) the variety of applications, which makes it necessary to cate-gorize them and to develop different models for different categories of applications, and (ii)the need for expertise on these different application areas for a proper modelling.

Since this abstraction level is used to explore the role of the system in support of somefunction of the environment, aspects of the environment, i.e. outside of the system, as well asaspects of the (role of the) distributed processing system may be considered.

4.2Interaction System between System and Environment

Objective: definition of the shared boundary between the system and its environment. Thisabstraction level assigns the common behaviour performed by a system and its environment toa single functional entity, theirinteraction system, such that distributions of responsibilitiesand constraints between the system and the environment are not considered.

At this abstraction level many requirements of the common behaviour of the system and itsenvironment can be defined, such as temporal ordering of actions, timing and reliabilityaspects, etc. Models at this abstraction level should be derived from the definition of thesystem embedded in its environment, by proper selection of functions.

Figure 3 illustrates the system embedded in its environment and the interaction systembetween system and environment.

The environment which embeds the system is shown in Figure 3 as consisting of threeparts, reflecting some actual structure of the environment, with cooperation between the partsrepresented by double headed arrows. Although not considered at this level, the cooperationbetween parts may not be direct, but through intermediate entities. The purpose of the systemdesign may then be to find a proper implementation of this cooperation.

8

PartAPartBApplicationEnvironmentPartCOpen Distributed System= action pointInteractionSystemFigure 3: System Embedded in its Environment and Interaction System between System andEnvironment4.3Integrated Perspective of a SystemObjective: definition of the behaviour of the system as it is observed by its environment. Atthis level of abstraction we consider the responsibilities and constraints that have to beassigned to the system and to its environment in performing interactions. Possible internalorganizations of the system that result in the same observable behaviour are not considered atthis abstraction level.Models at this abstraction level should be derived from the definition of the interationsystem between system and environment, by proper selection of responsibilities in the estab-lishment of interactions between system and environment.Figure 4 illustrates the interaction system between system and environment, the integratedperspective of a system, and their possible relationship.4.4Partitioned Perspective of a SystemObjective: definition of the application support functions, without considering the commu-nication infra-structure (distribution). This abstraction level identifies logical functions thatsupport the functional requirements of the integrated perspective of the system, such that theircombination conforms to the integrated perspective of the system. It should be derived fromthe definition of the integrated perspective of the system, by identifying (logically) orthogonalfunctions and distributing them onto application support components.Figure 5 illustrates the integrated and the partitioned system perspectives and their possiblerelationship. The partitioned perspective should conform to the integrated perspective, suchthat the behaviour of these two perspectives cannot be distinguished from the environmentpoint of view.9

InteractionSystem= action pointSystem= interaction pointFigure 4: Interaction System between System and Environment and Integrated System PerspectiveSystemAi’s = application functionsA1A4A2A3= interaction pointFigure 5: Integrated and Partitioned System Perspectives4.5Distributed Perspective of a SystemObjective: definition of the functional requirements for inter-working at the application andcommunication levels.The distributed system perspective should be derived from the partitioned system perspec-tive, by considering the communication infra-structure that supports the communicationbetween application functions, taking into account how the application functions use thecommunication infra-structure in order to operate. Cooperation between application compo-nents defined in the partitioned system perspective are supported by the communication infra-structure in the distributed system perspective.Figure 6 illustrates the partitioned and the distributed system perspectives, and theirpossible relationships.Heterogeneity between various implementation environments, such as hardware and oper-ating systems issues, makes it unnecessary and even undesirable to consider standardizationfurther than the distributed system perspective, except for concrete interfacing.10

A1A2A3A4A1'CommunicationInfra-structureA2'A3'A4'= interaction pointFigure 6: Partitioned and Distributed System Perspectives4.6Abstraction Levels and ODP ViewpointsAccording to the current definition of viewpoints in the ODP-RM, viewpoints can not bedirectly mapped onto a set of related abstraction level. However we indicate in the sequelpossible relationships between aspects of the ODP viewpoints and the abstraction levels intro-duced before.The ODP enterprise viewpoint could be related to the abstraction level of the systemembedded in its environment. In particular the behavioural roles and activities performed byODP systems are addressed by this abstraction level.The ODP information viewpoint could be related to the information established in(inter)actions at each of the abstraction levels defined above.The ODP computational viewpoint could be related to the abstraction level of system’spartitioned perspective. Distribution transparent objects, activities and interactions defined inthis viewpoint could correspond to entities, behaviour and interactions of a system’s parti-tioned perspective.The ODP engineering viewpoint could be related to the abstraction level of system’sdistributed perspective. In particular the organization of an abstract infra-structure to supportinterworking corresponds to the communication infra-structure depicted in Figure 6.The ODP technology viewpoint is not considered by our abstraction levels.5Elementary Behaviour ConceptsThe behaviour of an entity is defined in terms of relationships between the actions andinteractions of this entity. These relationships result in a specific ordering between these11

actions and interactions. This section presents a collection of concepts that allow for the defi-nition of behaviours.

5.1Actions and Interactions

We suppose that there is an activity in the real world that we want to model from which alldetails are known. A possible approach is to select the most essential elements of this activityat a certain abstraction level and model them as actions, allowing us to reason about theseactivities without the burden of their details. Therefore we introduce the concept ofactionwhich is a unit of activity that is assigned to a functional entity at a specific abstraction level.Since a designer generally wants to be able to refer to individual occurrences of actions, weassume that each action can be distinguished from the others. Actions are distinguishedaccording to specific modelling and design goals. This means that we can, for convenience,assign a uniqueidentifier to each action, allowing to refer to each individual action.

An action can be characterized by one or moreattributes. The following attributes areconsidered in this text:

•location: defines where an action is allowed to occur;•time: defines when an action is allowed to occur;

•information (local results): defines the possible results of an action, in terms of values ofinformation established by its occurrence;•functionality (passed results): defines values of information that are passed to an action byprevious actions, so extending the local results of the action.We should be able to define what values are possible for an action’s attributes. Restrictionson the values of an attribute are calledconstraints. An attribute may have zero, one or moreconstraints associated with it.

The following examples illustrate some possible actions:

ab (v: Nat)

c (v: Nat) [2 < v < 10]

action with identifiera, no attributes considered

actionb, with unconstrained information attribute of typeNatactionc, with information attribute of typeNat, constrainedbetween the values2 and10

Aninteraction is a unit of activity that is common to two or more functional entities, and isdefined such that the contributions of each functional entity to the interaction can be distin-guished. An interaction can therefore be considered as a decomposition of an action in thesense that its occurrence is visible to the involved functional entities, and its attribute valuesare determined by the conjunction of individual constraints imposed by all the participatingfunctional entities. A contribution of a functional entity to an interaction can be characterizedusing the same attributes as the ones we have considered for an action.

We illustrate some interactions, with contributions from two functional entities, that corre-spond to the actions above.

interaction contribution 1ab (v:Nat)

interaction contribution 2ab (v:Nat)

corresponding actionab (v:Nat)

12

c (v:Nat) [v < 10]c (v:Nat) [v > 2]c (v: Nat) [2 < v < 10]

In the following, we use the termaction to refer to actions or interactions, unless it is feltnecessary to be specific about one of them.

5.2Causality Relations

The role of an action in a behaviour is determined by its relationships with other actions ofthis behaviour. These relationships are defined by means of causality relations. Acausalityrelation states the conditions which enable and constrain the occurrence of an action. Theseconditions are called theenabling condition for the action, and the action itself is called theresult action. An enabling condition specifies the occurrence and non-occurrence of actionsthat are required for the result action to occur. The result action only refers to the actions in theenabling condition, which can be seen as the minimal state information necessary for theresult action. Causality relations therefore form an appropriate basis for the definition of thebehaviour of opendistributed systems, which do not have a global state, but rather a collectionof ‘sub-states’ (multiple threads of control).

Consider the situation in which an actiona2 is allowed to occur only if another actiona1has occurred. We represent this by the causality relationa1 -> a2, wherea1 is an enablingcondition anda2 is the result action. Although no explicit reference to time attributes areincluded so far, we assume thata1 must have occurred beforea2. This time condition isalways implicitly present in case of causality with the occurrence of an action in an enablingcondition.

Consider now the situation in which an eventa2 is allowed to occur only if another eventa1has not occurred (before nor at the same time). We represent this by the causality relation¬a1->a2. The implicit time condition related to this relation is that if botha1 anda2 occur in acertain system run,a1 should occur aftera2.

Arbitrary complex enabling conditions can be constructed by combining occurrence andnon-occurrence of actions using the logical operators∧ and∨. Some elementary examples are:a1∧a2 ->a3a1∧ ¬a2 ->a3a1∨ a2->a3a1∨ ¬a2->a3

(conjunction of occurrences)

(conjunction of occurrence and non-occurrence)(disjunction of occurrences)

(disjunction of occurrence and non-occurrence)

Enabling conditions may be defined in terms of specific attribute values of the enablingaction occurrences. Constraints on the attributes of a result action can make reference toattribute values of the actions in the enabling conditions. Some examples are:

a1 (v1:Nat) [5 < v1 <10] -> a2(the enabling condition ofa2 is thata1 happens with valuev1 between 5 and 10)

a1 (v1:Nat) -> a2(v2:Nat) [v2 = v1 + 10] (the valuev2 established ina2 is constrained by areference to the valuev1 established in actiona1 of the enabling condition)

a1 (v1:Nat) [5 < v1 <10] -> a2(v2:Nat) [v2 = v1 + 10] (combination of attribute valueconditions and constraints)

13

5.3Behaviour DefinitionThe behaviour of a functional entity can be characterized by the following elements: initialactions, relationships between actions, and termination conditions of the behaviour. We repre-sent behaviour as a set of causality relations between actions, one causality relation for eachaction, which describes the conditions and constraints of this action. Initial actions are enabledby a specialstart condition, which means that these actions do not depend on other actions.Examples of behaviours are:B1 := {start -> a1, a1 -> a2} defines the sequential ordering ofa1and a2.B2 := {start -> a1, a1∧¬a2 -> a3, a1∧ ¬a3 -> a2} defines the sequential ordering ofa1 anda non-deterministic choice betweena2 anda3.B3 := {start -> a1, start -> a2} defines the independence ofa1and a2.5.4Graphical NotationA graphical notation for causality relations is used as an alternative representation to thetextual form presented above. This graphical notation is expected to be useful for helpingunderstanding and analyzing causality relations. In this notation actions are indicated ascircles, and causality relations as arrows. Interactions are represented as circle segments, eachsegment representing a contribution to the interaction, such that the composition of segmentscorresponds to the original common action (see Figure 11 for example).Figure 7 depicts some examples of causality relations between actions and their representa-tion.a1a3a2(a) a1∧ a2 -> a3a2(b) a1∨ a2 -> a3a1a3a2(c) a1∧¬a2 -> a3a1a3a2(d) a1∨¬a2 -> a3a1a3Figure 7: Graphical Representation of Causality RelationsFigure 8 depicts some well-known behaviour patterns using the graphical notation. In thisfigure the conditionsa0∧(a1 ∨ ¬a1) and a0∧ (a2 ∨ ¬a2) are represented in terms of their equiv-alent forms(a0∧ a1) ∨(a0∧¬a1) and (a0∧ a2) ∨(a0∧¬a2), respectively.5.5Mapping onto Petri NetsThis section presents the mapping of causality relations onto place/transition Petri nets([14]). We take Petri nets for this since they support the representation of true parallelism, andmoreover, are based on causal relationships between transitions. Thus we may expect astraightforward and intuitive mapping of concepts like actions and causality relations ontonets. Furthermore, nets have a nice and intuitive graphical representation, and a lot of exten-sions of nets are known, such as timed, stochastic and colored nets, that seem to be usefulwhen decorating actions with attributes like time, probabilities, and values.14

a0a1a2a0a1a2a0a1a2(a) sequential orderinga0a1a2(d) choice(b) independencea1a2(c) disabling(e) arbitrary interleavingFigure 8: Some Behaviour PatternsA net consists of a set of places (represented by circles), a set of transitions (fat bars), aflow relation connecting states (transitions) to transitions (states), depicted as arrows, and amarking assigning one or more tokens (black dots) to some states. A transition, which is thesemantic counterpart of an action, is able to execute when all its incoming states contain atleast one token, that is, when all conditions in the corresponding causality relation arefulfilled. On execution it consumes a token from all its incoming states, and produces (instan-taneously) a token in all its outgoing states. Transitions that are able to execute may execute inparallel; there is no need for interleaving of transitions. The nets that correspond to someelementary causality relations are depicted in Figure 9. We assume that each transition mayfire at most once.abaaababstart -> aa -> bb¬a -> bca∧ b -> cc¬a∨ b -> cFigure 9: Net semantics of Some Elementary Causality Relations.We conjecture that the net semantics of all behaviours constructed from causality relationscan be generated from the three left-most nets of Figure 9 in acompositional way.As an example we consider the net semantics ofa∨ ¬a -> b (see Figure 10),denoting thatb should interleave witha. We also consider that actions may refer to attributes of enablingactions. To model this aspect nets are extended with open tokens, which represent attributesthat may be referred to, and dotted arrows, i.e. transitions along which only open tokens aretransferred. Closed tokens are transferred along solid arrows.Figure 10: Net Semantics ofa∨ ¬a -> b.It should be noticed that it suffices to have either a full or an open token (but not both) to bepresent in the common state in order for transitionb to fire. When only considering the15

ordinary solid transitions, the net is fully symmetric ina andb: ifb is interleaved witha,a isinterleaved withb also. However, when incorporating the way in which actions (transitions)may refer to each others’ attributes, interleaving isnot symmetric asa is not able to refer toattributes ofb, whereas the reverse does hold (whenb is caused bya).

The work on establishing a (formal) semantics is currently ongoing. We stress that a netsemantics is onlyone of several possibilities to assign a semantics to the presented model.Other possible approaches could be, for instance, extensions of event automata ([12]), linear-time temporal logic ([10]), families of posets ([15]), or causal automata ([6]). A net semanticsof finite behaviours is available. Extensions of this work towards a full semantics will include,amongst others, the formalization of implementation relation(s), decorating attributes andconstraints on attributes to causality relations, definition of appropriate equivalence relationsand considering recursive behaviours. This is subject of further research.

6Behaviour Composition

Behaviour definitions in terms of monolithic causality relations, as presented in Section 5,are limited to the representation of simple finite behaviours. Recursion and complexity makesit necessary to introduce extra structuring mechanisms. Causality-oriented and constraint-oriented behaviour composition are the structuring mechanisms presented in this section.

6.1Causality-oriented Behaviour Composition

Behaviours can be structured in terms of causality relations between behaviours, ratherthan between actions. A structuring mechanism, to be interpreted as a shorthand notation, hasbeen introduced for this purpose. This structuring mechanism consists of:

•entry points: points in a behaviour that can be used to allow other behaviours to enableactions of this behaviour;•exits: conditions in a behaviour that can be used to enable actions of other behaviours.Behaviours can be composed by relating their exit and entry points. Entry points and exitsare denoted with the keywordsentry andexit, respectively. An example is:B := {start -> B1(entry), B1(exit) -> B2(entry)}where

B1 := {entry -> a1, a1 -> a2, a2 -> exit}B2 := {entry -> a3}In this example the entry ofB1 is enabled by a start, and the entry ofB2 is combined to theexit ofB1, such thata2 becomes a condition fora3.

Similarly to causality relations between actions, causality relations between (entries andexits of) behaviours allow the reference to attribute values. An example is:B := {start -> B1(entry), B1(exit(v2: Nat)) -> B2(entry(v2))}where

B1 := {entry -> a1, a1 -> a2(v2: Nat)[v2 = 5], a2(v2:Nat) -> exit(v2)}B2 := {entry(v2: Nat) -> a3(v3:Nat)[v3 < v2]}

In this example,a2 establishes value5, which is forwarded toa3 by theentry/exitconstruct.After thata3 establishes a value which is smaller than5.

We generalize the causality relations above in order to allow behaviours and actions toenable each other. An example is:

16

B := {start -> B1(entry), B1(exit) -> a3}where ...Structuring behaviours in terms of these generalized causality relations allows reusabilityof components and the definition of hierarchies of behaviours in terms of sub-behaviours. Thisstructuring technique is calledcausality-orientedbehaviour composition.The notion of entryand exit points in a behaviour can be generalized in a natural way to allowing multiple entryand exit points. In this way, behaviours can be composed in a flexible way.6.2Constraint-oriented Behaviour CompositionAnother structuring approach is based on the conjunction of constraints on actions, whichare defined in separate behaviours. This structuring technique is called theconstraint-orientedbehaviour composition. It forces us to represent actions in a distributed form, since eachaction to be distributed is defined by a collection of causality relations in different behavioursthat represent the constraints on the action. The combination of these causality relationscompletely determines the (constraints on) the action.There are some options for the decomposition of a behaviour in sub-behaviours that repre-sent constraints. Each individual action can be assigned to just one sub-behaviour or it can beshared by more than one sub-behaviour. Furthermore, in case an action is shared by sub-behaviours, its conditions and constraints, which were defined in a single causality relation inthe monolithic behaviour definition, can be again distributed over these sub-behaviours inmany different ways. These choices determine the design freedom designers have, and shouldbe selected according to specific design objectives and quality principles.Figure 11 shows an example of two design choices for the decomposition of a behaviour inconstraints.a1a5a4(a)a1a2a4B1(b)a3a5a4B2a2a3a4B1(c)a1a2a3a5a4B2a2a3a2a3Figure 11: Example of Behaviour Decompositions in Constraints (a) Monolithic Behaviour, (b)Decomposition 1, (c) Decomposition 217

Figure 11(a) considers a monolithic behaviour which we want to structure such that actionsa2,a3and a4 are distributed over sub-behavioursB1 andB2. These sub-behaviours representspecific constraints on actionsa2,a3and a4. Actionsa1 anda5 are not distributed, beingassigned toB1 andB2 respectively. We refrain from discussing the specific design objectivesthat motivated these choices and the decomposition choices that follow.Figure 11 (b) and (c) show two possible constraint-oriented decompositions of the mono-lithic behaviour of Figure 11(a). Non-decomposed actions are shown as circles, and decom-posed actions are shown as semicircles. This graphical notation is used throughout this work.Conditions can be duplicated in the sub-behaviours. Figure 11 (b) shows, for example, thatconditiona2 enablesa3, can be placed in bothB1 andB2. Conditions can also be distributedover sub-behaviours, since the composition of sub-behaviours implies that conditions andconstraints of bothB1 andB2 apply. Figure 11 (c) shows, for example, that the conditions fora4, namely the occurrence ofa2 and the non-occurrence ofa5 can be distributed, such thatoccurrence ofa2 is guaranteed byB1 and the non-occurrence ofa5 is guaranteed byB2.In some circumstances designers may have no choice of assignment of constraints onactions to behaviours. In Figure 11, the conditiona1 enablesa2, considering the distribution ofactions to behaviours given in the example, can only be placed inB1, which can be seen inFigure 11 (b) and (c).The constraint-oriented behaviour composition supports the development of a design struc-ture that distinguishes between functional entities with interactions between them.6.3Causality versus Constraint-oriented CompositionCausality-oriented behaviour composition using theentry/exit mechanism corresponds todecomposing causality relation(s) such that the conditions and result(s) are put in separatebehaviours. The graphical representation of causality-oriented composition is that the condi-tions of causality relations are disconnected from the result actions. Figure 12 compares thegraphical interpretation of causality-oriented and constraint-oriented behaviour compositionsObserving Figure 12 we can notice that the causality-oriented behaviour composition looks asif someone has cut the causality relations with a knife, defining sub-behaviours in this way. Inthe constraint-oriented behaviour composition the knife goes through the actions, generatingsub-behaviours that share these actions.B1B2B1B2(a)(b)Figure 12: Graphical Representation of (a) Causality-oriented Behaviour Composition and(b) Constraint-oriented Behaviour Composition18

7Framework for Design and Implementation

This section discusses the application of our design model in a framework for the designand implementation of distributed systems.

7.1Entity Composition and Behaviour Structuring

There are two main purposes for applying structuring in design: (i) understandability,which aims at getting overview of a complex design, and (ii) prescription for implementation,which aims at defining compositions of parts that should reflect the system implementation.Entity structuring relates to prescription for implementation, i.e. a composition of entitiesis interpreted as the structure to be found in the actual implementation of the system.

Behaviour structuring can relate to both understandability and prescription for implementa-tion. Understandability is supported when a certain structured behaviour (causality-oriented,constraint-oriented or a combination of both) is mapped onto a single functional entity.Prescription for implementation is supported when representing a composition of entities bythe composition of their corresponding behaviours. In both cases behaviours are assigned tofunctional entities, and the combination of these behaviours has to comply to theconsistencyconditions derived from the combination of functional entities:

•interactions common to two or more behaviours assigned to functional entities happen atinteraction points which are shared by all these functional entities;•actions of a behaviour assigned to a functional entity happen at action points which are partof this functional entity.These rules are the only consistency restrictions to the designer’s freedom to define entitystructures, behaviour structures and their relationship. Practical restrictions arise, for example,from technological limitations and the availability of specific system components.

Figure 13 depicts the design freedom for entity and behaviour domains. This figure showsthat behaviours may be structured as monolithic, causality-oriented, constraint-oriented, ormixed causality-constraint-oriented structures. It also shows that the introduction of interac-tions (interaction points in the entity domain) forces some sort of constraint-oriented composi-tion, either explicit, which means that interactions between functional entities are explicitlydefined, or implicit, which means that only a system in terms of its interactions with an envi-ronment is defined.

Specification styles and their application to formulate LOTOS specifications ([21]) cannow be placed in the perspective of these two domains. Since LOTOS does not support aseparate definition of entity structuring and behaviour structuring, this could only be donenow that we have obtained a more comprehensive framework.

The monolithic specification style corresponds to an unstructured representation of thebehaviour of a functional entity. The constraint-oriented specification style also concentrateson the behaviour specification of a single functional entity, structuring this behaviour in termsof a composition of constraints, and corresponds to the constraint-oriented behaviour compo-sition. The resource-oriented specification style concentrates on the representation of entitycompositions by means of the composition of their behaviours, and considers a specificassignment of behaviours to functional entities, which can be generated from constraint-oriented behaviour compositions. The state-oriented specification style corresponds to therepresentation of the behaviour of a specific functional entity based on some assumptions onhow this functional entity should be implemented in terms of a finite state machine.

19

Entity DomainBehaviour DomainmonolithicbehaviourAction PointsInteraction Pointscausality-orientedcompositionconstraint-orientedcompositionmixedcausality-constraintAction andInteractionPointsFigure 13: Design Freedom for Relating Entity and Behaviour Compositions7.2Design StepsOne of the benefits of identifying and working out separate but related models for the entityand behaviour domains is that this distinction enables a clear separation of design concerns forthe characterization of design steps.The design objectives of some important design steps are defined from the entity domain,in terms of manipulations of elements in this domain. Examples of such steps are functionality(entity) decomposition and interaction point refinement ([16]). Although the objectives ofthese design steps originate from the entity domain, they are also characterized by conditionsthat apply to the behaviour domain, thus defining correctness criteria for them.Other design steps may have their objectives originated from the behaviour domain, andare defined in terms of manipulations solely in this domain, while the entity composition withits actions and interaction points remains intact. Examples are reduction of non-determinismand behaviour reduction or extension ([16]).In the sequel we define two design steps, entity decomposition and introduction of actionpoints, and discuss how these steps can be applied to perform design steps such as the onesdetermined by the abstraction levels presented before.Entity DecompositionEntity decomposition is a design step in which an entity of a certain abstraction level isreplaced by more, possibly cooperating, entities at the next lower abstraction level. We restrictentity decomposition to a specific treatment of interaction and action points and specificbehaviour conditions. We suppose that in the entity domain the following conditions hold:1.original interaction points of the functional entity are also found in the decomposition,and2.original action points are either maintained or transformed into interaction points in thedecomposition.Figure 14 depicts an example of entity decomposition.In the behaviour domain we define the conformance between the composition of the behav-iours of the decomposed functional entity and the original behaviour of the functional entity.20

ip2ip1ap1ap2ap3ip4ap3turns into ip1'ap4turns into ip2'ip3ip1ip2ip3F1ap4f1ap1ip2'f2ap2ip1'f3ip4f4Figure 14: Entity Domain of Entity Decomposition ExampleWe expect that some form ofbehaviour isomorphism applies, in which some internal behav-iour and relationships between the original interactions and actions are preserved by thedecomposed functional entity. In this area we think that most research is yet to be done.Introduction of Action PointsIntroduction of action points is a design step in which action points are introduced in afunctional entity.We suppose that in the entity domain the following conditions hold:1.the original interaction and action points of the functional entity are still found in the de-composition, and2.some action points are introduced in the decomposed functional entity.We may consider these new action points to be placed between existing actions or interac-tion points, such that in the behaviour domain we are forced to decompose the relationshipsbetween actions or interactions according to the placement of action and interaction points. In the behaviour domain the condition seems to be a partial behaviour isomorphism, inwhich the relationships between the original actions and interactions is preserved in thedecomposition. Again some research on this topic is necessary.A specific form of partial behaviour isomorphism is the observable behaviour condition, inwhich behaviour as observed by the environment of a functional entity is supposed to bepreserved by the decomposed functional entity. Several variations of this condition are avail-able in the literature for process algebras, such as weak bisimulation equivalence, testingequivalence, etc. ([18]).Figure 15 depicts an example of introduction of action points. This example shows that theintroduction of action points may contain some more conditions concerning the relativeposition of the action points. In the example, action points ap3 andap4 are placed betweenap1and ap2, such that all direct relationships between actions inap1 and ap2 should now be madethrough actions atap3 andap4. In this simple example, the original condition thata1 is acondition fora2 is indirectly preserved by actionsa3 anda4 in the decomposed behaviour.7.3RecursionThe design steps introduced in this section can be used recursively, defining a design meth-odology for the design and implementation of distributed systems. For example functionalentities at some abstraction level can be decomposed, and the resulting decomposition yieldsagain functional entities that can be decomposed and so on.Figure 16 illustrates an example of recursive application of design steps.21

Entity Domainap1ap2Behaviour Domaina1(atap1)a2(atap2)F1ap1ap2ap4a1(atap1)a2(atap2)F1'ap3a3(atap3)a4(atap4)Figure 15: Example of Introduction of Action Points in Entity and Behaviour Domainsip2ip1F1ap1ap2ip3ip4ip1ap1ip2f1f2f4ip3ap2ip1'f3Introduction ofAction Pointsip1ip2'ip2ap1ap4ap3ap2ip3ip4EntityDecompositionip1ip4F1Introduction ofAction Pointsap1ip1'f1ip2'ap1'Figure 16: Recursive Application of Design Steps in Entity DomainThe design steps between the abstraction levels presented in Section 4 relate to the designsteps presented before. The table below presents this relationship.Embedded System -> Interaction SystemInteraction System -> Integrated SystemIntegrated System -> Partitioned SystemPartitioned System -> Distributed SystemIntroduction of action pointsEntity decompositionIntroduction of action points andEntity decompositionRecursion22

...EntityDecomposition8ExampleThe use of our design model is illustrated by the design of a system which supports aMultimedia Information Exchange Service (MIES). This example shows how a designprocess can be carried out in a stepwise fashion according to the methodology presentedbefore. Furthermore, it shows how real concurrency and timing conditions can be dealt with,which are notorious problems with many existing specification languages. It is clearly not ourintention to focus on technological solutions to the problem of multimedia informationexchange. Our example, therefore, simplifies the problems encountered in practical settings.8.1Informal Description of the Design ProblemIn the context of multimedia systems, a medium denotes a type of information such as data,voice, audio, and video ([17]). A multimedia system supports multimedia applications thathandle several media in an integrated fashion. In the case of a distributed multimedia system,this induces specific requirements on the subsystem that is concerned with the exchange ofmultimedia information between remote application processes. One significant requirement isthat ofsynchronization, which assures a temporal relationship between information elementsin accordance to the application.In this example we consider the exchange of live audio and video between a source and asingle destination. Audio and video are stream media, i.e. media that may be expressed as afunction of real-time. Together they form a multiple stream, with sound-track synchroniza-tion1 between the audio and video component. Since audio and video have different character-istics (e.g. in terms of sensitivity to delay variations and loss of samples), it is often desirableto treat these streams independently during transmission over a network ([9],[11]). For thisreason we decompose the multiple stream into two single ones, viz. an audio and a videostream. Figure 17 depicts the example.SourceExchangeVideoAudioVideo StreamAudio StreamVideoAudioBla-blaDestinationFigure 17: Exchange of Audio and VideoThe synchronization requirements are formulated as follows:1.the function of time of both audio and video streams should be preserved2. This meansthat the rate at which audio and video samples are produced at the source should be equalto the rate at which they arrive at the destination;1.The term sound-track synchronization comes from motion pictures celluloid where the sound is recorded in atrack along the picture frames. This kind of synchronization for voice and video is often called lip synchroni-zation.2.Within predefined limits, determined by human auditorial and visual perception, deviations can be tolerated.This is not further discussed here.23

2.

the sound-track synchronization between audio and video should be preserved. Thismeans that the temporal relationship between audio samples and video samples at thesource should also apply at the destination.

In the following, we assume that the stream components areisochronous in nature, i.e. theaudio and video samples are generated at fixed time intervals. Furthermore, we do notconsider the possibility of loss or corruption of samples.

The design problem is formulated independent of a specific application environment (e.g.video-conferencing), but rather in terms of general purpose multi-media support. Thereforewe start the design at the abstraction level of the interaction system between the system and itsenvironment, rather than at the abstraction level of the system embedded in its environment.

8.2MIES Definition

The MIES design is concerned with the target application of the system, i.e. the exchangeof audio and video such that the synchronization requirements are fulfilled. This enables theplayback of audio and video at the destination as generated at the source. The MIES designdoes not address the possible limitations of available network technology, the synchronizationanomalies that may occur as a consequence of these limitations, and the corrections of theseanomalies such that the original goal (as presented by the MIES design) is attained. Theseconcerns are deferred until next design steps. During later design steps it may turn out that therequirements set by the original goal cannot be satisfied. In such a case, a new, less ambitiousgoal should be formulated, leading to changes in the MIES design.

In the entity domain, we consider the MIES as an entity containing four action points.There are two action points co-located with the source,a_in andv_in, associated with theaudio and video stream respectively; and there are two action points co-located with the desti-nation,a_out andv_out, respectively associated with the audio and video stream.

In the behaviour domain, the submission of a sample and the arrival of a sample are repre-sented as distinct actions. The submission of an audio sample is identified asa_req, and of avideo sample asv_req; the arrival of an audio sample is identified asa_ind, and of a videosample asv_ind. The isochronous nature of the streams is represented by the constraint thataudio samples are separated in time by the sampling delay∆a, and video samples by thesampling delay∆v. The synchronization requirements are represented by the constraint that thedelay between submission and arrival of samples is constant (requirement 1) and theconstraint that this delay should be identical for both streams (requirement 2). This delay, thelatency or transmission delay, is denoted byδ.

Figure 18 shows the representation in both domains.

A textual representation of the MIES behaviour is given below.

MIES_behaviour := {start -> a_req,

a_req -> a_ind [ta_ind = ta_req +δ],a_req -> SAudio (entry (ta_req)),start -> v_req,

v_req -> v_ind [tv_ind = tv_req +δ],v_req -> SVideo (entry (tv_req))where

SAudio := {entry (t0)-> a_req [ta_req = t0 + ∆a],

a_req -> a_ind[ta_ind = ta_req +δ],a_req -> SAudio (entry (ta_req)) }

SVideo := {entry (t0)-> v_req [tv_req= t0 + ∆v],

24

MIES_behavioura_reqa_req'∆aδa_req''∆aδat a_inSourcea_inv_inDestinationδ∆aSAudioa_outv_outat a_outa_indv_reqv_req'∆vδa_ind'v_req''∆vδa_ind''at v_in∆vδMIESSVideoat v_outv_indv_ind'v_ind''Figure 18: MIES Representation in Entity and Behaviour Domainv_req -> v_ind [tv_ind = tv_req +δ],v_req -> SVideo (entry (tv_req)) } }8.3MIES Provider DefinitionThe next step is an application of entity decomposition where we determine the assignmentof responsibility in the MIES actions to the system supporting the service, i.e. the MIESprovider (MIESP). We assume that the MIESP is able to support the exchange of audio andvideo streams with constant as well as variable sample rates up to a certain maximum,depending on the sample sizes. This maximum concurs with the maximum throughput (interms of samples/sec) supported by the MIESP. Assuming a fixed size for audio and videosamples, we denote the maximum throughput supported for audio by 1/λa, and the maximumthroughput supported for video by1/λv.The constraint on the submission of audio samples, from the MIESP point of view, is thenthat audio samples are separated in time by at least a time periodλa. Similarly, video samplesshould be separated by at least a time period λv. In order for the MIESP to support the MIES,twoconditions apply:λa <∆a andλv <∆v. Furthermore, the MIESP is responsible for assuringthat the transmission delay is equal toδ, as specified in the MIES definition.Figure 19 represents the MIESP.A textual representation of the MIESP behaviour is given below.MIESP_behaviour := {start -> a_req,a_req -> a_ind [ta_ind = ta_req +δ],a_req -> SPAudio (entry (ta_req)),start -> v_req,v_req -> v_ind [tv_ind = tv_req +δ],v_req -> SPVideo (entry (tv_req))where25

MIESP_behavioura_reqa_req'a_req''at a_inSourcea_inv_inDestinationa_outv_outδδSPAudioδat a_outa_inda_ind'a_ind'' [ta_req'≥ ta_req +λa]MIESPat v_inv_reqλvδv_req'λvδv_req''λvSPVideoδat v_outv_ind'... [tv_req'≥ tv_req +λv]v_indv_ind''Figure 19: MIESP Representation in Entity and Behaviour DomainSPAudio := {entry (t0)-> a_req [ta_req≥ t0 + λa],a_req -> a_ind[ta_ind = ta_req +δ],a_req -> SPAudio (entry (ta_req)) }SPVideo := {entry (t0)-> v_req [tv_req ≥ t0 + λv],v_req -> v_ind [tv_ind = tv_req +δ],v_req -> SPVideo (entry (tv_req)) } }8.4MIEP DefinitionAccording to our methodology, the logical next step in the design process (that is, the parti-tioned perspective) would be the consideration of a decomposition of the MIESP in terms ofinteracting application support functions. However, since the MIESP is only concerned withtransfer and not with processing of multimedia information, we cannot ignore the distributionof functions, and should therefore immediately consider a distributed perspective of thesystem. This distributed perspective is called the Multimedia Information Exchange Protocol(MIEP).The MIEP design considers the fulfillment of the synchronization requirements in the lightof the characteristics of general purpose end-to-end data communication systems. Generalpurpose communication systems are characterized by the supported data transfer quality ofservice (QoS), including properties such as data unit size, throughput, transfer delay, and reli-ability. In this example, we only consider throughput (in terms of data units/sec) and transferdelay in relation to two categories of data units: those that carry an audio sample (audio dataunits), and those that carry a video sample (video data units).This design step can be seen as an application of the introduction of action points (Section7). In the entity domain we represent the MIEP by four interaction points and four action26

points. The interaction points are the same as those of the MIESP. The four action points areassociated with the transfer of data units, one pair for the transfer of audio data units and onefor the transfer of video data units. Although data transfer is assumed to be transparent, i.e.independent of the data contents, the two data transfer paths can be used to support differentQoS properties in order to suit the different characteristics of audio and video streams. Theaction points where data units are sent are namedda_in anddv_in; the corresponding actionpoints where data units are received are respectively namedda_out anddv_out. Notice that thefour action points can be viewed as being the action points contained by a data transfer service(DTS). In the following, we will only further discuss the transfer of audio data units; bysymmetry, a similar reasoning can be applied to the transfer of video data units.

An audio sample should be presented to the destination after latencyδ. This means that theactual transfer delay of an audio sample, received in an audio data unit, should be known tothe receiving side in order to provide for the required additional delay. In this example, weassume that the sending and receiving side have synchronized clocks. The sending sideattaches a time stamp to the sample, and they are together transferred in an audio data unit. Atthe receiving side, the actual delay is determined by comparison of the time stamp with thelocal clock, and the sample is buffered for the time that remains until the control time expires.We denote the properties that characterize the transfer of audio data units as follows:•the transfer delay varies in betweenδa- andδa+(delay jitter); and•the maximum throughput is 1/λda data units/sec.

Furthermore, the total protocol processing time per data unit at the sending and receivingside is denoted byδp. Given the requirements expressed in the MIES behaviour, the followingconditions apply:δa+ +δp≤ δ, andλda≤λa.

In the MIEP behaviour, the following constraints should be expressed with respect to asend action, identified asda_req, and a receive action, identified asda_ind:

•the elapsed time betweena_req and the correspondingda_req is at mostδ -δa+. Moreover,assuming equal processing times at the sender and receiver, the maximal elapsed timebetweena_req andda_req is (δ -δa+)/2;•the minimal time between two subsequentda_req’s isλda;

•the time period betweenda_req and the relatedda_ind is betweenδa-andδa+;

•the time period between ada_ind and the relateda_ind is equal to the local protocolprocessing time (at most (δ -δa+)/2) plus the buffer time. This time period is calculated bythe receiver entity on basis of the current time (concurring with the time at which thea_indoccurred) and the time stamp (indicating the time at which the relateda_req occurred) asfollows:δ - (current time - time stamp).Figure 20 shows the representation of the MIEP so far (the constraints onda_reqandda_ind are not indicated).

Another, more refined, representation of the MIEP can be obtained by application of entitydecomposition, where the action points are transformed into interaction points of protocolentities and a DTS provider. Figure 21 depicts this decomposition, introducing separateprotocol entities for the support of audio and video streams (only those in support of the audiostream are shown).

27

[ta_req'≥ ta_req +λa]a_reqa_req'a_req''...Sourcea_inv_inDestinationa_outv_outda_reqda_req'da_ind'da_req''da_ind''da_indv_inDTSda_outdv_outda_indMIEPa_ind[ta_ind = ta_req +δ]a_ind'a_ind''Figure 20: MIEP Representation in Entity Domain (without Entity Decomposition)and Behaviour Domain (Support of Audio Stream only) [ta_req'≥ ta_req +λa]a_reqa_req'a_req''...Sourcea_inv_inDestinationa_outv_outMIEP layerDTSa_ind[ta_ind = ta_req +δ]a_ind'a_ind''Figure 21: Decomposed MIEP Representation in Entity Domain and Behaviour Domain(Support of Audio Stream only)9Concluding RemarksThis paper discusses demands of design methodologies for ODP systems, and concludesthat the current status of ODP-RM standard does not fully support these demands. This moti-vated the development of a design model. The purpose of this model is to support the designof open distributed systems in a systematic stepwise fashion. We argued that the concepts ofthis design model are useful in the context of ODP, namely for supporting the development ofconsistent and parsimonious standards in that area.The basic design concepts for distributed systems have been grouped in two domains, viz.the entity domain and the behaviour domain. These two domains and their relationships form28

a framework for design and implementation, in which design steps can be precisely formu-lated and performed. We have furthermore identified a number of related abstraction levelsthat can be used as milestones in a stepwise design process and we have related these abstrac-tion levels through design steps, providing some guidance to designers.

The novelties of our approach are the explicit use of entity and behaviour domains, the useof actions and interactions in a single behaviour model, and the representation of behavioursthrough causality relations between actions and interactions. It is our belief that our model iscomplete with respect to functional requirements, such as timing, real parallelism and data.Aspects related to action probability are also being studied in the same framework. Furtherwork should be done on the precise definition of implementation notions, especially thoserelated to behaviour isomorphisms.

The choice of the design concepts has been based on architectural requirements thatemerged from abstraction levels. No assumptions were made with respect to a (formal)semantics to support these concepts. Our notation is still rather ad-hoc and cannot besupported by any form of automated tool. However since we did not use any specific designlanguage, we have been able to focus on the concepts to be manipulated in design, withoutconsidering the possible limitations design languages may bring. We admit, however, thatlanguage support is necessary in order to effectively apply the concepts in the design of prac-tical systems. A fully developed design language to support the concepts presented in thispaper constitutes therefore another important area in which further work is needed.

Although we have intentionally avoided to mention object-orientation in the paper, webelieve that entities can be considered as objects, and the object-oriented paradigm applies totheir behaviours. In this way encapsulation, re-usability, etc. would be incorporated in ourdesign model. Behaviour definitions using causality relations would not oppose the object-oriented paradigm but rather serve as a technical filling.

Acknowledgements

Thanks are due to Harro Kremer for intensive discussion on the subjects covered in thispaper. Dick Quartel is kindly acknowledged for his careful remarks and comments on a draftpaper. The material in Section 8 is based on a specification of the service provider (and asimilar protocol) in a timed variant of LOTOS ([2]) by Robert Huis in ’t Veld. This will bereported by him in a forthcoming paper. Kazi Farooqui is acknowledged for his detailedcomments on the relationship between abstraction levels and ODP viewpoints.

References

[1][2]

L.J. Bannon and K.Schmidt. CSCW: Four characters in search of a context. InJ.Bowers and S.Benford, editors,Studies in computer supported cooperative work:theory, practice and design, pages 3–16. North-Holland, 1991.

T.Bolognesi, F.Lucidi, and S.Trigila. From timed Petri nets to timed LOTOS. InL.Logrippo, R.Probert, and H.Ural, editors,Protocol Specification, Testing andVerification X, pages 377–406. Elsevier Science Publishers B.V. (North-Holland),1990.

D.Bowen. Open distributed processing.Computer Networks and ISDN Systems,23:195–201, 1991.

[3]

29

[4][5][6][7][8][9][10][11][12][13][14][15][16][17][18]

[19][20]

[21][22]

C.Chabernaud and B.Vilain. Telecommunication services and distributedapplications.IEEE Network Magazine, pages 10–13, 1990.

R.Gotzhein.Open Distributed Systems. On concepts, methods, and design from alogical point of view. Vieweg Advanced Studies in Computer Science. Vieweg,Wiesbaden, Germany, 1993.

J.Gunawardena. Causal automata.Theoretical Computer Science, 101:265–288, 1992.ISO/IEC JTC1/SC21/WG7. Basic Reference Model of Open Distributed Processing.ISO 10746, 1993. Part 1 to 4.

P.Linington. Introduction to the Open Distributed Processing Basic Reference Model.In J.deMeer, V.Heymer, and R.Roth, editors,Open Distributed Processing, pages 3–14. Elsevier Science Publishers B.V. (North-Holland), 1992.

T.D. Little and E.Ghafoor. Multimedia synchronization protocols for broadbandintegrated services.IEEE Journal on Selected Areas in Communications, 9(9):1368–1381, 1991.

Z.Manna and A.Pnueli.The Temporal Logic of Reactive and Concurrent SystemsSpecification. Springer-Verlag, 1992.

C.Nicolaou. An architecture for real-time multimedia communication systems.IEEEJournal on Selected Areas in Communications, 8(3):391–400, 1990.

G.Pinna and A.Poigné. On the nature of events. In I.Havel and V.Koubek, editors,Mathematical Foundations of Computer Science 1992, LNCS 629, pages 430–441.Springer-Verlag, 1992.

E.Rechtin. The art of systems architecting.IEEE Spectrum, pages 66–69, October1992.

W.Reisig.Petri Nets – An Introduction, volume4 ofEATCS Monographs onTheoretical Computer Science. Springer-Verlag, 1985.

A.Rensink.Models and Methods for Action Refinement. PhD thesis, University ofTwente, Enschede, The Netherlands, 1993.

J.Schot.The role of Architectural Semantics in the formal approach towardsDistributed Systems Design. PhD thesis, University of Twente, Enschede, TheNetherlands, 1992.

R.Steinmetz. Synchronization properties in multimedia systems.IEEE Journal onSelected Areas in Communications, 8(3):401–412, 1990.

R.van Glabbeek. The linear time - branching time spectrum. In J.Baeten and J.Klop,editors,CONCUR’90. Theories of concurrency: unification and extension, volume 458ofLecture Notes in Computer Science, pages 278–297, Germany, 1990. Springer-Verlag.

J.J. van Griethuysen. Open distributed processing (ODP). In E.Brinksma, G.Scollo,and C.A. Vissers, editors,Protocol Specification, Testing, and Verification, IX, TheNetherlands, 19. Elsevier Science Publishers B.V. (North-Holland).

C.A. Vissers, L.Ferreira Pires, and J.van de Lagemaat. Lotosphere, an attempttowards a design culture. In T.Bolognesi, E.Brinksma, and C.A. Vissers, editors,Third Lotosphere Workshop and Seminar, Workshop Proceedings, volume1, pages 1–30, 1992.

C.A. Vissers, G.Scollo, M.van Sinderen, and E.Brinksma. Specification styles indistributed systems design and verification.Theoretical Computer Science, :179–206, 1991.

C.A. Vissers, M.van Sinderen, and L.Ferreira Pires. What makes industries believe informal methods. In A.Danthine, G.Leduc, and P.Wolper, editors,ProtocolSpecification, Testing, and Verification, XIII, pages 3–26, The Netherlands, 1993.Elsevier Science Publishers B.V. (North-Holland).