Loading…
Translational expressiveness: comparing process calculi using encodings
Peters, Kirstin
Wir untersuchen die Beziehung zwischen Prozesskalkülen – insbesondere zwischen verschiedenen Varianten des Pi-Kalküls und dem Join-Kalkül – die sich in den verwendeten Interaktionsmechanismen unterscheiden. Dabei unterscheiden wir im Wesentlichen zwischen synchronen und asynchronen Interaktionsmechanismen, als Basisformen von Interaktion in verteilten Systemen. Aufgrund ihrer größeren Ausdrucksstärke werden synchrone Interaktionsmechanismen oft in Spezifikationen benutzt, asynchrone Interaktionsmechanismen lassen sich in der Regel aber leichter in realen Systemen implementieren. Wir untersuchen unter welchen Bedingungen eine Abbildung synchroner Interaktionen in asynchrone Interaktionen möglich ist. Dazu vergleichen wir die Ausdrucksstärke verschiedener Varianten von Prozesskalkülen, indem wir untersuchen, ob zwischen diesen Sprachen eine Kodierung existieren kann. Besonders interessieren wir uns für die Möglichkeit einer Kodierung, welche den Grad der Verteilbarkeit der zu übersetzenden Prozesse bewahrt. Wir diskutieren verschiedene Resultate sowohl für die Möglichkeit als auch für die Unmöglichkeit einer solchen Kodierung zwischen Varianten des Pi-Kalküls und dem Join-Kalkül.
We study the relation between process calculi—in particular between variants of the pi-calculus and the join-calculus—that differ in their either synchronous or asynchronous interaction mechanism. Synchronous and asynchronous interactions are the two basic paradigms of interactions in distributed systems. While synchronous interaction is widely used in specification languages, asynchronous interaction is often better suited to implement real systems. We are interested in the conditions under which synchronous interactions can be implemented using just asynchronous interactions. We compare the different variants of the calculi with respect to their expressive power. To do so we analyse the existence of encodings between the languages, i.e., translations of the processes of one language into processes of another language. In particular we are interested in encodings that preserve distributability, i.e., in translations that to not reduce the degree of concurrency of the translated processes. We discuss positive as well as negative results between synchronous and asynchronous variants of the pi-calculus and the join-calculus.
