SASlogo

SAS (Synchronous and Asynchronous Interaction in Distributed Systems) is a joint research project of the TU Braunschweig and the TU Berlin. The project is funded by the DFG (German Research Foundation).

 

Scope

The goal of this project is to investigate the paradigms of synchronous and asynchronous interaction in distributed systems.  In many formalisms for systems specification or design, synchronous communication is provided as a basic notion. However, it is often hard to implement efficiently.  In contrast, the realisation of asynchronous interaction in distributed systems is uncritical, but a restriction to asynchronous concepts constrains the class of implementable system specifications.  A simulation of synchronous interaction by means of asynchronous interaction is not always possible in distributed systems.

The project analyses under which conditions synchronous interaction can be implemented in distributed systems.  The research is based on an abstract model of distributed systems, which is captured both semantically (in terms of Petri nets) and syntactically (by means of process calculi). As a result, the project aims to clearly identify the limits of the implementability of synchronous interaction patterns; within these limits, the project is to provide concrete implementation concepts based on synchronous and asynchronous interaction patterns.

Participants

The following people are currently working on the project.

  • @ IPS, TU Braunschweig: Prof. Dr. Ursula Goltz, Jens-Wolfhard Schicke and Malte Lochau.
    Ursula Goltz has been studying the foundations and semantic subtleties of Petri nets since the 1980s. She contributed important results on causal semantics and notions of equivalence.
  • @ MTV, TU Berlin: Prof. Dr. Uwe Nestmann, Dr. Kirstin Peters, and Christian Hammerschmidt.
    Within the field of process calculi (in particular the pi-calculus), Uwe Nestmann has contributed important results to the conceptual and formal understanding of asynchronous communication and the correctness of distributed implementations.

Two internationally renowned researchers are associated with this project:

Publications

@article{glabbeek11abstract, title = "Abstract Processes of Place/Transition Systems", journal = "Information Processing Letters", volume = "111", number = "13", pages = "626 - 633", year = "2011", issn = "0020-0190", doi = "DOI: 10.1016/j.ipl.2011.03.013", url = "http://www.sciencedirect.com/science/article/B6V0F-52F85VS-2/2/fa0abf8ebd29282dcb574c3c1b4de924", author = "Rob J. van Glabbeek and Ursula Goltz and Jens-Wolfhard Schicke", }

[GGS11] R. Glabbeek, U. Goltz & J.-W. Schicke
Abstract Processes of Place/Transition Systems
Information Processing Letters, 111, 13, 2011, 626 - 633
Download

A well-known problem in Petri net theory is to formalise an appropriate causality-based concept of process or run for place/transition systems. The so-called individual token interpretation, where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig, is often considered too detailed. The problem of defining a fully satisfying more abstract concept of process for general place/transition systems has so-far not been solved. In this paper, we recall the proposal of defining an abstract notion of process, here called BD-process, in terms of equivalence classes of Goltz-Reisig processes, using an equivalence proposed by Best and Devillers. It yields a fully satisfying solution for at least all one-safe nets. However, for certain nets which intuitively have different conflicting behaviours, it yields only one maximal abstract process. Here we identify a class of place/transition systems, called structural conflict nets, where conflict and concurrency due to token multiplicity are clearly separated. We show that, in the case of structural conflict nets, the equivalence proposed by Best and Devillers yields a unique maximal abstract process only for conflict-free nets. Thereby BD-processes constitute a simple and fully satisfying solution in the class of structural conflict nets.

@inproceedings{GGS11a, author = "Glabbeek, Rob van and Goltz, Ursula and Schicke, Jens-Wolfhard", title = "On Causal Semantics of Petri Nets (extended abstract)", booktitle = {International Conference on Concurrency Theory (CONCUR 2011)}, year = "2011", month = "September", eprint = "http://www.ips.tu-braunschweig.de/docs/research/goltz/CONCUR2011.pdf", editor = "Joost-Pieter Katoen and Barbara K├Ânig" }

[GGS11a] Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
On Causal Semantics of Petri Nets (extended abstract)
International Conference on Concurrency Theory (CONCUR 2011), 2011
Download

We consider approaches for causal semantics of Petri nets, explicitly representing dependencies between transition occurrences. For one-safe nets or condition/event-systems, the notion of process as defined by Carl Adam Petri provides a notion of a run of a system where causal dependencies are reflected in terms of a partial order. A wellknown problem is how to generalise this notion for nets where places may carry several tokens. Goltz and Reisig have defined such a generalisation by distinguishing tokens according to their causal history. How- ever, this so-called individual token interpretation is often considered too detailed. A number of approaches have tackled the problem of defining a more abstract notion of process, thereby obtaining a so-called collective token interpretation. Here we give a short overview on these attempts and then identify a subclass of Petri nets, called structural conflict nets, where the interplay between conflict and concurrency due to token multiplicity does not occur. For this subclass, we define abstract processes as equivalence classes of Goltz-Reisig processes. We justify this approach by showing that we obtain exactly one maximal abstract process if and only if the underlying net is conflict-free with respect to a canonical notion of conflict.

@inproceedings{PSN11, author = "Peters, Kirstin and Schicke, Jens-Wolfhard and Nestmann, Uwe", title = "Synchrony vs Causality in the Asynchronous Pi-Calculus", booktitle = {Proceedings 18th International Workshop on Expressiveness in Concurrency}, year = "2011", month = "September", eprint = "http://www.ips.tu-braunschweig.de/docs/research/schicke/1108.4469v1.pdf", doi = {10.4204/EPTCS.64.7}, editor = "Bas Luttik and Frank Valencia" }

[PSN11] Kirstin Peters, Jens-Wolfhard Schicke and Uwe Nestmann
Synchrony vs Causality in the Asynchronous Pi-Calculus
Proceedings 18th International Workshop on Expressiveness in Concurrency, 2011
DOI 10.4204/EPTCS.64.7download

We study the relation between process calculi that differ in their either synchronous or asynchronous interaction mechanism. Concretely, we are interested in the conditions under which synchronous interaction can be implemented using just asynchronous interactions in the Pi-calculus. We assume a number of minimal conditions referring to the work of Gorla: a "good" encoding must be compositional and preserve and reflect computations, deadlocks, divergence, and success. Under these conditions, we show that it is not possible to encode synchronous interactions without introducing additional causal dependencies in the translation.

@inproceedings{SPG11, author = "Schicke, Jens-Wolfhard and Peters, Kirstin and Goltz, Ursula", title = "Synchrony vs. Causality in Asynchronous Petri Nets", booktitle = {Proceedings 18th International Workshop on Expressiveness in Concurrency}, year = "2011", month = "September", eprint = "http://www.ips.tu-braunschweig.de/docs/research/schicke/1108.4471v1.pdf", doi = {10.4204/EPTCS.64.9}, editor = "Bas Luttik and Frank Valencia" }

[SPG11] Jens-Wolfhard Schicke, Kirstin Peters and Ursula Goltz
Synchrony vs. Causality in Asynchronous Petri Nets
Proceedings 18th International Workshop on Expressiveness in Concurrency, 2011
DOI 10.4204/EPTCS.64.9download

Given a synchronous system, we study the question whether the behaviour of that system can be exhibited by a (non-trivially) distributed and hence asynchronous implementation. In this paper we show, by counterexample, that synchronous systems cannot in general be implemented in an asynchronous fashion without either introducing an infinite implementation or changing the causal structure of the system behaviour.

@inproceedings{GGS12, author = {Glabbeek , Rob J. van and Goltz , Ursula and Schicke-Uffmann , Jens-Wolfhard}, title = {On Distributability of Petri Nets - (Extended Abstract)}, year = {2012}, pages = {331-345}, editor = {Lars Birkedal}, booktitle = {Foundations of Software Science and Computational Structures - 15th International Conference, FOSSACS 2012, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2012, Tallinn, Estonia, March 24 - April 1, 2012. Proceedings}, publisher = {Springer}, series = {Lecture Notes in Computer Science}, volume = {7213}, eprint = {http://www.tu-braunschweig.de/Medien-DB/ips/fossacs2011.pdf}, doi = {10.1007/978-3-642-28729-9_22} }

Rob J. van Glabbeek, Ursula Goltz, Jens-Wolfhard Schicke-Uffmann
On Distributability of Petri Nets - (Extended Abstract)
Foundations of Software Science and Computational Structures - 15th International Conference, FOSSACS 2012
DOI 10.1007/978-3-642-28729-9_22download

We formalise a general concept of distributed systems as sequential components interacting asynchronously. We define a corresponding class of Petri nets, called LSGA nets, and precisely characterise those system specifications which can be implemented as LSGA nets up to branching ST-bisimilarity with explicit divergence.

Back to concurrency-theory >>