Skip to main content

Asynchronous Communication in Distributed Systems

Asynchronous Communication in Distributed Systems

  • Aim: We aim to discover which systems can be implemented in a distributed way—and how—using only asynchronous communication between components, while preserving desirable properties that may be specified in terms of synchronous communication. In connection with this, we try to establish an expressiveness hierarchy of specification formalisms with different communication paradigms.
     
    Maximal Processes of Petri Nets

  • Approach: We have chosen Petri nets as a suitable specification formalism for concurrent systems that accurately models the mode of communication between components in a distributed system—synchronous or asynchronous—and allows specification of properties of system behaviour that ought to be preserved by distributed implementations. In this framework we investigate which systems allow distributed implementations that preserve all relevant behaviour properties. We also investigate which subset of behavioural properties may be preserved by implementations that work for all concurrent systems.
           Upon answering some of these questions in the framework of Petri nets, we hope to transfer the results to other specification formalisms, such as process algebras. In order to compare the expressive power of different specification formalisms, and different communication paradigms, we develop a general theory of expressiveness, based on valid encodings of the processes specifiable in one formalism in terms of processes specifiable in the other.
  • Collaboration:TU-Braunschweig & TU-Berlin

People


Activities

  • Synchronous versus asynchronous communication: We propose and inventory various definitions of what it means for processes to communicate with each other using only asynchronous communication, and subsequently investigate which processes can be implemented conform these definitions. In deciding whether a given process can be implemented using only asynchronous communication, one needs to choose a semantic equivalence that specifies which aspects of the specified behaviour need to be preserved under implementation. Depending on this choice, either a class of systems can be implemented distributedly—and we aim at giving a structural characterisation of this class—or all systems can be implemented distributedly—and we aim to investigate the strongest behavioural equivalence that makes this possible.
  • Causal semantics of Petri nets: A well-known problem in Petri net theory, open since the mid eighties, is to formalise an appropriate causality-based concept of process or run. The so-called "individual token interpretation", where tokens are distinguished according to their causal history, giving rise to the processes of Goltz and Reisig (1983), makes distinctions between runs that are commonly understood to be the same. This project studies a class of Petri nets, the structural conflict nets, that strictly contains the well-known 1-safe nets and is closed under asynchronous parallel composition. On this class we propose an abstract concept of process, and aim to show that it constitutes a simple and fully satisfying solution.
  • Expressiveness of process calculi: We propose and elaborate a definition of what it means for one system description language to encode another one, thereby enabling an ordering of system description languages with respect to expressive power. Our definition requires a system to be behaviourally equivalent with its encoding, and thus is parametrised with the choice of a suitable semantic equivalence on the represented processes. By means of a series of case studies we hope to ascertain which semantic equivalences are most suitable for certain applications. Finally, we hope to apply the framework to compare the expressiveness of existing process calculi, in particular focussing on calculi with synchronous and with asynchronous communication primitives.

Publications

2015

Abstract PDF Kirstin Peters and Rob van Glabbeek
Analysing and comparing encodability criteria
Combined 22th International Workshop on Expressiveness in Concurrency and 12th Workshop on Structural Operational Semantics, pp. 46-60, Madrid, Spain, August, 2015
Abstract PDF Rob van Glabbeek and Peter Hoefner
CCS: It's not fair! Fair schedulers cannot be implemented in CCS-like languages even under progress and certain fairness assumptions
Acta Informatica, Volume 52, Number 2-3, pp. 175-205, April, 2015
Abstract PDF Rob van Glabbeek, Ursula Goltz and Ernst-Rüdiger Olderog
Special issue on "Combining Compositionality and Concurrency": Part 1
Acta Informatica, pp. 3-4, Springer, 2015

2013

Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke-Uffmann
On characterising distributability
Logical Methods in Computer Science, Volume 9, Number 3, pp. 1-58, September, 2013

2012

Abstract PDF Rob van Glabbeek
Musings on encodings and expressiveness
Combined 19th International Workshop on Expressiveness in Concurrency and 9th Workshop on Structural Operational Semantics, pp. 81–98, Newcastle upon Tyne, United Kingdom, August, 2012
Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke-Uffmann
On distributability of petri nets (extended abstract)
15th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), pp. 331–345, Tallinn, Estonia, March, 2012

2011

Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
On causal semantics of petri nets (extended abstract)
22nd International Conference on Concurrency Theory, pp. 43-59, Aachen, Germany, September, 2011
Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
Abstract processes of place/transition systems
Information Processing Letters, Volume 111, Number 13, pp. 626-633, July, 2011

2009

Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
Symmetric and asymmetric asynchronous interaction
Electronic Notes in Theoretical Computer Science, Volume 229, Number 3, pp. 77-95, July, 2009

2008

Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
On synchronous and asynchronous interaction in distributed systems
33nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2008), pp. 16-35, Torun, Poland, August, 2008
Abstract PDF Rob van Glabbeek, Ursula Goltz and Jens-Wolfhard Schicke
Symmetric and asymmetric asynchronous interaction
First Interaction and Concurrency Experience (ICE'08): Synchronous and Asynchronous Interactions in Concurrent Distributed Systems, pp. 5-22, Reykjavik, Iceland, July, 2008
Best student/young researcher paper.

Non-NICTA/Data61 Publications

2016

Abstract PDF Kirstin Peters, Jens-Wolfhard Schicke-Uffmann, Ursula Goltz and Uwe Nestmann
Synchrony versus causality in distributed systems
Mathematical Structures in Computer Science 26(8), pp. 1459-1498, 2016

2014

Abstract PDF Stephan Mennicke, Jens-Wolfhard Schicke-Uffmann and Ursula Goltz
On the Step Branching Time Closure of Free-Choice Petri Nets
Formal Techniques for Distributed Objects, Components, and Systems, FORTE 2014 pp. 232-248, June 2014

2013

Abstract PDF Kirstin Peters, Uwe Nestmann and Ursula Goltz
On Distributability in Process Calculi
22nd European Symposium on Programming, ESOP 2013, pp. 310-329, Rome, Italy, March, 2013

2011

Abstract PDF Jens-Wolfhard Schicke, Kirstin Peters and Ursula Goltz
Synchrony vs. Causality in Asynchronous Petri Nets
18th International Workshop on Expressiveness in Concurrency, EXPRESS 2011, EPTCS 64, pp. 119-131, Aachen, Germany, September 2011
Abstract PDF Kirstin Peters, Jens-Wolfhard Schicke and Uwe Nestmann
Synchrony vs Causality in the Asynchronous Pi-Calculus
18th International Workshop on Expressiveness in Concurrency, EXPRESS 2011, EPTCS 64, pp. 89-103, Aachen, Germany, September 2011

Master's theses

Abstract PDF Stephan Mennicke
Strong Distributability Criteria for Petri Nets
Institut für Programmierung und Reaktive Systeme, TU Braunschweig, Germany, May, 2013
Abstract PDF Christopher Lippert
Verschiedene Prozesskalküle und ihre relative Ausdrucksmächtigkeit
Institut für Programmierung und Reaktive Systeme, TU Braunschweig, Germany, April, 2013
Abstract PDF Jens-Wolfhard Schicke
Synchrony and Asynchrony in Petri Nets
Institut für Programmierung und Reaktive Systeme, TU Braunschweig, Germany, January, 2009

Contact

Rob van Glabbeek, Robert.vanGlabbeek <at> data61.csiro.au