# Modellierung verteilter Systeme

## Kapitel 1: Ein Beispiel
### 1.1 Ein Keksautomat
**Beispiel:** ein Automat, der Kekse verkauft mit Einwurfschlitz für Münzen und Entnahmefach für Keksschachtel
- *Anfangszustand:* Münze im Einwurfschlitz
- Entnahmefach leer
- *Plätze* als Ellipsen, siehe Einwurf und Entnahmefach
- *Marke* ist Münze im Einwurf
- *Markierung* ist eine Verteilung von Marken auf Plätze
- *Transition* als Quadrat, siehe Münze kassieren --> Kekse geben
- *Eintreten* der Transition ändert aktuelle Markierung
--> Bewegung oder Fluss von Marken

### 1.2 Ein Blick ins Innere
- Innere des Automaten als Petrinetz: gefüllt mit 5 Schachteln, leere Kasse
- Transition a = "Münze nehmen" tritt ein
- Pfeile zeigen Vorgehen: Münze verschwindet aus Einwurfsschlitz, Erscheint in Kasse, geben eines Signals an Transition b
- Transition b tritt ein
- Beschriftungen der Pfeile alle vorhanden: schwarzer Punkt in Signal & Schachtel im Speicher

### 1.3 Die Schnittstelle
- bisherige Betrachtung des Automats als *geschlossenes System*
- jetzt: Modellierung von Aktivitäten der Umgebung
- Münze wird eingworfen oder Schachtel wird entnommen
- Ansatz:
- Transition "Münze einwerfen" sitzt vor leerem Einwurfschlitz
- "Münze einwerfen" hat keine weiteren Vorbedingungen (wie in realer Welt z.B. Münze existiert)
- Schlitz fasst nie mehr als eine Münze --> Voraussetzung: Einwurfschlitz leer
- Einwurfschlitz wird frei durch Eintritt von a
- Einführung des Platzes "Einwurf möglich" --> immer mit schwarzer Marke belegt, wenn Einwurfschlitz leer
- Einführung des Platzes "kein Signal", damit nie zwei Signale zugleich Transition b feuern
- Einführung Transition "Schachtel entnehmen"
- Transitionen "Münze einwerfen" und "Schachtel entnehmen" als Schnittstellen
--> weitere Ursachen und Wirkungen, die hier nicht modelliert, daher $\epsilon$

### 1.4 Heiße und kalte Transitionen
- *heiße Transitionen:* aktivierte Transitionen treten immer ein, z.b. a und b
- *kalte Transitionen:* aktivierte Transitionen bleiben in dem Zustand ohne einzutreten, z.B. Münze einwerfen und Schachtel
- oftmals zu finden an den Transitionen, die Schnittstellen zur nicht modellierten Umgebungen bilden
- gekennzeichnet mit $\epsilon$

### 1.5 Abläufe
- *Ablauf:* Beschreibung wie Transitionen nacheinander eintreten, bezeichnet mit $\sigma$
- *vollständig*: ein Ablauf ist vollständig, wenn am Ende höchstens eine kalte Transition aktiviert ist
- *unvollständig:* Ablauf ist unvollständig, wenn $\sigma$ eine der heißen Transitionen aktiviert
- mehrere Abläufe entstehen, z.B. durch Wiederholungen von Transitionen
- Abbildung zeigt: erste Schachtel kann entnommen werden, zweite Schachtel kann ins Fach gelegt werden, dritte Münze kann eingeworfen werden (Transitionen unabhängig voneinander)

### 1.6 Alternativen
- Simulieren dass Münze entweder im Münzspeicher oder an Umgebung zurückfällt
- Münze kann schadhaft sein oder Kunde betätigt Rückgabeknopf
- durch Münzeinwurf liegen Voraussetzungen für Eintreten von "Münze zurück" oder a vor
- a und "Münze zurück" stehen im *Konflikt*
- tritt a ein, dann "Münze zurück" nicht und anderherum


### 1.7 Feinschliff

- nach 5 eingeworfenen & 5 ausgegebenen Schachteln ist Speicher leer
- bei 6. Münze bekommt Kunde keine Kekse (OH NEIN)
- Modell erweitern durch einen *Zähler*
- Zähler modelliert als Platz, der immer eine Marke enthält
- Marke ist natürliche Zahl, die Anzahl der Schachteln im Speicher entspricht
- jeder Eintritt der Transition a reduziert Wert um eins
- zu erreichen mit Hilfe eines *Parameters* x
- Voraussetzung von a nun ein *Schaltmodus*, d.h. Ersetzung von x durch korrekten Wert
- Inschrift x > 0 als zusätzliche Voraussetzung in a
- a kann nicht eintreten von Zähler der Marke "0" ist

### 1.8 Verschiedenartige Komponenten
- Plätze und ihre Marken beschreiben:
- Komponenten eines realen Automaten
- Einwurfschlitz, Kasse, Speicher, Entnahmefach
- Münzen und Schachteln als Marken
- technische Abstraktionen
- Zähler mit einer Zahl als Marke
- Signal mit einer schwarzen Marke
- logische Abstraktionen
- Einwurf möglich, kein Signal mit einer schwarzen Marke für Wahrheitswert wahr

- Transitionen beschreiben:
- Aktionen des Automaten in seinem Inneren
- Modellieren Transport von Objekten und Signalen
- a (Münze akzeptieren), b (Schachtel abgeben)
- Aktionen des Automaten an seiner Schnittstelle:
- Münze zurück
- Aktionen des Kunden, die Automat ermöglicht und ihn beeinflussen
- Münze einwerfen, Schachtel entnehmen

- Markierungen als globaler Zustand des Keksautomaten (Verteilung von Marken auf Plätze)
- Aktivität als ein Übergang von einem Zustand in einen anderen entspricht einem Schritt von einer Markierung zu einer anderen im Modell
- Abfolge als Zusammenspiel mehrerer Aktivitäten, also eine Abfolge von Schritten im Modell

Side Note zur Definition von Konflikt: Im Zusammenhang mit Petri-Netzen bezeichnet man mit einem Konflikt ein nicht eindeutiges Verhalten eines Systems. Dies bedeutet, dass 2 Ereignisse um eine Bedingung in Konkurrenz stehen, beide aktiviert sind, aber nur ein Ereignis stattfinden kann, da durch den Eintritt des einen das andere nicht mehr aktiviert ist.

## 2 Die grundlegenden Konzepte

### 2.1 Eine Variante des Keksautomaten
siehe Buch

### 2.2 Komponenten eines Netzes
* **Plätze**: Kreis / Ellipse, modelliert passive Komponente, kann Dinge lagern, speichern, sichtbar machen, sich in einem Zustand befinden
* **Transitionen**: Quadrat / Rechteck, modelliert aktive Komponente, kann Dinge erzeugen, verbrauchen, transportieren, verändern
* **Kanten**: Pfeil, modelliert keine Systemkomponente, nur abstrakte Beziehung zwischen Komponenten: logischer Zusammmenhang, Zugriffsrecht, räumliche Nähe, unmittelbare Kopplung - verbindet Plätze und Transitionen
* **Netzstruktur**: N = (P, T, F), Flussrelation F von N ist Teilmenge von (P x T) u (T x P)
* Vorbereich \*x: {y \| yFx}
* Nachbereich x*: {y \| xFy}
* Schlinge: (x in \*y) & (y in \*x) (Zyklus)
* **Markierung**: "Verteilung von Marken auf Plätze"
* symbolische Marken: Dinge der realen Welt
* abstrakte "schwarze" Marken: oft für Bedingungen (als Platz dargestellt) oder zur Modellierung von konkreten Elemente in elementaren Netzen
* **Beschriftung der Kanten und Transitionen**: Ausdrücke (u.a. Funktionen, Variablen)
* Zentrale Eigenschaft: Wenn man in einem Ausdruck alle Variablen durch Elemente ersetzt, kann man ihn ausrechnen und erhält wiederum ein Element
* Kantenbeschriftung: <span style="text-decoration:overline">pt</span> / <span style="text-decoration:overline">tp</span> (beschreibt die Marken, die bei Eintritt von t "durch die Kante fließen")
* Variablen = Parameter, die verschiedene Instanziierungen ("Modi") einer Transition beschreiben.
* Transition kann nur eintreten, wenn Ausdruck true ist

### 2.3 Die Datenstrukturen für Petrinetze: Multimengen
* Eine Multimenge *a* ist eine Abbildung *a: U -> Natürliche Zahlen*, die jeder Sorte u eines Universums U die Anzahl seiner Vorkommen in a zuordnet
* M(U) bzw. M ist die Menge aller Multimengen über U, wenn der Kontext U eindeutig bestimmt
* Das Universum kann unendlich viele Dinge enthalten. Eine Multimenge a über U kann fast allen (u in U) den Wert a(u) = 0 zuordnen: u kommt dann nicht in a vor.
* a heißt endlich, wenn a(u) != 0 für nur endlich viele (u in U)
* endliche Multimenge Schreibweise [...]
* [] leere Multimenge: a(u) = 0 für alle (u in U)
* Rechenoperationen:
* Addition
* (a + b)(u) = a(u) + b(u)
* Vergleich
* a <= b gdw. für alle (u in U) gilt a(u) <= b(u)
* Subtraktion, wenn b <= a: (deshalb glaube ich auch immer noch, dass bei dem Olat test [a, b, b] - [a, c] nicht definiert sein sollte und nicht das Ergebnis [b,b] ist, da b <= a nicht gilt)
* (a - b)(u) = a(u) - b(u)
* Wenn auf einem Platz p immer nur Marken eines Type &tau; liegen, wird dem Platz p der Typ &tau; zugeordnet

### 2.4 Markierungen als Multimenge
Eine Markierung einer Netzstruktur (P, T, F) ist eine Abbildung *M: P -> M(U)*. M ordnet jedem Platz p eine Multimenge M(p\) zu.
M beschreibt damit einen Zustand des modellierten Systems. Die Anfangsmarkierung wird üblicherweise mit M₀ bezeichnet.

### 2.5 Schritte bei konstanter Kantenbeschriftung
* Im Allgemeinen steht an jeder Kante eine Multimenge als Beschriftung: <span style="text-decoration:overline">pt</span> in M, <span style="text-decoration:overline">tp</span> in M,
* Falls es keine Kante zwischen t und p gibt, gilt <span style="text-decoration:overline">pt</span> = [], <span style="text-decoration:overline">tp</span> = []
* In einer Markierung M kann eine Transistion t eintreten, wenn entsprechende Vorbedingungen vorliegen, wenn M die Transition aktiviert
* Trennung von Aktivierung und Effekt
* Aktivierung: Ob eine Markierung eine Transition aktiviert, hängt ab von der Anschrift der Kanten, die in t enden: M aktiviert t, wenn M(p\) >= <span style="text-decoration:overline">pt</span> für jeder solcher Kanten (p,t) gilt.
* Wenn eine Markierung M eine Transition t aktiviert, so ergibt sich der *Schritt* M -^t-> M', wobei die Markierung M' für jeden Platz p durch M'(p\) = M(p\) - <span style="text-decoration:overline">pt</span> + <span style="text-decoration:overline">tp</span> definiert ist (Effekt).

### 2.6 Schritte bei variabler Kantenbeschriftung
* Wenn ein Ausdruck a an einer Kante steht, wertet er zu einer Multimenge aus
* Wenn ein Ausdruck a an einer Transition steht, wertet er zu Boole'schen Werten aus
* Alle Kantenbeschriftungen rund um t müssen hierbei betrachtet werden
* Seien x₁, ..., x_n die Variablen der Kantenbeschriftungen rund um eine Transition t. Seien u₁, ..., u_n Elemente des Universums. Dann ist &beta;:(x₁ = u₁, ..., x_n = u_n) ein Modus für t.
* Wenn <span style="text-decoration:overline">pt</span> keine Variablen enthält, gilt &beta;$(p,t)$ = <span style="text-decoration:overline">pt</span>
* Ein Modus &beta; für $t$ erzeugt für eine Inschrift $i$ an $t$ einen Wahrheitswert &beta;($i$) => &beta; erzeugt Multimengen an den Kanten rund um $t$
* Schritt von $t$ im Modus &beta;: $M$ -^{t, &beta;}-> $M'$
* Eine Markierung $M$ aktiviert eine Transition $t$ in einem Modus &beta; von $t$, wenn für jede Kante der Form $(p,t)$ gilt: $M(p)\ge$ &beta;$(p,t)$ und für fir Anschrift $i$ von $t$ gilt: &beta;$(i)=true$.
* $M'(p) = M(p) +$ &beta;$(p,t) +$ &beta;$(p,t)$ nach Schritt
* falls keine Kante von $p$ nach $t$ oder umgekehrt, ist &beta;$(p,t) = []$

### 2.7 Systemnetze
* Eine Netzstruktur zusammen mit einer Anfangsmarkierung, Transitionsbedingungen, Kantenanschrifen und als *kalt* gekennzeichnete Transitionen bilden ein *Systemnetz*
* modellieren reale in diskreten Übergängen veränderliche Systeme (Plätze = Zustände, Transitionen = Aktionen, Marken = Ausprägungen von Zustandskomponenten)

### 2.8 Markierungsgraph
* Für ein Systemnetz $N$ mit der Anfangsmarkierung $M_0$ ist eine Markierung $M$ von $N$ erreichbar, wenn es eine Sequenz von Schritten gibt, mit $M_n = M$
* Im Allgemeinen sind unendlich viele Markierungen von $N$ erreichbar
* Erreichbare Markierungen und Schritte können als Markierungsgraph von N dargestellt werden
* Knoten = erreichbare Markierungen
* Kanten = Schritte zwischen erreichbaren Markierungen
* auch Erreichbarkeitsgraph genannt
* kann bei endlich vielen erreichbaren Markierungen als Ausgangspunkt für (rechnergestützt) Analysen genutzt werden

### 2.9 Endmarkierung
* Zustand, in dem ein System für immer verharren kann
* Dort sind höchstens kalte Transitionen aktiviert

## 3. Häufiger Spezialfall: Elementare Systemnetze

- Petrinetze beschreiben wie Kontroll- und Datenflüsse eines verteilten Algorithmus oder verteilten Systems ineinader greifen
- oftmals nur formulieren, wo ein Kontrollfluss momentan steht, ob Betriebsmittel verfügbar, etc.
- hierfür keine Marken verschiedener Sorten nutzen, nur schwarze Punkte
- elementar: durch jeden angrenzenden Pfeil fließt genau eine Marke

3.1 Elementare Systemnetze
- besteht aus Netzstruktur $N = (P, T, F)$
- endliche Mengen $P$ und $T$ von Plätzen und Transitionen
- Anfangsmarkierung $M_0:P \rightarrow N$
- einige Transitionen sind *kalt* gekennzeichnet
- jede Markierung der Form $M:P \rightarrow N$
- jeder Platz trägt Marken $M(p)$
- eine Markierung $M$ aktiviert eine Transition $t$, wenn $M(p)\geq 1$ für jeden Platz $p \in *t$
- für einen Schritt $M \rightarrow t M'$, dann M'(p):
- $M(p)-1$, falls $p \in *t$ und $p \notin t*$
- $M(p)+1$, falls $p \in t*$ und $p \notin *t$
- $M(p)$, sonst
- die mit der Anfangsmarkierung $M_0$ beginnenden Schrittfolgen $M_0 \rightarrow t_1 M_1 \rightarrow t2 ... \rightarrow t_2 M_n$
- Endzustand von N aktiviert höchstens kalte Transitionen

### 3.2 Ein abstraktes Modell des Keksautomaten

- Schachtel und Münzen als schwarze Marken dargestellt
- Zähler als Anzahl schwarzer Marken

### 3.3 Wechselseitiger Ausschluss
- Synchronisation von Aktionen als Platz modellieren
- z.B. eine Aktion kann eintreten, wenn bestimmte Bedingung erfüllt oder lokaler Zustand erfüllt ist
- Problem des wechselseitigen Ausschlusses
- Zusammenspiel zweier Prozesse und einer knappen Ressource
- Forderung, dass die beiden Prozesse niemals zugleich die knappe Ressource verwenden

- jeder Prozess *l* und *r* kann drei Zustände zyklisch durchlaufen: *lokal*, *wartend* und *kritisch*
- *lokal*: Prozess arbeitet ohne knappe Ressource
- *wartend*: Prozess signalisiert Interesse an der Ressource
- Transitiionen a und d sind kalt -> Prozess nicht verpflichtet, diesen Schritt auszuführen
- arbeitet ggf. also irgendwann nur lokal
- *kritisch*: Prozess verwendet die knappe Ressource
- Transitionen b und e führen Schritt von wartend nach kritisch durch
- zusätzliche Marke auf Schlüssel nötig
- Prozess r kann so nicht den kritischen Zustand annehmen, weil Schlüssel nicht verfügbar
- Prozess l gibt Schlüssel erst beim Verlassen des kritischen Zustands zurück
- zwischen b und e unendlich oft Konflikt möglich -> keine Strategie zur Lösung des Konfliktes modelliert
- Konflikt könnte sich immer zugunsten eines Prozesses ausspielen
- anderer Prozess wäre so immer wartend

- mögliche (wenig überzeugende) Lösung:
- beginnend mit r beide Prozesse abwechselnd kritischen Zustand erreichen lassen
- wenn Prozess im lokalen Zustand bleibt, dann hindern des anderen wiederholt seinen kritischen Zustand zu erreichen

### 3.4 Der Crosstalk-Algorithmus
- zwei Agenten kommunizieren über technischen Kanal
- Kanal zuverlässig, so lange *eine* Nachricht übertragen wird
- *crosstalk*: Zusammentreffen der Nachrichten beider Agenten im Kanal
- durch 'Übersprechen' der Nachrichten Verfälschung
- Crosstalk kann nicht verhindert, aber erkennbar gemacht werden
- beispielsweise Nachrichten in vorher abgesprochener Reihenfolge erneut übertragen
- Algorithmus arbeitet in *Runden*: entweder senden einer Nachricht durch einen Agenten oder erkennen von crosstalk von beiden

#### Nachrichten von links nach rechts

- linker Agent verlässt Anfangszustand $ruhig_l$, schickt Nachricht, ab und geht in Wartezustand *wartend* über
- nach Erhalten von *bestätigt* *beenden* der Runde
- dann Anfangszustand $ruhig_r$ durch rechten Agent verlassen durch *antworten* und *bestätigt* die vom linken Agenten gesendete Nachricht
- rechterAgent beendet seine Runde durch *zurückkehren*

#### Nachrichten in beide Richtungen

- System blockiert, wenn in einer Runde beide Agenten Nachricht schicken
- erkennen der Blockade durch Erwarten von *bestätigt*, aber erhalten von *gesendet*
- jeder Agent kann so Blockade durch Transition *crosstalk* auflösen


#### Rundenfehler vermeiden

- Fehler:
- linker Partner kann Nachricht senden $senden_l$
- rechter Partner kann korrekt mit $antworten_r$ empfangen und bestätigen
- danach zurückkehren zum Ausgang und Nachrichten senden $senden_r$
- linker Partner findet Bestätigung $bestätigt_r$ und zugleich neue Nachricht $gesendet_r$, der nicht angesehen werden kann, dass sie zur nächsten Runde gehört
-> fälschlicherweise erkennen als crosstalk

- Lösung:
- Einführen der zusätzlichen Nachricht $beendet_l$
- System ist damit korrekt
- $senden_l$ und $senden_r$ als kalte Transitionen
- kein Zwang Nachricht zu senden, aber wenn Nachricht versendet, dann vollständig verarbeitet
- System terminiert, wenn beide Agenten in Anfangszustand $ruhig$ sind

### 3.5 1-beschränkte elementare Systemnetze
- *1-beschränkt*: jede erreichbare Markierung *M* und jeden Platz *p* vom Systemnetz *N* gilt: $M(p) \leq 1$
- eine Markierung *M* eines 1-beschränkten elementaren Systemnetzes kann als Sequenz der markierten Plätze geschrieben werden
- *ADE* (oder *DAE*, *DEA*) als Anfangsmarkierung des wechselseitigen Ausschlusses
- in dieser Markierung beginnen die Schritte: $ADE \rightarrow c BDE$ und $ADE \rightarrow d ADF$

## 4. Sequentielle und verteilte Abläufe
### 4.1 Sequentielle Abläufe
- elementares Systemnetz mit Anfangsmarkierung *AC*
- *AC* aktiviert die drei Transitionen $AC \rightarrow (a) BC$, $AC \rightarrow (c) D$, $AC \rightarrow (d) AE$
-> Ablauf eines Systemnetzes $N$ als Sequenz von Schritten formulieren
- Anfangsmarkierung $M_0$
- typische Abläufe für $N$: $AC \rightarrow (a) BC \rightarrow (b) \rightarrow (c) D$ und $AC \rightarrow (d) AE \rightarrow (d) BE$, wobei Reihenfolge von *d* und *a* willkürlich
- *sequentieller Ablauf* eines Systemnetz N: $M_0 \rightarrow (t_1) M_1 \rightarrow (t_2) ...$ von Schritten von N beginnend mit $M_0$
- endlich oder unendlich lang
- *vollständige* Abläufe: $M_0 \rightarrow (t_1) M_1 \rightarrow (t_2) ... \rightarrow (t_n) \rightarrow M_n$, wenn §M_n§ eine Endmarkierung ist (also höchstens kalte Transitionen aktiviert)
- ein unendlicher Ablauf ist vollständig, wenn nirgends ein Schritt mit zusätzlicher Transition eingefügt werden kann
- $AC \rightarrow (a) BC \rightarrow (b) AC \rightarrow (a) ...$ ist unvollständig, da *d* eingfügt werden kann

### 4.2 Marken als beschriftete Plätze
- auch möglich: *verteilter* Ablauf statt sequentiell
- Idee: Repräsentieren jedes Auftretens einer Marke auf einem Platz als eigenen Platz
- zwei beschriftete Plätze beispielsweise  und Marken (C) im Vorbereich der Transition *c*
- je 5 mit Speicher und Zähler beschriftet, je ein Platz mit Eingabe und kein Signal
- für normales Systemnetz entsprechend Marken $u_1, ..., u_n$ auf Platz *p* durch *n* entsprechend beschriftete Plätze

### 4.3 Aktionen
- verteilter Ablauf bestehend aus *Aktionen*
- *Aktion A* als schlingenfreies, beschriftetes Netz mit genau einer Transition
- *A* repräsentiert Transition *t* eines elementaren Systemnetzes, wenn
- Transition *a* von *A* mit *t* beschriftet ist
- $*a$ die Marken in $*t$ repräsentiert
- $a*$ die Marken in $t*$ repräsentiert
- für allgemeines Systemnetz $N$ *repräsentiert* Aktion A eine Transition von $N$ im Modus $\beta$, wenn
- Transition *a* vonA mit $(t, \beta)$ beschriftet ist
- $*a$ die Marken $\beta(p,t)$ für jedes $p \in *t$ repräsentiert
- $a*$ für die Marken $\beta(t, q)$ für jedes $p \in t*$ repräsentiert

### 4.4 Verteilte Abläufe
- Ablauf besteht aus azyklischen, zusammengesetzten Aktionen -> Kausalnetz
- *Kausalnetz* $K = (P, T, F)$ mit folgenden Eigenschaften
- kein Platz verzweigt, an jedem Platz endet oder beginnt höchstens *eine* Kante
- keine Sequenz von Kanten schließt sich zum Kreis, für jede Kette der Form $k_0Fk_1 ... k_{n-1}Fk_n$, also $k_0 \neq k_n$
- jede Sequenz von Kanten hat ein erstes Element, keine "nach links unendliche" Kette der Form $... kFk'$
- *Anfang*: Plätze ohne eingehende Pfeile $°K$
- *Ende*: Plätze ohne ausgehende Pfeile $K°$
- kann unendlich viele Elemente haben (NICHT wie bei Systemnetz)
- *partieller Ablauf* eines Systemnetzes: beschriftetes Kausalnetz *K*, in dem jede Transition *t* zusammen mit $*t/,t*$ eine Aktion von *N* bilden -> K beschreibt ein zusammenhängendes Stück Verhalten von *N*
- *vollständig verteiler Ablauf* von N: partieller Ablauf + K° aktiviert höchstens kalte Transitionen + °K als Anfangsmarkierung von N
- Beispiel siehe Buch Seite 52 - 53
- *kausal unabhängig*: wenn Aktionen nicht über eine Pfeilkette miteinander verbunden
- sequentielle und verteilte Abläufe können unendlich werden
- N° eines endlich verteilten Systemnetzes N repräsentiert dessen Endzustand

### 4.5 Beispiel: Eine Glocken-Uhr
- Zähler wird schrittweise um 1 erhöht und wiederholt sich nach 60 Schritten
- Platz *p* enthält immer genau eine Marke mit Zahl zwischen 0 und 59
- beginnend mit 58 erhöht Transition t diese Zahl immer um 1, bis sie von 59 auf 0 gesetzt wird

- Glocken-Uhr: mit Übergang zur neuen Stunde beginnen Glocken zu läuten
- Ende des Glockenspiels nicht an Uhr gekoppelt
- lediglich spezifizieren, dass Glockenspiel geendet, bevor die nächste Stunde beginnt
- Transitionen t und v unabhängig voneinander

### 4.6 Das Kindergartenspiel
- ein Agent (= Objekte), der mit gegebenen Objekten (= Kinder) spielt
- jedes Kind entweder schwarz oder weiß gekleidet
- zwei Kinder können spontan Spielfläche verlassen, eines kann zurückkommen, nach folgender Regel:
- beide verschiedenfarbig, weiß kommt zurück
- gleichfarbig, schwarz kehrt zurück
- wenn beide weiß, dann umziehen zu schwarz
- einen Platz *Kinder*, mit Kinderschar als Anfangsmarkierung
- schwarz- bzw. weiß gekleidetes Kind

- alle drei Transition sind heiß -> Ablauf terminiert, wenn keine Transition aktiviert ist (wenn nur noch 1 Kind übrig)
- alle 3 Abläufe beginnen mit der Anfangsmarkierung

### 4.7 Kausale Ordnung
- verteilter Ablauf protokolliert kausale Zusammenhänge als Alternative zu sequentiellen Abläufen


- verteilte Abläufe sind jedoch verschieden: $N_l$ hat einen einzigen verteilten Ablauf, $N_r$ hat zwei verteilte Abläufe


__________________________________________

- eine Aktion $\alpha$ kann Marken erzeugen, die $\beta$ verwendet: $\alpha$ liegt kausal vor $\beta$
- diese Relationen sind transitiv
- außerdem irreflexiv -> *kausal vor* ist keine Halbordnung
- Ordnung nicht total: Aktion $\delta$ kann unabhängig von $\beta$ eintreten -> Gleichzeitigkeit ist transitiv, Unabhängigkeit ist es nicht
- siehe Seite 59


### 4.8 Die Komposition verteilter Abläufe
- *Komposition* $K \cdot L$: wenn K° das Ende von K und der Anfang °L von L die gleiche Markierung repräsentieren
-> identifizieren gleich beschrifteter Plätze miteinander
- $K \cdot L$ enthält alle Elemente von K und L + übernimmt deren Ordnung
- wenn K und L komponierbar ist, ist $K \cdot L$ der Ablauf $(P_K \cup P_L,\, T_K \cup T_L,\, F_K \cup F_L)$