MvS Modellierung verteilter Systeme UHH

Ein elementares Systemnetz besteht aus einer Netzstruktur N= (P,T,F) , wobei

P= Platz

T= Transition

F= Kante (von,nach),

einer Angangsmarkierung Mo,

Transitionsbedingungen,

Kanteninschriften,

mit epsilon gekennzeichnete kalte Transitionen.

Analyse ist das Nachweisen von wichtigen Eigenschaften eines Systemnetzes N. 

Eine wichtige Eigenschaft sind hier erreichbare Markierungen von N:

• Ist M erreichbar?
• Wird M auf jeden Fall erreicht?

Synthese ist das Ableiten eines Systemsnetzes N aus einem System, welches zB als Zustandsautomat modelliert ist.

Synthesesatz: Falls das SyntheseProblem eines Zustandsautomaten G mit einem 1-beschränkten elementare Systemnetz lösbar ist, dass ist das Systemnetz von G eine Lösung.

=> Also ein Systemnetz N löst das Syntheseproblem, wenn der Markierungsgraph G von N isomorph ist (wenn jeder Knoten von G eindeutig einem Knoten von Z entspricht)

Ansonsten ist das Syntheseproblem nicht mit einem 1-beschränkten elementaren Systemnetz lösbar und man benötigt den Algorithmus.

1. Regionen bilden

2. Minimale Regionen werden Plätze

3. Kanteninschriften werden Transitionen

Sequenzieller Ablauf:

Der Ablauf eines Systemnetzes N, formuliert als Sequenz von Schritten, beginnend mit der Anfangsmarkierung M_0.

Ein sequenzieller Ablauf ist endlich oder unendlich lang und kann vollständig sein, wenn M_n eine Endmarkierung ist (nur kalte Transitionen aktiviert), oder wenn keine Schritte mehr mit einer zusätzl. Transition mgl. sind.

Verteilter Ablauf:

Ein verteilter Ablauf besteht aus Aktionen.

Eine Aktion ist ein beschriftetes, Schlinkenfreies Netz, mit genau einer Transition.

Ein Kausalnetz ist ein verteilter Ablauf

Zusammenhang Eindeutig?

Nein! Verteilte Abläufe verlangen einen größeren technischen Aufwand, repräsentieren das Verhalten aber genauer

Ein Kausalnetz ist ein verteilter Ablauf eines elementaren Systemnetzes N=(P,T,F), wenn

• zyklenfrei
• an allen Stellen höchstens eine Eingangs- und Ausgangstransition hat - also kein Platz ist verzweigt
• fängt mit M₀ an
• endet mit Epsilon

K beschreibt ein zusammenhängendes Stück Verhalten von N.

Man kann auch kausale Unabhängigkeit zeigen, denn generell bescheibt eine Kette von Kanten von einem x zu einem y, dass x kaussal vor y steht. Sind x und y garnicht verbunden, sind die kausal unabhängig.

Es handelt sich um Eigenschaften, die direkt am Zustandsautomaten festgemacht werden können

Lebendigkeit: 

Von jeder erreichbaren Markierung M aus, ist für jede Transition t eine Markierung M' erreichbar, die t aktiviert.

Zustandsautomat: An jedem Knoten des dazugehörigen Zustandsautomaten G beginnt ein Weg, auf dem die Transition t als Pfeilinschrift vorkommt.

Beschränktheit:

Es gibt eine Zahl b, sodass jeder Platz von N unter jeder erreichbaren Markierung höchstens b Marken enthällt

Zustandsautomat: G ist endlich

Verklemmung: (= Deadlock)

Eine Markierung M, die keine einzige Transition aktiviert, beschreibt einen totalen Systemstillstand.

N ist deadlockfrei, wen jede erreichbare Markierung mind. eine Transition aktiviert.

Zustandsautomat: An jedem Knoten von G beginnt mind. eine Kante.

Beschränktheit:

Es gibt eine Zahl b, sodass jeder Platz von N unter jeder erreichbaren Markierung höchstens b Marken enthällt.

1. Man kann es entweder am Zustandsgraphen stehen, denn G ist endlich

2. Man kann es an dem Markierungsgraphen ablesen, denn der visusalisiert die erreichbaren Markierungen und Schritte eines Systemnetzes N. Allerdings hat ein Systemnetz mit mind. 1 unbeschränkten Platz einen unendlichen Markierungsgraphen

3. Man konstruiert einen endlich Überdeckungsgraphen, weil er einen unendlichen Markierungsgraphen approximieren kann. Regelmäßige unendliche Teilstrukturen werden durch omega-Markierungen  in endliche Teilgraphen verdichtet. Wenn keine omega-Markierungen entstehen, erhalten wir einen normalen Markierungsgraphen

4. Man berechnet die Platzinvarianten, denn ein Platz p mit einer positiven invariante ist beschränkt.

Man konstruiert einen endlich Überdeckungsgraphen, weil er einen unendlichen Markierungsgraphen approximieren kann. Regelmäßige unendliche Teilstrukturen werden durch omega-Markierungen  in endliche Teilgraphen verdichtet. 

Algorithmus:

1. M₀ ist ein Knoten
2. In jedem Schritt entsteht eine Kante zu einem vorhandenen oder zu einem neuen Knoten
   • Der Graph wird nun um die Kante M-> M'' ergänzt. Falls M'' noch kein Knoten ist, wird er einer
   • M'' ist entwerder eine omega-Markierung oder eine normale M'(p):
   • Wenn M'>M für vorher auf dem Pfad dahin berechnete Markierungen, wird an den Stellen omega gewählt
3. Terminiert, wenn für jeden Knoten M und jede in M aktivierte Transition t eine t-beschriftete Kante beginnt.
4. Wenn keine omega-Markierungen entstehen, erhalten wir einen normalen Markierungsgraphen

Die Lösung der Gleichung x*N=→0 heißt Platzinvariante von N

1. Man kann Markierungen als Spaltenvektoren schreiben, wobei die Anzahl der Marken drin steht und die Stelle anzeigt, an welchem Platz
2. Man kann Transitionen als Spaltenvektoren schreiben
   • -1 wenn Platz im Vorbereich
   • 1 wenn Platz im Nachbereich
   • 0 sonst
3. Daraus Matrix für alle Plätze erstellen und Gleichung lösen

Transisitionsinvarianten geben an, wie oft welche Transition schalten muss, um die Anfangsmarkierung zu reproduzieren.

1. drei Transitionen "input" "was tun" und "output"

2. in der Mitte mehrere Transitionen die mit durch eine message im Input und dann guards an den Transitionen unterschieden werden 

3. mit einem Knoten als Wissensbasis anstatt eben die vielen Transitionen zur Fallunterscheidung

4. Agenteneigenschaften:

   • Autonomie

   • Intelligenz, Lernfähigkeit, Adaptiion und Flexibilität

   • Reaktivität, proaktivität

   • Klare Umgebungsabgrenzung (Kapselung)

   • Agiert mit der Umwelt

Infrastruktur

Das Multiagentensystem repräsentiert Orte (Plattformen) und deren Kommunikations- und Mobilitätsstruktur.
Diese wird in der Abbildung als statisch dargestellt.
Generell gilt, dass auch diese Ebene veränderlich ist.

Wichtig sind die vier Ebenen UND ihre Beziehungen. Diese lassen sich für beliebige Einheiten kombinieren.

Jede Einheit kann als Repräsentant jeder Ebene auftreten. Dies erlaubt mehrfach geschachtelte Systeme.

Zentrale Idee ist die gekapselte Einbettung in eine bestimmte
Umgebung; die jeweils festgelegte Relation von Einheit und Umgebung über deren Schnittstelle zur jeweils anderen Einheit liefert die softwaretechnisch und modellierungstechnisch relevante Beziehung Insgesamt ergibt sich ein agentenorientiertes Architekturmodell.

Platform
Die Plattform verfeinert die Darstellung der Orte aus der ersten
Ebene. Sie stellt die Umgebung für die Agenten dar. Damit ergibt
sich die Kommunikationsstruktureinbettung zu den anderen
Plattformen und die plattforminterne Kommunikations- und
Interaktionsmöglichkeit.
Wichtig ist die Beziehung zwischen Ebene 1 und Ebene 2. Sie
beschreibt die Einbettung von Plattformen in eine
Kommunikations- und Mobilitätsinfrastruktur.

Agent

Der Agent  befindet sich in seiner Umgebung, der Plattform. Gleichzeitig ist er die Umgebung
für die Protokolle und die Wissensbasis. 

Wichtig ist wiederum die Beziehung zwischen Plattform und Agent. 

Auch hier erfolgt eine bestimmte Einbettung. Die externe und interne Kommunikation und Mobilität auf der Plattform wird festgelegt.

Protokoll

Das Protokoll befindet sich in seiner Umgebung, dem Agenten.

Im Zentrum der Betrachtung steht wiederum die Beziehung zwischen Agent und Protokoll.
Auch hier erfolgt eine bestimmte Einbettung.

Die Kommunikation und Mobilität innerhalb des Agenten wird festgelegt.
 

Orthogonalität / Parallelität:

AND-Dekomposition: alle Subzustände eines Zustandes
werden gleichzeitig eingenommen , wenn dieser betreten wird.

grafische Repräsentation: gestrichelte Linien, die die einzelnen
AND-Komponenten voneinander trennen.