Establishing Properties of Interaction Systems


Martens, Moritz


[img]
Preview
PDF
DrArbeitMyThesis.pdf - Published

Download (1MB)

URL: https://ub-madoc.bib.uni-mannheim.de/2629
URN: urn:nbn:de:bsz:180-madoc-26298
Document Type: Doctoral dissertation
Year of publication: 2009
Place of publication: Mannheim
Publishing house: Univ.
University: Universität Mannheim
Evaluator: Majster-Cederbaum, Mila
Date of oral examination: 18 December 2009
Publication language: English
Institution: School of Business Informatics and Mathematics > Praktische Informatik II (Majster-Cederbaum Em)
Subject: 004 Computer science, internet
Classification: CCS: F.1.2 Mode F.1.1 Mode ,
Subject headings (SWD): Nebenläufigkeit , Komponente <Software> , Transitionssystem , Verklemmung , Fortschritt , Robustheit
Individual keywords (German): hinreichende Bedingungen
Keywords (English): concurrency, component-based systems, deadlock-freedom, progress, robustness
Abstract: We exhibit sufficient conditions for generic properties of component based systems. The model we use to describe component based systems is the formalism of interaction systems. Because the state space explosion problem is encountered in interaction systems (i.e., an exploration of the state space gets unfeasible for a large number of components), we follow the guideline that these conditions have to be checkable efficiently (i.e., in time polynomial in the number of components). Further, the conditions are designed in such a way that the information gathered is reusable if a condition is not satisfied. Concretely, we consider deadlock-freedom and progress in interaction systems. We state a sufficient condition for deadlock-freedom that is based on an architectural constraint: We define what it means for an interaction system to be tree-like, and we derive a sufficient condition for deadlock-freedom of such systems. Considering progress, we first present a characterization of this property. Then we state a sufficient condition for progress which is based on a directed graph. We combine this condition with the characterization to point out one possibility to proceed if the graph-criterion does not yield progress. Both sufficient conditions can be checked efficiently because they only require the investigation of certain subsystems. Finally, we consider the effect that failure of some parts of the system has on deadlock-freedom and progress. We define robustness of deadlock-freedom respectively progress under failure, and we explain how the sufficient conditions above have to be adapted in order to be also applicable in this new situation.
Translation of the title: Über den Nachweis von Eigenschaften von Interaktionssystemen (German)
Translation of the abstract: Wir präsentieren hinreichende Bedingungen für allgemeine Eigenschaften von komponentenbasierten Systemen. Als Formalismus zur Modellierung komponentenbasierter Systeme nutzen wir Interaktionssysteme (interaction systems). Da für Interaktionssysteme das Problem der Zustandsraumexplosion auftritt (d.h. für eine große Anzahl von Komponenten ist eine Analyse des gesamten Zustandsraums nicht durchführbar), sollen die Bedingungen effizient überprüfbar sein (d.h. mit polynomiellem Aufwand in der Anzahl der Komponenten). Des Weiteren sind die Bedingungen so geartet, dass die gesammelte Information wiederbenutzbar ist, falls eine Bedingung nicht erfüllt sein sollte. Im Einzelnen betrachten wir Deadlockfreiheit und Fortschritt in Interaktionssystemen. Wir formulieren eine hinreichende Bedingung für Deadlockfreiheit, welche auf einer Einschränkung an die Kommunikationsarchitektur basiert: Wir definieren baumartige Interaktionssysteme und leiten dann eine hinreichende Bedingung für die Deadlockfreiheit solcher Systeme her. Im Hinblick auf Fortschritt geben wir zunachst eine Charakterisierung dieser Eigenschaft an. Dann formulieren wir basierend auf einem gerichteten Graphen eine hinreichende Bedingung für Fortschritt. Wir kombinieren diese Bedingung mit der Charakterisierung, um einen Ausweg aufzuzeigen, falls das Graphkriterium nicht erfüllt ist. Beide hinreichenden Bedingungen können effizient überprüft werden, weil nur die Analyse bestimmter Teilsysteme erforderlich ist. Schließlich untersuchen wir noch die Auswirkungen, welche der Ausfall bestimmter Teile eines Systems auf Deadlockfreiheit und Fortschritt hat. Wir definieren zunächst Robustheit von Deadlockfreiheit beziehungsweise Fortschritt unter Ausfall. Dann erklären wir, wie die obigen hinreichenden Bedingungen angepasst werden müssen, damit sie auf diese neue Situation angewendet werden können. (German)
Additional information:

Dieser Eintrag ist Teil der Universitätsbibliographie.

Das Dokument wird vom Publikationsserver der Universitätsbibliothek Mannheim bereitgestellt.




+ Citation Example and Export

Martens, Moritz (2009) Establishing Properties of Interaction Systems. Open Access Mannheim [Doctoral dissertation]
[img]
Preview


+ Search Authors in

+ Download Statistics

Downloads per month over past year

View more statistics



You have found an error? Please let us know about your desired correction here: E-Mail


Actions (login required)

Show item Show item