Establishing properties of interaction systems [Elektronische Ressource] / vorgelegt von Moritz Martens

Establishing Properties ofInteraction SystemsInauguraldissertationzur Erlangung des akademischen Gradeseines Doktors der Naturwissenschaftender Universit¨at Mannheimvorgelegt vonMoritz Martensaus K¨olnMannheim, November 2009Dekan: Professor Dr. Felix Freiling, Universit¨at MannheimReferentin: Professor Dr. Mila Majster-Cederbaum, Universit¨at MannheimKorreferent: Professor Dr. Felix Freiling, Universit¨at MannheimTag der mu¨ndlichen Pru¨fung: 18. Dezember 2009AbstractWe exhibit sufficient conditions for generic properties of component basedsystems. The model we use to describe component based systems is theformalismofinteractionsystems. Becausethestatespaceexplosionproblemis encountered in interaction systems (i.e., an exploration of the state spacegets unfeasible for a large number of components), we follow the guidelinethattheseconditionshavetobecheckableefficiently(i.e., intimepolynomialin the number of components). Further, the conditions are designed in suchawaythattheinformationgatheredisreusableifaconditionisnotsatisfied.Concretely, we consider deadlock-freedom and progress in interactionsystems. We state a sufficient condition for deadlock-freedom that is basedon an architectural constraint: We define what it means for an interactionsystem to be tree-like, and we derive a sufficient condition for deadlock-freedom of such systems. Considering progress, we first present a charac-terization of this property.