Wenn ein Prozess einen anderen Prozess erzeugt

13

Mein Hintergrund liegt in der Komplexitätstheorie / -logik (wo es meistens nur einen Prozess gibt) und im verteilten Rechnen (wo es Prozesse gibt und einer oder mehrere im Laufe der Zeit ausfallen könnten). Jetzt möchte ich jedoch in der Lage sein, etwas über einen Prozess zu sagen, der einen anderen Prozess erzeugt / erzeugt / auslöst. Gibt es Strenge bei Parallel-Computing, Betriebssystemen usw., die dies erklären?n

Motivation:

Ich versuche, Modelle zu konstruieren, die bestimmte Merkmale molekularer Wechselwirkungen abstrahieren. Ich möchte sagen, dass die Menge der chemischen Reaktionen ein unabhängiger Prozess ist und dass zu einem bestimmten Zeitpunkt weiterer unabhängiger Prozess . Intuitiv fühlen sich diese Dinge wie unabhängige Prozesse an, weil sie nach einiger Zeit keinen Kontakt miteinander haben - oder nur sehr wenig Kontakt, sondern nur "Botschaften" austauschen.StSt

Formeller:

(1) Gibt es bereits existierende CS-Definitionen, die den Begriff eines Prozesses erfassen, der einen anderen unabhängigen Prozess hervorbringt? Ich bin besonders daran interessiert, in der Lage zu sein, abzugrenzen, wo aufhört und beginnt, und warum dies "vernünftig" ist.SS

(2) Wenn es mehr als eine Antwort auf (1) gibt, welche Vor- und Nachteile sehen Sie für die verschiedenen Definitionen?

(Hinweis: Ich habe keine Ahnung, wie ich dies angemessen kennzeichnen soll, und plane, es abhängig von den Antworten erneut zu kennzeichnen.)

Aaron Sterling
quelle
Ich fand den forkSystemaufruf in Unix-ähnlichen Betriebssystemen immer konzeptionell sehr elegant. Sie können es als atomare Operation betrachten, die den aktuellen Prozess dupliziert . Vor einer Gabel gab es nur einen Prozess , während es nach der Gabel zwei Prozesse S und S 'gibt . Wenn wir vereinfachen Dinge, S und S ' sind identisch in allen anderen Aspekten, mit der Ausnahme , dass es eine Anzeige eines Bit ist , das läßt S ' weiß , dass es das „neue“ Verfahren ist , während S weiß , dass es der „Original“ Prozess. Danach S und S 'SSSSSSSSSkönnen separat fortfahren und sie können sich sogar selbst modifizieren .
Jukka Suomela
@Jukka: Danke :-) Es wäre süß, wenn es eine Möglichkeit gäbe, das, was ich mache, mit einem Unix-Primitiv zu verbinden.
Aaron Sterling

Antworten:

13

Natürlich gibt es viele Systeme zur Modellierung von Prozessen. Diese fallen unter die Kategorie der Prozessalgebren . Die wichtigsten Beispiele sind Kalkülπ , CCS , ACP und CSP .

Prozesskalküle verfügen über grundlegende Mechanismen zum Festlegen des Prozessverhaltens, z. B .: Senden und Empfangen von Nachrichten (synchron oder asynchron), Erstellen paralleler Prozesse, nicht deterministische Auswahl zwischen Verhalten und Replikation von Prozessen. Obwohl die Kalküle in Bezug auf die Anzahl der Konstrukte klein sind, sind sie sehr aussagekräftig und es wurde viel Forschung in die Untersuchung ihrer Eigenschaften gesteckt.

Der Kalkül unterscheidet sich von den anderen darin, dass er im Wesentlichen die Übergabe von Prozessen als erstklassige Werte ermöglicht. Tatsächlich können Kanalnamen als erstklassige Werte weitergegeben werden, wodurch Änderungen in der dynamischen Topologie möglich werden. Dies ist wahrscheinlich der von Ihnen gewünschte Kalkül, da er die größte Dynamik bietet.π

CSP (Communicating Sequential Processes) ist aus der Perspektive der Modellierung von Molekülen etwas seltsam. Es hat eine Menge Hintergrundtheorie und Werkzeugunterstützung. (Erfunden von CAR Hoare.)

CCS und ACP haben eine geringere Dynamik als der Kalkül, sind jedoch viel einfacher zu analysieren und zu simulieren. Für ACP steht ein solides Toolset mit den Bezeichnungen μ CRL (und μ CRL2) zur Verfügung. Ähnliche Tools gibt es sicherlich auch für CCS.πμμ

Ich beginne mit der Untersuchung der verwandten Arbeiten (siehe unten) und finde dann heraus, welcher der Modellierungsformalismen zu dem passt, wonach Sie suchen.

Tatsächlich hat es eine Menge Arbeit gegeben, chemische Reaktionen und biologische Prozesse mithilfe der Prozessalgebra zu modellieren. Wahrscheinlich ist die Publikationsliste von Luca Cardelli der beste Ort, um danach zu suchen . Seine gesamte Forschungslinie zu BioComputing umfasst wahrscheinlich 30 Artikel zu diesem Thema. Dieser Vortrag gibt einen Überblick über einen Großteil seiner Arbeit. Das eine ist etwas formal, obwohl die Papiere lesen wirklich der einzige Weg ist , um die Details zu sehen.

Ein Ansatz, der chemische Prozesse direkt modelliert, ist CHAM (die chemische abstrakte Maschine). Der Hauptbestandteil ist hier eine Lösung von Molekülen und Membranen. Es gibt Heiz- und Kühlregeln für die Umlagerung der Moleküle und für die Beseitigung von Müll. Diese Regeln sind umkehrbar. Schließlich gibt es Reaktionsregeln, die Reaktionen modellieren. Im Gegensatz zu Prozessalgebren sorgen sich CHAM-Modelle nicht so sehr um die Syntax von Prozessen, sodass Sie Ihre eigene Darstellung der Moleküle erfinden können.

Rewrite-Logik, wie sie im Toolset realisiert wurde Maude bietet einen anderen mehr oder weniger direkten Ansatz, um solche Reaktionen zu spezifizieren. Man muss nur die Umschreiberegeln spezifizieren, die Abgabe der "Suppe" erfolgt automatisch. Das Toolset würde die Simulation und Analyse von (geringfügigen) chemischen Reaktionen ermöglichen. Es gibt auch eine probabilistische Variante von Maude.

Dave Clarke
quelle
Könnten Petrinetze auch in Betracht gezogen werden? Das Gabeln könnte modelliert werden, indem man eine Stelle mit zwei ausgehenden Übergängen hat.
M. Alaggan
Generell können Interaktionen im Petrinetz-Stil in linearer Logik modelliert werden (ein Beispiel, wenn auch nicht das einzige, siehe "Ein konkurrierendes logisches Gerüst: Das Propositionsfragment" von Watkins et al., TYPES 2003)
Rob Simmons
π
@M. Alaggan: An der Oberfläche scheint es, dass Petri-Netze den Job machen könnten. Jeder Ort könnte als Pool von Chemikalien angesehen werden. Jeder Übergang kann als Reaktion angesehen werden. Wenn wir also Orte mit den Namen H und O und H2O hätten, könnte ein Übergang zwei Token von H eins von O nehmen und ein Token in H2O legen. Das Problem bei der Modellierung auf diese Weise ist, dass nur einer dieser Übergänge gleichzeitig ausgelöst werden kann, im Gegensatz zu Prozessalgebren, bei denen viele solcher Übergänge gleichzeitig ausgelöst werden könnten.
Dave Clarke
@Aaron: Je nachdem, was Sie versuchen, können modernere Prozesskalküle wie BioPEPA für Sie nützlich sein.
András Salamon
7

Eine andere Art der Arbeit, die - glaube ich - mit BioComputing zu tun hat, aber nicht mit BioComputing identisch ist (in diesem Bereich kenne ich mich leider nicht so gut aus), ist das "Membrancomputing".

Mein Verständnis von Membran-Computing ist, dass es Metaphern verwendet, die größtenteils in der Prozess-Caclui-Welt entwickelt wurden (Dave Clarkes Antwort gab dort eine Reihe guter Hinweise), um zelluläre Interaktionen explizit zu modellieren. Ein guter Leitfaden für das Membran-Computing ist wahrscheinlich der treffend benannte Leitfaden für das Membran-Computing von Paun und Rozenberg in TCS. Es war vor ein paar Jahren (und ich bin im Moment nicht in einer Paywall, um das zu überprüfen), aber ich glaube, dass einige Modelle des Membrancomputing den Begriff "Forking" haben, der die zelluläre Mitose irgendwie widerspiegeln soll.

Rob Simmons
quelle
Danke, Rob. Cardellis Arbeit berührt, soweit ich weiß, nicht das Membrancomputing. Es konzentriert sich mehr auf den Aufbau einer Programmiersprachtheorie für DNA-Schaltkreise. Ich schätze den Zeiger, aber ich schätze, ich suche nach etwas mehr "Mainstream" (was bedeutet, dass es in keiner Weise mit der Biologie zu tun hat).
Aaron Sterling
1
Dies ist sicherlich eine Alternative. @Aaron: Cardellis Brane Calculus lucacardelli.name/Papers/Brane%20Calculi.pdf modelliert Membranen.
Dave Clarke
Ha! Die Kraft des Crowdsourcing! Danke noch einmal! :-)
Aaron Sterling