---
# System prepended metadata

title: Modellierung verteilter Systeme

---

# 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
![](https://i.imgur.com/1JQNgyN.png =450x90)
- *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
![](https://i.imgur.com/vjy4ic1.png =400x200)
- 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
![](https://i.imgur.com/EAJ5Met.png =500x)
- 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
![](https://i.imgur.com/FJvgEWi.png =500x)
- *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
![](https://i.imgur.com/UEEXxOy.png =500x)
- 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

![](https://i.imgur.com/eBKF2DZ.png =200x)


### 1.7 Feinschliff
![](https://i.imgur.com/g22QRtR.png =500x)

- 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<sub>0</sub> 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 -<sup>t</sup>-> 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<sub>1</sub>, ..., x<sub>n</sub> die Variablen der Kantenbeschriftungen rund um eine Transition t. Seien u<sub>1</sub>, ..., u<sub>n</sub> Elemente des Universums. Dann ist &beta;:(x<sub>1</sub> = u<sub>1</sub>, ..., x<sub>n</sub> = u<sub>n</sub>) 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$ -<sup>t, &beta;</sup>-> $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
![](https://i.imgur.com/6rC99Tp.png =500x)

- 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

![](https://i.imgur.com/pq8O6D4.png =500x)
- 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

![](https://i.imgur.com/ZY02jt0.png =500x)
- 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

![](https://i.imgur.com/D3RGHRl.png =500x)
- 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
![](https://i.imgur.com/mNwd3IP.png =500x)

- 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

![](https://i.imgur.com/IpyHCWs.png =500x)



#### Rundenfehler vermeiden 
![](https://i.imgur.com/KL36xpN.png =500x)

- 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
![](https://i.imgur.com/pSZb16t.png =500x)
- 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 
![](https://i.imgur.com/RCmZxDn.png)
    - zwei beschriftete Plätze beispielsweise ![](https://i.imgur.com/SQDCK4u.png) 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
    ![](https://i.imgur.com/SQDCK4u.png)

### 4.3 Aktionen
- verteilter Ablauf bestehend aus *Aktionen*
- *Aktion A* als schlingenfreies, beschriftetes Netz mit genau einer Transition
![](https://i.imgur.com/EzSRjjQ.png)
- *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
    ![](https://i.imgur.com/O4A8jB5.png =500x)
    ![](https://i.imgur.com/QLvqhCQ.png)
- 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 
![](https://i.imgur.com/7vph8dV.png)

### 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
![](https://i.imgur.com/WcRgiGj.png)
- 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

![](https://i.imgur.com/GgNctqH.png =500x)
- 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
![](https://i.imgur.com/9mXPaj3.png)

![](https://i.imgur.com/8uqsbCb.png)
- 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 
![](https://i.imgur.com/UM0vPUZ.png =500x)

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

![](https://i.imgur.com/mTYpB8H.png =500x)
![](https://i.imgur.com/vkfiUwM.png)

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

![](https://i.imgur.com/WAv5DB1.png =500x)

__________________________________________
![](https://i.imgur.com/WnJD4lZ.png)

- 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

![](https://i.imgur.com/qMZqpnt.png)

### 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)$

![](https://i.imgur.com/Vq8Xwdc.png =500x)






  


