Synchronous and Asynchronous Interaction in Distributed Systems

• Applicants: Professorin Dr. Ursula Goltz; Professor Dr.-Ing. Uwe Nestmann; Dr. Kirstin Peters
• Subject Area: Theoretical Computer Science
• Term: from 2010 to 2018
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 167512345

In the first period of our project, 'Synchronous and Asynchronous Interaction in Distributed Systems' (SAS), we have investigated basic interaction patterns in modelling languages for distributed systems. Our goal was to analyse the border of expressiveness and distributability between synchronous and asynchronous interaction patterns. Synchronous interaction is a powerful concept and is the foundation of many approaches to specification, but causes problems regarding efficiency and implementability in a distributed system. Asynchronous interaction unproblematic for distributability, but in general less expressive than its synchronous counterpart. As the main result of the first project period, we have identified a border of asynchronously distributable interaction patterns. We have characterised this border precisely for Petri nets as well as for process calculi by significant results. Moreover, it turned out that this border is part of a hierarchy of interaction patterns. We already achieved additional selective results in this hierarchy for Petri nets and for process calculi.In the second project period of SAS we plan to start by refining the identified hierarchy. Above and below of the already identified border, we expect several stages of interaction patterns. For each of these stages, we want to identify the minimal requirements on the underlying system model, under which the associated interaction patterns are implementable. We will provide prototypical realisations for these positive results. Furthermore, we extend the so far investigated formalisms and distributability concepts by aspects for probabilistics, real time and fault tolerance. This allows us to consider basic insights on distributed algorithms from the viewpoint of our formal models and their implementability. We will verify the generality of our results by transferring them to related formalisms, such as I/O automata and the ACTOR model.

• DFG Programme: Research Grants
• International Connection: Australia
• Participating Person: Professor Dr. Robert van Glabbeek