Synchronous and Asynchronous Interaction in Distributed Systems

在我们项目的第一阶段，“分布式系统中的同步和异步交互”（SAS），我们已经研究了分布式系统建模语言中的基本交互模式。我们的目标是分析同步和异步交互模式之间的表达性和可分布性的边界。同步交互是一个强大的概念，是许多规范方法的基础，但在分布式系统中会导致效率和可实现性方面的问题。异步交互在可分布性方面没有问题，但通常不如同步交互具有更好的表达性。作为项目第一阶段的主要成果，我们已经确定了异步分布式交互模式的边界。我们的特点是这个边界正是Petri网以及过程演算的显着结果。此外，事实证明，这个边界是互动模式层次结构的一部分。我们已经取得了额外的选择性成果，在这个层次结构的Petri网和过程calculation.In SAS的第二个项目期间，我们计划开始细化确定的层次结构。在已经确定的边界之上和之下，我们预期交互模式的几个阶段。对于这些阶段中的每一个，我们都希望确定底层系统模型上的最小需求，在这些需求下，相关的交互模式是可实现的。我们将为这些积极的结果提供原型实现。此外，我们扩展到目前为止调查的形式主义和可分配的概念方面的概率，真实的时间和容错。这使我们能够从我们的正式模型及其可实现性的角度考虑分布式算法的基本见解。我们将验证我们的结果的一般性，将它们转移到相关的形式主义，如I/O自动机和ACTOR模型。

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.