A Two-Level Decomposition Scheme for Markovian Process Algebra Models

Dateibereich 21634

811,3 KB in einer Datei, zuletzt geändert am 16.03.2009

Dateiliste / Details

DateiDateien geändert amGröße
diss.pdf16.03.2009 14:56:29811,3 KB
Die nebenläufige Komposition von Markovketten führt mit steigender Anzahl an involvierten Komponenten schnell zum bekannten Problem der Zustandsraumexplosion, auch bekannt als Largeness Problem. Im Kontext von Markovschen Prozess-Algebren (MPA) ist dieses Problem von besonderer Bedeutung, da kleine und kompakte Modellbeschreibungen in Form von Sprachtermen riesige Markovketten repräsentieren können. Viele altbekannte Gegenstrategien zur Zustandsraumexplosion, wie z.B. Produkt-Form-Lösungen, Lumpability, dünnbesetzte Datenstrukturen, können auf die von der jeweiligen MPA erzeugten Markovkette angewendet werden. Die jüngste Forschung konzentriert sich vornehmlich auf die Klassifikation von syntaktischen Eigenschaften auf der MPA Sprachebene, welche die Anwendbarkeit dieser Strategien garantieren. In der vorliegenden Arbeit schlagen wir einen neuen Ansatz zur Lösung von MPA Modellen vor, der explizit die nebenläufige Struktur des gegebenen Modells ausnutzt. Diese Methode besteht aus zwei Ebenen der Kompositionalität. In der ersten Ebene wird das Modell entlang von globalen Synchronisationspunkten in mehrere Submodelle aufgespalten. Diese Submodelle werden zunächst in Isolation gelöst; anschließend erhält man durch geeignete Kombination der einzelnen Lösungen eine Lösung für das gesamte Modell. Die zweite Ebene der Kompositionalität betrifft die individuellen Submodelle. Unter bestimmten Bedingungen kann jedes Submodell als die parallele Entwicklung mehrerer unabhängiger absorbierender Markovketten beschrieben werden. Diese Unabhängigkeit kann zur Lösung der Submodelle ausgenutzt werden. Als ein Nebenprodukt der Betrachtung der zweiten Ebene der Kompositionalität, präsentieren wir ein neues Resultat über kumulative Ma\ss{}e gemeinsamer absorbierender Markovketten. Falls die marginalen Prozesse unabhängige kontinuierliche Markovketten sind, können die mittlere Zeit bis zur Absorption, sowie die mittlere Verweilzeit in einer transienten Teilmenge des Zustandsraums aus isolierten Lösungen der marginalen Prozesse zusammengesetzt werden. Da bei dieser Methode keine Operationen auf dem gemeinsamen Zustandsraum ausgeführt werden, umgehen wir das Problem der Zustandsraumexplosion. Der Rechenbedarf unserer Methode hängt von Konvergenzeigenschaften der gemeinsamen Markovkette ab, d.h. von der Anzahl an Schritten bis zur Absorption einer in der gemeinsamen kontinuierlichen Markovkette eingebetteten diskreten Markovkette.
Lesezeichen:
Permalink | Teilen/Speichern
Dokumententyp:
Wissenschaftliche Abschlussarbeiten » Dissertation
Fakultät / Institut:
Fakultät für Wirtschaftswissenschaften » Fachgebiet Informatik » Systemmodellierung
Dewey Dezimal-Klassifikation:
300 Sozialwissenschaften » 330 Wirtschaft » 330 Wirtschaft
Beitragende:
Prof. Dr. Müller-Clostermann, Bruno [Betreuer(in), Doktorvater]
Prof. Dr. Haverkort, Boudewijn [Gutachter(in), Rezensent(in)]
Sprache:
Englisch
Kollektion / Status:
Dissertationen / Dokument veröffentlicht
Datum der Promotion:
23.01.2009
Dokument erstellt am:
17.03.2009
Promotionsantrag am:
27.10.2008
Dateien geändert am:
16.03.2009
Medientyp:
Text