Symmetric and Asymmetric Asynchronous Interaction - Computer Science > Logic in Computer ScienceReport as inadecuate

Symmetric and Asymmetric Asynchronous Interaction - Computer Science > Logic in Computer Science - Download this document for free, or read online. Document in PDF available to download.

Abstract: We investigate classes of systems based on different interaction patternswith the aim of achieving distributability. As our system model we use Petrinets. In Petri nets, an inherent concept of simultaneity is built in, sincewhen a transition has more than one preplace, it can be crucial that tokens areremoved instantaneously. When modelling a system which is intended to beimplemented in a distributed way by a Petri net, this built-in concept ofsynchronous interaction may be problematic. To investigate this we considerasynchronous implementations of nets, in which removing tokens from places canno longer be considered as instantaneous. We model this by inserting silentunobservable transitions between transitions and some of their preplaces. Weinvestigate three such implementations, differing in the selection of preplacesof a transition from which the removal of a token is considered time consuming,and the possibility of collecting the tokens in a given order.We investigate the effect of these different transformations of instantaneousinteraction into asynchronous interaction patterns by comparing the behavioursof nets before and after insertion of the silent transitions. We exhibit forwhich classes of Petri nets we obtain equivalent behaviour with respect tofailures equivalence.It turns out that the resulting hierarchy of Petri net classes can bedescribed by semi-structural properties. For two of the classes we obtainprecise characterisations; for the remaining class we obtain lower and upperbounds.We briefly comment on possible applications of our results to MessageSequence Charts.

Author: Rob van Glabbeek, Ursula Goltz, Jens-Wolfhard Schicke


Related documents