Ähnlichkeiten und Unterschiede in Hauptprozessalgebren

21

Meines Wissens gibt es drei Hauptprozessalgebren, die eine breite Palette von Forschungen zu formalen Modellen der Parallelität inspiriert haben. Diese sind:

  • CCS und Kalkül beide von Robin Milnerπ
  • CSP von Tony Hoare und
  • ACP von Jan Bergstra und Jan Willem Klop

Alle drei scheinen bis heute eine recht aktive Anhängerschaft zu haben und es wurden enorme Mengen an Forschung an ihnen betrieben.

Was sind die wesentlichen Gemeinsamkeiten und Unterschiede dieser Ansätze? Warum ist die Forschung in der Prozessalgebra divergiert, anstatt konvergiert zu sein, in dem Sinne, dass es kein universelles Modell gibt, das das Feld vereinheitlicht?

Dave Clarke
quelle
2
Eine teilweise ketzerische teilweise Antwort: 3 Ansätze ermöglichen 3-mal so viele Thesen.
Kai

Antworten:

8

Ich kenne nur CSP und CCS / Pi-Kalkül (nicht ACP).

CSP wurde durch zwingende Programmierprozesse motiviert, die über Nachrichten kommunizierten. Hoare versuchte dann, einen einfachen Kalkül daraus herauszuziehen. Andererseits war CCS eine Bemühung, einen grundlegenden Kalkül wie den Lambda-Kalkül zu erstellen. Angesichts ihrer ursprünglichen Ausgangspunkte und ihrer endgültigen Form würde ich sagen, dass sie eher konvergiert als auseinander gegangen sind.

Was ich bei CSP und CCS gemeinsam finde, ist, dass beide auf dem Begriff "Prozess" basieren (und damit eine abstrakte Vorstellung von zeitlich angeordneten Ereignissen). Der Hauptunterschied zwischen ihnen besteht darin, dass CSP zwei Formen der Wahl hat (intern / extern oder nicht deterministisch / deterministisch). In CCS verschmelzen die beiden Ideen zu einer Idee. Ich denke, das ist ein unüberbrückbarer Unterschied.

Die Unterscheidung zwischen interner und externer Wahl ermöglicht es CSP, eine Semantik in Bezug auf lineare Spuren zu haben. Die CCS-Semantik muss dagegen auf Bäumen basieren.

Ich denke, Hoares aktueller Plan für "Theorien vereinen" besteht darin, beide in einem einzigen Rahmen zusammenzufassen. Wir müssen abwarten, was ihm einfällt!

Uday Reddy
quelle
7

Noch eine Teilantwort.

Die Herangehensweise der verschiedenen Gemeinschaften an die Semantik war zumindest ursprünglich unterschiedlich.

  • Die ACP-Semantik ist axiomatisch / algebraisch.
  • CSP-Semantik ist im Allgemeinen in Bezug auf Ablaufverfolgungen denotational.
  • π

Natürlich wurden seit der ursprünglichen Semantik mehr Modelle entwickelt. Interessant ist jedoch, dass die ursprünglichen Forscher mit unterschiedlichen semantischen Ansätzen begannen.

Dave Clarke
quelle
6

Beantworten Sie (zumindest) den Teil Ihrer Frage, warum die Forschung nicht konvergiert, sondern auseinandergegangen ist.

Als kein Experte für Prozessalgebren habe ich mich einmal genau das Gleiche gefragt: Warum gibt es so viele Theorien? Ich wurde auf eine Umfrage von Parrow hingewiesen: Expressivität von Prozessalgebren, 2008 . Ich denke, es ist sehr schön geschrieben und sogar ein Anfänger könnte es verstehen.

Parrow untersucht die Ausdruckskraft von Algebren und beantwortet die Frage. Kurz gesagt, verschiedene Theorien sind verschiedene Werkzeuge zur Lösung einer großen Aufgabe.

Juho
quelle