Modeling Dynamic Distributed Object Structures by Graph Transformation

Gabriele Taentzer
Technical University of Berlin
Berlin, Germany
gabi@cs.tu-berlin.de
http://www.cs.tu-berlin.de/~gabi


Abstract

Object-oriented software development methodologies are based on a number of graphical notations describing the key aspects of a system. There is an increasing research interest to incorporate distribution issues into development methods. Allocation of objects and tasks, object replication and migration, remote interactions, multiple threads of control as well as dynamic network topologies are important issues in distributed object systems. In this article, a graphical notation for dynamic distributed object structures is presented which uses graph transformation as underlying formal framework.

This new approach integrates networking aspects with object structures and object interaction concerns. The description is performed on two abstraction levels: the network and the local level. The network level focuses on the topological structure of a system. The local level contains snapshots showing local object structures which may evolve independently or dependently of others using suitable interaction mechanisms. Distributed operations for the description of dynamic networks, communication and synchronization are modeled in a rule-based manner by showing object structure parts before and after. Applying several rules, i.e. performing distributed graph transformation, results in a distributed scenario. The advantage of using rules is the modeling of multiple threads of control on the level of events.

Using graph transformation as underlying formal framework, distributed object structures may be modified on the network and on the local level concurrently in such a way that consistency of the resulting distributed object structure is ensured.


Introduction

Graphical notations have been employed for a long time in specification and design of software systems. Prominent representatives are automata, data flows, control flows, Petri nets and entity-relationship diagrams. Recently a number of object-oriented methods have been introduced (e.g. OMT [1], OOD [2] ) which highly rely on diagrammatic notations. These methods nicely support the design of object class structures, the main static part of an object-oriented system.

Traditional object-oriented methods offer little help in understanding the interaction processes between objects. Methods which mainly support the modeling of operations and processes are based on classical control models such as those based on finite state-automata, state charts and Petri nets. They are operational models which do not support an easy to understand visual description of dynamic object structures.

There are modeling languages which combine operational process descriptions with object concepts mostly based on actor systems (e.g. O3ML [3]). But they do not address distribution issues. There already exist extensions of the object-oriented analysis and design methodologies for distributed systems (like MOSES [4] and PARSE [5]) which concentrate on allocation and partitioning, active and passive objects, object replication and migration and remote service invocations. The notation of more complex remote object interactions, concurrency dependent of dynamically changing object structures and dynamic network structures are nearly not considered.

In the following, a graphical model is introduced which integrates operational, object-oriented and distribution issues. This model does not deal with the internal states of objects and their transitions by executing methods, but concentrates on object allocation, a flexible description technique for object replication and remote object interactions and concurrency of events dependent of dynamically changing object and network structures.

The notation presented distinguishes two abstraction levels. The more abstract network level focuses on the distribution structure of the system. The local level contains snapshots of local object structures where objects are allowed to be used also remotely. The levels are related to each other describing the allocation of objects. Altogether this notation yields a structured graph with two abstraction levels and describes a snapshot of a distributed object structure.

On both levels, the structures may be of a dynamic nature which is described by graph transformation. Graph transformation means the rule-based manipulation of graphs. The application of rules defines a relation on graphs which may be iterated arbitrarily often yielding the transformation process. In this way, a set of graph transformation rules gets an operational semantics. Graph transformation has been studied in a variety of approaches motiviated by application domains as pattern generation and recognition, implementation of functional programming languages, specification of database systems and distributed systems, etc. This development is mainly documented by proceedings and other collections of selected papers [6, 7, 8, 9].

On the network level graph transformation is used to describe dynamic networks. The usage of graph transformation on the local level includes the description of local as well as remote object interaction, object migration, replication, communication and synchronization. All these activities are described in a rule-based manner by showing parts of the object structure before and after. Applying one or more rules, i.e. performing distributed graph transformation [10, 11], results in a distributed scenario. The advantage of using rules is the modeling of multiple threads of control on the level of events.

Using graph transformation as underlying formal framework, consistency of the resulting distributed object structure is ensured. Objects which are used (remotely) by other objects cannot be destroyed and components with channels from or to other components cannot be deleted.


Distributed state graphs

An object diagram consists of a set of objects where each of them has its own unique identity. Objects may use each others by communicating via orders for method execution. Such a use structure can clearly be modeled by a graph where the nodes represent the objects and the edges the use relations between them. Such a graph shows a certain state of an object system, i.e. a snapshot, and is therefore called state graph. If the state is a distributed one it is reflected by several graphs where each of them shows a local state.

Distributed object systems have an underlying network structure. Although this might be transparent to the users, each object belongs to a certain component in the network. For interaction, the object also has to be known in other components. Objects which are used by remote components, have to be exported and replicated in that remote component. Such a replicated object is modeled by a local node with a connection to its origin. Thus, remote objects as well as their use relations can occur again in the local component. This enables the user of the local component to abstract from distribution. If two components have a connection, exported objects can occur as replications in the remote component.

The local systems are allowed to change their states. Moreover, the network structure may change. It changes if, for example, new local components are added or connections are changed. In a distributed state, the current network structure of the whole distributed system as well as all local states and their connections are stored.

The network structure of a distributed system is modeled by a graph. Its nodes represent the components. The edges of the network graph describe connections which allow remote use relations between remote objects. Components as well as connections may be typed to group those of similar structure and behavior together, i.e. components are modeled analogously to objects.

In the following, components are depicted by rectangles with their type shown in the title bar. Thick arrows between them depict connections. Local states are shown inside the rectangles. Objects are depicted by small rectangles with their types written inside. Arrows between these rectangles represent use relations. A rectangle with a shadow depicts an object which is exported. Replications of objects are represented by shadows only. Their position in the component and their color are like those of their originals.

Example

Let us consider a very small example of a distributed shipping system where we concentrate on the administration of orders and clients. In figure 1 a snapshot is depicted where the system consists of two components: Orders and Clients.

To model object relations in distributed environments we simply place all objects which may be used remotely into the export interface of Clients. Component Orders can contain these objects as replications. Figure 1 shows a situation where two ``client''-objects are replicated in Orders. A third ``client''-object ist not exported, i.e. not drawn with a shadow.


Figure 1:  A distributed state graph: Object replication

The interaction medium between components may be active or passive. In contrast to the connection in figure 1, an active medium, like a channel, allows to transfer an object parallel to its processing on the server component, i.e. asynchronously. Figure 2 shows components Orders and Clients again connected by a channel which runs from Clients to Orders.


Figure 2:  A distributed state graph: Modeling a channel

In this snapshot one object of class ``client'' is hold within the channel. This is the upper (red) one which has still a connection to its original, i.e. it is replicated. Since this object is used by Orders it is in the export interface of Clients. If such an object should be deleted in Clients it has to be deleted in Orders, too. The lower (blue) one is no more in the channel and the corresponding lower ``client''-object in Orders is no more connected with its origin, but the original remains in the export interface of Clients. The ``client''-object in Orders became a real copy of the original object. It is depicted as normal object. Thus, it may be changed in the Clients and in the Orders components independently.

Moreover, it is possible to model objects which have been sent but are not yet arrived. Such an object would be in Clients (within the interface part) and in the channel but not in Orders.


Graph Transformation

Graph transformation means the rule-based manipulation of graphs. In this context graphs are always used to describe the static part of a system. The dynamic part is formulated within graph rules using the if-then style. If a certain structure, i.e. the left-hand side of the rule, is existing then it may be transformed into a new one, the right-hand side of the rule, where some items may be the same. These items function as central points in the structure where the operations take place. Graph transformation, i.e. the application of rules, defines a relation on graphs which may be iterated arbitrarily often yielding the transformation process. In this way, a set of graph transformation rules gets an operational semantics.

There are several graph transformation approaches [12, 13, 15, 16] which differ in the underlying graph structure as well as in the way rules are written and applied. For the precise definition of graph transformation different calculi are used, e.g. set theory, logic, or category theory. The underlying approach for distributed graph transformation as presented in this article is the double-pushout approach [12, 17] where the main parts of a graph transformation step are characterized by pushouts, one of the basic features in category theory.

Based on directed node- and edge-labeled graphs we write graph rules which consist of a left- and a right-hand side which both contain a common graph that is preserved. A graph rule can describe deletion and insertion of structure parts. Actions which belong together semantically should be encapsulated in one rule, since rule application is atomic. A node cannot be deleted if there is a context edge adjacent to that node. If this application condition is satisfied, graph transformation ensures that the result of a rule application is again a graph. A rule application consists of the following steps: choose an occurrence of the left-hand side of the rule, check the application condition, remove this occurrence except of the preserved part and glue the right-hand side at the preserved part.

Example

In figure 3 a sample graph transformation is given where the different parts of a graph rule application are distinguished by (colored) frames. The vertical arrows between graphs represent graph occurrences and the horizontal arrows reflect the temporal order in a graph transformation.


Figure 3:  A sample graph transformation

Distributed Graph Transformation

Distributed graph transformation as presented below has been formally introduced in [10, 11]. It can be regarded as structured graph transformation on two abstraction levels.

A distributed graph consists of a network graph where each network node is equipped with a local graph and each network edge is equipped with a local occurrence of the source graph in the target graph.

A distributed graph describes a distributed state of a system. The network graph represents the current network structure of the system. It may evolve over the time. A network node models a component or an interface and a network edge a connection between components and interfaces. However, connections like a channel may be modeled by a separat component with connections to those it should connect. Local graphs are used to describe local states of components and interfaces.

A distributed graph rule consists of a network rule and local rules for all network nodes which are preserved by the network rule. Each newly created network node is equipped with a local graph. If a network node is deleted its local graph is deleted, too. Distributed graph transformation is performed by a number of simple graph transformations on both abstraction levels of a distributed graph. Besides the network transformation a number of local graph transformation may be executed. Relations between transformed local graphs are induced by the transformation steps.

Distributed graph rules are useful to describe dynamic network structures by the network rule as well as dynamic local object structures in each component by a set of local rules.

If the application of a distributed graph rule satisfies certain conditions, mainly the context and the network conditions which are explained below, this yields a valid distributed state graph as result. This coherence is extremely useful to design consistent object structure transformations in a distributed environment.


Local object interaction

Local object interaction can be regarded as a simple transaction on an object structure allowing an encapsulated set of atomic events. Atomic events are the creation and deletion of objects and their relations. Since the internal states of objects are not modeled within object structures, events like state modifications of objects are described by identical replacements of object nodes. To ensure consistency on the local object structures, objects are not allowed to be deleted if they are still related to others.

Local object interaction can be modeled by a distributed rule consisting of a local rule which describes the local interaction and a network rule which just describes the preservation of the component where the local action takes place. Such a distributed graph rule can be applied to a distributed state graph if the local interaction is compatible with the context where it takes place. The rule application is prohibited if the following condition, called context condition, is not satisfied: Exported objects cannot be deleted if they have replications. Obeying this condition, local interactions in different components can be executed simultaneously or in either order, i.e. in a true concurrent way, since they do not affect other components.

Example

An example for a local object interaction is the creation of a new ``client''-object and its relation to an existing ``place''-object. The interaction is modeled by the graph rule in figure 4. This graph rule can always be applied to a distributed state graph if a Clients component with a suitable ``place''-object is available.


Figure 4:  A local object interaction: Creation of a new ``client'' object

A graph rule as in figure 5 which deletes an exported ``client''-object is applicable, if this object is not replicated in some connected component.


Figure 5:  Deletion of an exported ``client''-object


Dynamic networks

Modeling distributed systems, the description of networks is usually static. With graph transformation we get the possibility to model dynamic networks, i.e. changes in networks are described by graph rules. To avoid inconsistencies, the deletion and creation of components has to be done very cautious. This means that deletions must not destroy the remote use relations, i.e. a component may only be deleted if all its objects are not used remotely. Additionally, deletion of components must not destroy the network structure, i.e. connections or channels run always between components. If components shall be deleted their final states have to be modeled to specifiy that moment when the deletion is permitted. Moreover, creating e.g. a new channel its initial state has to be consistent with the components it connects. In the easiest case a channel's initial state is empty. If these conditions, called network conditions, are satisfied the network actions can be performed concurrently, i.e. new components may be inserted and other components (possibly with adjacant connections) may be deleted. Moreover, connections between components may be deleted and created, too.

Altogether a network administrating activity is also described by a distributed graph rule where its network rule describes the changes of the network topology. Moreover, the inital (final) state of the newly created (deleted) components or channels are described. For preserved components and channels those states are specified where a network modification may take place.

Example

The graph rule in figure 6 describes the creation of a Clients component without any connection. The component does not contain any object in the beginning.


Figure 6:  Dynamic networks: Creation of a component

The inverse of the rule in figure 6 models the deletion of a component Clients where the final state is the empty one. For example, such a deleting rule is not applicable to the distributed state graphs in figures 1 and 2.

The creation of a channel from a Clients component to an Orders component is modeled by the rule in figure 7. This rule is always applicable when such two components are available.


Figure 7:  Dynamic networks: Creation of a channel


Distributed object interaction

Distributed object interaction like object migration meaning the movement of an object from one component to another, or object replication is modeled by several actions in components connected with each other. The network graph rule just mention those components which take part in the interaction. All connections which are used for communication have to be represented in the distributed graph rule. For each component, a local rule is applied which models the corresponding communication part of the object interaction to be performed there.

Example

Changes on objects in export interfaces can cause changes on their replications in connected components. If a replication has to be hold consistent at all time, object and replication updates have to be done in a synchronous way. Figure 8 shows a distributed graph rule containing two local rules modeling the updates. In these rules the ``client''-object is related to that ``place''-object where the client lives, this ``place''-object is put into the export interface of Clients and this new relation is propagated to the Orders component.


Figure 8:  Synchronized object update

Asynchronous communication between two local parts can be expressed by synchronization with their common communication medium. Considering a network as in figure 2, both components have to synchronize themselves with the channel, Clients for sending and Orders for receiving an object. Figures 9 and 10 show the corresponding distributed graph rules modeling these interactions. Rule ``send'' can be applied independently of rule ``receive'', but not vice versa, since a replication of the ``client''-object is first put into the channel and then further propagated to the Orders component. Thus, there is the natural dependency of ``receive'' from ``send'' modeled.


Figure 9:  Distributed object interaction: Sending an object


Figure 10:  Distributed object interaction: Receiving an object


Distributed scenarios

Starting with some network topology and local initializations, the initial state of a distributed scenario can be described by a distributed state graph. Local as well as distributed object interactions, network activities and, moreover, also combinations of these actions are allowed as state transitions. A distributed scenario is described by a distributed graph transformation sequence.

Distributed graph transformation supports a model where components specify their own process. Insertion of a new component models the start of a new process and deleting a component means termination of a process. Each local rule modeling an object interaction defines its own thread of control. Thus, threads of control are modeled here independently of objects and allow concurrency on the level of events.

Distributed scenarios specified by distributed graph transformation support the understanding of the concurrent behavior which may cause situations like state-dependent deadlocks or starvation. If distributed rule applications are independent of each others they may happen simultaneously or in either order, i.e. true concurrently.

Example


Figure 11:  A sample distributed scenario

In figure 11 a short scenario is depicted where two state transitions are shown. In the first state transition, two different events take place. Component Clients sends a ``client''-object (compare the rule in figure 9) and, imagine the work in distributed shipping companies, a new Clients component is created to administrate the clients at another site (compare the rule in figure 6). In a second step, component Orders receives a replication of another ``client'' object (compare the rule in figure 10) and, since the new component has to have also a connection to the order administration, a channel between this new component and the Orders component is established (compare the rule in figure 7). Moreover, in the Clients component, a new ``client''-object is created (compare the rule in figure 4).


Conclusion

This article suggests graph transformation for the graphical notation of dynamic distributed object structures. This notation integrates operational, object-oriented and distributed issues. It focuses on dynamic networks, flexible object allocation, remote object relations, complex (remote) object interactions and concurrency dependent on dynamically changing object structures by multiple threads of control.

Structure consistency is ensured by the connection and the network conditions for distributed graph transformation. For more advanced reasoning about the system design user-defined consistency conditions have to be supported. Using such conditions, certain aspects of dynamic distributed object structures may be modeled in a declarative way. There is the possibility to automatically checking consistency constraints for graph transformation before run time [18]. This procedure has to be extended to the distributed case.

Since graph transformation has a very operational and constructive character coupled with an easy to understand graphical notation that would provide tool support. There are some tools available which are based on graph transformation like PAGG [19], PROGRES [15] and AGG [20]. They contain at least a graphical editor for drawing graphs, and an interpreter for graph transformation. Moreover, the PROGRES environment offers a nice support for graphical prototyping of software systems. Until now, none of these tools supports distributed graph transformation. Our current work is the development of a tool based on a distributed graph transformation machine as a run time system for distributed object systems.


References

1
J. Rumbaugh, M. Blaha, W. Premerlani, E. Eddy, and W. Lorenson. Object-Oriented Modeling and Design. Prentice Hall International, 1991.

2
G. Booch. Object-Oriented Analysis and Design with Applications. Benjamin Cummings, 1994.

3
R. Agarwal, M. Torchiano, and G. Bruno. Operational Object Oriented CASE. Object Currents, 1(7), July 1996. full paper

4
G. Rasmussen, B. Henderson-Sellers and G.C. Low. An object-oriented analysis and design notation for distributed systems. Object Currents, Vol. 1, Issue 10, 1996. full paper

5
A. Liu and I. Gorton. Modelling Dynamic Distributed System Structures in PARSE. In Proc. 4th European Workshop on Parallel and Distributed Processing, Braga, Portugal, IEEE Computer Society Press, 1996.

6
H. Ehrig, H.-J. Kreowski, and G. Rozenberg (eds.). 4th International Workshop on Graph Grammars and Their Application to Computer Science. Springer, LNCS 532, 1991.

7
H.-J. Schneider and H. Ehrig. Graph Transformations in Computer Science. LNCS 776. Springer, 1994.

8
J. Cuny, H. Ehrig, G. Engels, and G. Rozenberg. Graph Grammars and Their Application to Computer Science. Springer, LNCS 1073, 1996.

9
H. Ehrig, G. Engels, and G. Rozenberg (eds.). Special issue: graph transformation. Fundamenta Informaticae, vol. 26, no. 3,4, June 1996.

10
G. Taentzer. Parallel and Distributed Graph Transformation: Formal Description and Application to Communication-Based Systems. PhD thesis, TU Berlin, Shaker, 1996.

11
G. Taentzer. Hierarchically Distributed Graph Transformation. In [8], pages 304 - 320.

12
H. Ehrig. Introduction to the Algebraic Theory of Graph Grammars. In V. Claus, H. Ehrig, and G. Rozenberg (eds.), 1st Graph Grammar Workshop, LNCS 73, pages 1-69, Springer, 1979.

13
G. Rozenberg. An introduction to the NLC way of rewriting graphs. In 3rd Int. Workshop on Graph Grammars and their Application to Computer Science, LNCS 291, pages 55-66. Springer, 1987.

15
A. Schürr. PROGRESS: A VHL-Language Based on Graph Grammars. In [6], pages 641 - 659.

16
M. Löwe. Algebraic approach to single-pushout graph transformation. Theoretical Computer Science, 109:181-224, 1993.

17
H. Ehrig, M. Korff, and M. Löwe. Tutorial introduction to the algebraic approach of graph grammars based on double and single pushouts, in [6], pages 24-37.

18
R. Heckel and A. Wagner, Ensuring Consistency of Conditional Graph Grammars - A constructive Approach. Proc. of SEGRAGRA'95 "Graph Rewriting and Computation", Electronic Notes of Theoretical Computer Science, 2, 1995. full paper.

19
H. Göttler. Graphgrammatiken in der Softwaretechnik, volume 178 of Informatik Fachberichte. Springer, 1988.

20
M. Löwe and M. Beyer. AGG - An Implementation of Algebraic Graph Rewriting. In Proc. Fifth Int. Conf. Rewriting Techniques and Applications, '93, LNCS 690, pages 451-456. Springer, 1993.


©1996 SIGS Publications, Inc., New York, NY, USA. All Rights Reserved.