We describe an approach to modeling the dynamics of distributed systems. By distributed systems we mean systems consisting of concurrent processes communicating via shared ports and posing certain synchronization requirements, via the ports, to the adjacent processes. The basic idea is to use graphs to represent states of such systems, and graph rewriting to represent their evolution. The kind of graph rewriting we use is based on simple context-free productions which are, however, combined by means of a synchronization mechanism. This allows for a good level of expressivity in the system without sacrifying full distribution. To formally model this kind of graph rewriting, however, we do not adopt the classical graph rewriting style but a more general framework, called the tile model, which allows for a clear separation between sequential rewriting and synchronization. Then, since the problem of satisfying the synchronization requirements may be a complex combinatorial problem, we suggest exploiting existing techniques for constraint solving. This is based on the observation that the synchronization problem can be modeled as a (finite domain) constraint problem. In this respect, we propose to use both local consistency techniques, to remove the possible redundancies in a system state, and a distributed backtracking search algorithm, as used in distributed constraint solving. Our method has the following advantages: first, it provides a formal description of the way a distributed system evolves; second, it seems promising from the performance point of view, since the techniques we propose for combining productions have been proved to be very convenient in several cases; finally, the kind of system evolution we describe here is just a particular instance of what can be described by using the tile model in its most general form, thus suggesting the possibility of extending our approach to modeling more complex distributed systems.
Graph rewriting, constraint solving and tiles for coordinating distributed systems
MONTANARI, UGO GIOVANNI ERASMO;
1999-01-01
Abstract
We describe an approach to modeling the dynamics of distributed systems. By distributed systems we mean systems consisting of concurrent processes communicating via shared ports and posing certain synchronization requirements, via the ports, to the adjacent processes. The basic idea is to use graphs to represent states of such systems, and graph rewriting to represent their evolution. The kind of graph rewriting we use is based on simple context-free productions which are, however, combined by means of a synchronization mechanism. This allows for a good level of expressivity in the system without sacrifying full distribution. To formally model this kind of graph rewriting, however, we do not adopt the classical graph rewriting style but a more general framework, called the tile model, which allows for a clear separation between sequential rewriting and synchronization. Then, since the problem of satisfying the synchronization requirements may be a complex combinatorial problem, we suggest exploiting existing techniques for constraint solving. This is based on the observation that the synchronization problem can be modeled as a (finite domain) constraint problem. In this respect, we propose to use both local consistency techniques, to remove the possible redundancies in a system state, and a distributed backtracking search algorithm, as used in distributed constraint solving. Our method has the following advantages: first, it provides a formal description of the way a distributed system evolves; second, it seems promising from the performance point of view, since the techniques we propose for combining productions have been proved to be very convenient in several cases; finally, the kind of system evolution we describe here is just a particular instance of what can be described by using the tile model in its most general form, thus suggesting the possibility of extending our approach to modeling more complex distributed systems.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
