Symmetric and Asymmetric Asynchronous Interaction

Select |




Print


van Glabbeek, Robert; Goltz, Ursula; Schicke, Jens-Wolfhard

van Glabbeek, Robert; Goltz, Ursula; Schicke, Jens-Wolfhard


2008-07-06


Conference Material


First Interaction and Concurrency Experience (ICE'08): Synchronous and Asynchronous Interactions in Concurrent Distributed Systems


Reykjavik, Iceland


5-22


We investigate classes of systems based on different interaction patterns with the aim of achieving distributability. As our system model we use Petri nets. In Petri nets, an inherent concept of simultaneity is built in, since when a transition has more than one preplace, it can be crucial that tokens are removed instantaneously. When modelling a system which is intended to be implemented in a distributed way by a Petri net, this built-in concept of synchronous interaction may be problematic. To investigate the problem we assume that removing tokens from places can no longer be considered as instantaneous. We model this by inserting silent (unobservable) transitions between transitions and their preplaces. We investigate three different patterns for modelling this type of asynchronous interaction. Fully symmetric asynchrony assumes that every removal of a token from a place is time consuming. For symmetric asynchrony, tokens are only removed slowly in case of backward branched transitions, hence where the concept of simultaneous removal actually occurs. Finally we consider a more intricate pattern by allowing to remove tokens from preplaces of backward branched transitions asynchronously in sequence (asymmetric asynchrony). We investigate the effect of these different transformations of instantaneous interaction into asynchronous interaction patterns by comparing the behaviours of nets before and after insertion of the silent transitions. We exhibit for which classes of Petri nets we obtain equivalent behaviour with respect to failures equivalence. It turns out that the resulting hierarchy of Petri net classes can be described by semi-structural properties. In case of fully symmetric asynchrony and symmetric asynchrony, we obtain precise characterisations; for asymmetric asynchrony we obtain lower and upper bounds. We briefly comment on possible applications of our results to Message Sequence Charts.


reactive systems, Petri nets, distributed systems, asynchronous interaction, equivalence notions


http://www.cse.unsw.edu.au/~rvg/pub/ice2008.pdf


nicta:843


van Glabbeek, Robert; Goltz, Ursula; Schicke, Jens-Wolfhard. Symmetric and Asymmetric Asynchronous Interaction. In: F. Bonchi, D. Grohmann, P. Spoletini, A. Troina & E. Tuosto Editor, editor/s. First Interaction and Concurrency Experience (ICE'08): Synchronous and Asynchronous Interactions in Concurrent Distributed Systems; Reykjavik, Iceland. 2008-07-06. 5-22.



Loading citation data...

Citation counts
(Requires subscription to view)