Distributed Graph Transformation with Application to Visual Design of Distributed Systems

Distributed systems demand a number of requirements on specification techniques which do not have to be taken into account for the development of non-distributed software. 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 systems. Some of these distribution issues are already handled by common modeling techniques mostly based on graphical notations, but altogether distributed systems cannot be designed sufficiently with these techniques satisfying all the requirements. In this chapter, new concepts for visual design of distributed systems are presented which are based on distributed graph transformation as underlying formal specification technique. The kernel of this technique focuses on a structured graph with two abstraction levels, the network and the local level, and its transformation. On the network level, the (possibly) dynamic topological structure of a distributed system is specified. The local level contains the graphical description of local object and data structures where parts of them may be replicated in remote network nodes. Those structures may evolve independently or synchronized with remote structures using a interaction mechanism based on subactions. Network activities as well as local actions are described rule-based. The advantage of using rules in this context is to avoid purely sequential or serie-parallel control flow, since rules naturally support the design of multiple threads of control on the level of events without prescribing the order of execution. Distributed graph transformation is based on the double-pushout approach to graph transformation. Local graph transformations may be attributed and may use application conditions for rules. Using graph transformation as underlying formal framework, distributed behaviour is designed in a way that consistency of the network as well as of all object and data structures involved is ensured in a way that the result is again a distributed graph. This result is obtained from the formalization of distributed graph transformation as double-pushout in the category of distributed graphs and graph morphisms. For the illustration of the concepts presented we use a reference application modeling distributed version management for any kind of document. This subject becomes the more important the more remote software development becomes popular. In contrast to server-client solutions where all documents are held centrally, the documents are really distributed over the involved sites in our case.