Zusammenfassung Offene Netze sind eine petrinetzbasierte formale Beschreibung von Services. Zwei offene Netze sind füreinander Partner, wenn ihre Komposition aus jedem erreichbaren Zustand einen Endzustands erreichen kann. Dieser Beitrag erweitert das Konzept der offenen Netze auf High-Level Petrinetze, um die Verarbeitung von Daten in Services darzustellen. Es werden exemplarisch Partner offener High-Level Netze und die in ihnen vorkommenden Ausdrucksmittel untersucht.
(b) N2 (c) N1
N2
Abbildung 1: Kompatible offene Netze und ihre Komposition verschmolzen werden. Die verschmolzenen Plätze werden dabei zu internen Plätzen der Komposition N1 N2. Die Komposition ist ein geschlossenes Netz ohne Sende- und Empfangsplätze.
Für ein einzelnes offenes Netz stellt sich die Frage nach seiner Bedienbarkeit:
Gegeben ein offenes Netz N, gibt es ein kompatibles offenes Netz S, so dass die
Komposition N S aus jedem erreichbaren Zustand einen ausgezeichneten Endzustand erreichen
kann? Eine Ursache von Nichtbedienbarkeit können in der Komposition erreichbare
Deadlocks sein. Bedienbarkeit ist ein Grundproblem der Controllersynthese und
wurde im Kontext von offenen Netzen z. B. in [
Dieser Beitrag verfolgt den Ansatz, Datenwerte explizit in den Formalismus der offenen Netze mit einzubeziehen. Dafür erweitern wir das Konzept der offenen Netze auf High-Level Petrinetze. Datenwerte werden in einem High-Level Petrinetz durch farbige Marken dargestellt. Da die im Folgenden behandelten Probleme weitgehend unabhängig vom verwendeten High-Level Petrinetzformalismus sind, soll die Definition hier nur kurz skizziert werden:
Ein High-Level Petrinetz besteht aus einer Menge von Plätzen P, einer Menge von Transitionen T , einer Menge F von Kanten und einer Anfangsmarkierung m0. Jedem Platz p ist eine eine Menge von Werten (seine Domäne) dom(p) zugeordnet. Jeder Transition t ist ein Guard g(t) und eine Menge var(t) von Schaltvariablen zugeordnet, wobei jede Variable x ebenfalls eine Domäne dom(x) hat. Die Kanten sind mit Termen über den Schaltvariablen beschriftet. Eine Markierung m ist eine Funktion, die jedem Platz p eine Multimenge von Elementen aus dom(p) zuweist. Eine Funktion b , die jede Variable x 2 var(t) einer Transition t mit einem Element e 2 dom(x) belegt, heißt Schaltmodus von t. Beim Schalten einer Transition in Modus b werden die Kantenbeschriftungen mit b ausgewertet und entsprechend Marken von Vorplätzen konsumiert bzw. auf den Nachplätzen produziert. Voraussetzung zum Schalten ist, dass der Guard für b zu true auswertet.
Der folgende Abschnitt erläutert zunächst den Begriff des Partners und zeigt exemplarisch einige Partner von offenen High-Level Petrinetzen. Es wird untersucht, wie sich die Verwendung von Variablen in einem offenen Netz auf die Struktur seiner Partner auswirkt. Es zeigt sich, dass sich selbst bei Verzicht auf Ausdrucksmittel wie Guards, Funktionssymbole und Konstanten nicht-triviale Abhängigkeiten ergeben, die ein Partner berücksichtigen muss. 2
Partner eines datenverarbeitenden Services
Wir betrachten im Folgenden die Partner von offenen High-Level Netzen. Zwei offene
Netze mit jeweils ausgezeichneten Mengen von Endmarkierungen nennen wir Partner,
wenn ihre Komposition schwach terminiert (vergleiche hierzu Def. 4 in [
Beispiel 1 Das offene Netz N aus Abb. 2 setzt eine Nachrichtenweiterleitung um. Die von N auf a (durch Schalten von t0) empfangene Nachricht wird unverändert (durch Schalten von t1) auf b zurückgeschickt. Das offene Netz S1 ist ein Partner von N. S1 p0 t0 p1 t1 pfin x x x x (a) N a b a b 3 3 r0 r1 s0 a s1 b rfin rfin
Abbildung 2: Ein offenes Netz N und kompatible offene Netze sendet zunächst durch Schalten von s0 eine Nachricht auf a mit dem Wert 3. Da N auf b den selben Wert 3 sendet, kann auch s1 schalten. Beide offene Netze erreichen somit ihre Endmarkierungen [p f in] und [r f in]. Daher terminiert N S1 schwach. Das offene Netz S2 ist ebenfalls ein Partner von N. Es kann alternativ zum Wert 3 auch den Wert 4 senden und und diesen anschließend empfangen. Das offene Netz S3 ist dagegen kein Partner von N. Es sendet den Wert 3 auf a, kann auf b aber nur Nachrichten mit Wert 4 empfangen. Da N auf b jedoch den Wert 3 sendet, kann s1 nicht schalten und die Endmarkierung [r f in] von S3 wird nicht erreicht. Das offene Netz S4 ist ein Partner von N. Es wählt zunächst nichtdeterministisch eine natürliche Zahl als Belegung für x und sendet diese auf a. Anschließend empfängt es einen beliebigen Wert auf b (unabhängig davon, ob dieser gleich dem gesendeten ist) und wechselt in seine Endmarkierung [r f in]. S5 verhält sich auf die gleiche Weise, verlangt jedoch, dass der auf b empfangene Wert gleich dem auf a gesendeten Wert sein muss. S5 ist in diesem Sinne präziser als S4: Beide offene Netze sind gleichermaßen Partner von N, jedoch lässt die Struktur von S5 einen genaueren Rückschluss auf die Funktionsweise von N zu. Aus S4 kann man nicht erkennen, dass der von N auf b gesendete Wert stets gleich dem von N auf a empfangenen Wert ist.
Das nächste Beispiel zeigt ein für High-Level Netze spezifisches Phänomen auf. Beispiel 2 Das offene Netz N0 in Abb. 3 hat die gleiche Struktur wie S2 aus Abb. 2. Es ähnelt dem offenen Netz N aus Abb. 2, jedoch sind Eingabe und Ausgabe vertauscht. Trotz dieses scheinbar geringen Unterschieds verfügt N0 über zwei entscheidende Ausdrucksmittel, über die N nicht verfügt: p0 t0 p1 t1 pfin x x x x (a) N0 a b a b x x r0 rfin 1. t0 ist eine erzeugende Transition, d. h. sie führt einen neuen Wert in das Netz ein.
Die Variable x ist beim Schalten von t0 nicht gebunden an den Wert einer Marke auf einem Eingangsplatz. Vielmehr wird x nichtdeterministisch an einen beliebigen Wert seiner Domäne dom(x) gebunden. Im Unterschied zu N, wo t0 einen auf a bereits vorhandenen Wert auf p1 lediglich verschiebt, wird in N0 auf den Plätzen p1 und a ein Wert neu erzeugt. 2. t1 führt einen Test auf Gleichheit aus. t1 kann nur dann schalten, wenn auf p1 und b Marken mit gleichen Werten liegen. Somit bestimmt der von der Umgebung auf b gesendete Wert direkt, ob N0 seine Endmarkierung [p f in] erreichen kann oder nicht. Über einen Partner von N0 können wir folgern: Der vom Partner auf b gesendete Wert darf nicht unabhängig sein vom auf a empfangenen Wert. Vielmehr muss ein Partner Sorge dafür tragen, dass der von ihm auf b gesendete Wert gleich dem von ihm auf a empfangenen ist. Aus diesem Grund ist S10 ein Partner von N0, S20 jedoch nicht. S0 3 berücksichtigt im Unterschied zu S20 die Gleichheit von empfangenem und gesendeten Wert, deckt aber nur einen einzigen Wert aus dom(x) ab. Daher ist s0 für die meisten auf a empfangbaren Werte nicht aktiviert und S30 infolgedessen kein Partner von N0.
Da dom(x) = N eine unendlich große Menge ist, muss jeder Partner ebenfalls über ein Ausdrucksmittel verfügen, das einen unendlich großen Wertebereich abdeckt. Diese Folgerung formulieren wir wie folgt: Vermutung 1. Jeder Partner von N0 enthält eine Kante, die mit einer Variablen beschriftet ist, deren Wertebereich unendlich groß ist.
Eine weitere entscheidende Beobachtung ist, dass ein Partner offenbar gewisse Abhängigkeiten zwischen gesendeten und empfangenen Werten einhalten muss. Augenscheinlicher Verursacher dieses Phänomens ist die Transition t1. Diese ist eine datenabhängige x x (a) x y
x x (b) x (d) x x
x (e) Abbildung 4: Datenunabhängige Transitionen: (a) - (b). Datenabhängige Transitionen: (c) - (e).
Transition. Wir nennen eine Transition datenabhängig, wenn die Entscheidung, ob sie schalten darf, von den Werten der Marken auf ihren Vorplätzen abhängt. Umgekehrt ist eine Transition datenunabhängig, wenn die Entscheidung nur von der Anzahl der Marken auf den Vorplätzen abhängt. Die Werte der produzierten Marken dürfen dagegen sehr wohl von den Werten der konsumierten Marken abhängen. Abb. 4 zeigt einige datenabhängige und -unabhängige Transitionen. Transitionen mit Guards sind im allgemeinen datenabhängig. Es ist offensichtlich, dass eine datenunabhängige Transition genau dan schalten kann, wenn sie im Skelett des Netzes schalten kann.
Das nächste Beispiel zeigt, dass jedoch auch Partner, die keine datenabhängige Transition enthalten, Abhängigkeiten zwischen Datenwerten berücksichtigen müssen. Auch dies steht, wie im vorangehenden Beispiel, in engem Zusammenhang zur Werterzeugung.
(b) S100 2 Partner(N00) (c) S200 2= Partner(N00) (d) S300 2 Partner(N00)
Abbildung 5: Ein offenes Netz N00 und kompatible offene Netze Beispiel 3 Das Netz N00 aus Abb. 5 empfängt zunächst zwei Werte auf a1 und a2 und trifft anschließend eine nichtdeterministische Entscheidung: Es wird eine Marke entwep1 pfin (a) N00 x y y p4 y y x a1 a2 b c1 c2 a1 a2 b c1 c2 1 2 1 2 s2 r3 s4 r0 s0 r1 s1 r2 rfin s3 r5 s5 a1 a2 b c1 c2 3 3 3 r0 s0 r1 s1 r2 s2 r3 rfin s3 s4 a1 a2 b c1 c2
r0 x s0 x r1 x y s1 [x≠y] (x,y) r2 (x,y) z s2 (x,y,z) r3 (x,y,z) s3
[z=sy4] rfin (x,y,z) [z=x] der (a) auf p5 oder (b) auf p6 produziert. Diese Wahl wird der Umgebung kommuniziert, indem entweder (a) der auf a1 empfangene Wert oder (b) der auf a2 empfangene Wert auf b gesendet wird. N00 erwartet anschließend (a) eine Nachricht auf c1 oder (b) eine Nachricht auf c2. Ein Partner von N00 darf niemals zwei gleiche Werte auf a1 und a2 senden. In diesem Fall sind die beiden Fälle (a) und (b) anhand der auf b empfangenen Nachricht nicht unterscheidbar und der Partner kann nicht wissen, ob N00 eine Antwort auf c1 oder c2 erwartet. Der Guard [x 6= y] an Transition s1 in S300 ist also zwingend erforderlich, um zu verhindern, dass N00 möglicherweise einen Deadlock erreicht. Aufgrund des Guards ist s1 eine datenabhängige Transition. Ebenfalls datenabhängig sind jeweils die Transitionen s2 und s3 in S100 sowie s3; s4 in S00, welche eine Fallunterschei3 dung abhängig vom auf b empfangenen Wert treffen. Wir gelangen zu der folgenden Vermutung: Vermutung 2. Jeder Partner von N00 enthält mindestens eine datenabhängige Transition. Diese Folgerung ist bemerkenswert, da N00 selbst weder datenabhängige noch erzeugende Transitionen enthält. Die Partner verwenden also Ausdrucksmittel, die in N00 nicht vorkommen: S100 verwendet Konstanten, S300 einen Guard. N00 verwendet weder Konstanten noch Guards.
Schlussfolgerungen und Ausblick Die untersuchten Beispiele zeigen, dass selbst bei beschränkten Ausdrucksmitteln (nur Variablen, keine Guards) vergleichsweise komplexe Anforderungen an Partner eines offenen Netzes entstehen. Insbesondere zeigt Beispiel 3, dass jeder Partner eines offenen Netzes unter Umständen Ausdrucksmittel verwendet, die im offenen Netz selbst nicht vorkommen. Dies ist vor allem für das Problem der Partnersynthese wichtig. Offen ist, welche Typen von Transitionen hinreichen, um jeden Partner eines offenen Netzes, dass keine datenabhängigen Transitionen enthält, zu beschreiben. Ebenfalls offen ist, welche Techniken zum Beweis der aufgestellten Vermutungen notwendig sind.