Das vorliegende Buch betrachtet verteilte Systeme, welche unter wahrscheinlichkeitstheoretischen Einflüssen, wie beispielsweise Fehlern, arbeiten. Wie gut können solche Systeme unter den Auswirkungen von Fehlern ihren Dienst erbringen? Wie gut können sie sich von Fehlern erholen? Neben einer ausführlichen Einleitung in das Gebiet der Fehlertoleranz stellt dieses Buch ein Maß genannt 'limiting window availability' zur Beantwortung dieser Fragen vor. Desweiteren wird eine Methode zur Berechnung der 'limiting window availability' entwickelt, welche auf der Konstruktion des Transitionsmodells aus System- und Umgebungsmodell basiert. Die Methode ist jedoch nur eingeschränkt tragfähig, da sich die Größe des Transitionsmodells exponentiell zur Größe des Systemmodells verhält. Dieser Effekt ist allgemein als Zustandsraumexplosion bekannt. Die Kombination von Dekomposition und Lumping - Methoden zur Zustandsraumreduktion aus dem Bereich Modellprüfung - erlaubt es jedoch, die Zustandsraumexplosion zu dämpfen. Dadurch kann das Spektrum analysierbarer Systeme maßgeblich erweitert werden. <dt.>
The present book focuses on distributed systems operating under probabilistic influences like faults. How well can such systems provide their service under the effects of faults? How well can they recover from faults? Along with a thorough introduction into the area of fault tolerance, this book introduces a measure called 'limiting window availability' to answer such questions. Furthermore, a method for computing the 'limiting window availability' based on constructing the transition models from the system and environment models is developed. The method yet hinges on the transition model being exponential in the size of the constituting system models. This effect is commonly known as state space explosion. Combining decomposition and lumping - methods for reducing the state space from the domain of model checking - yet allows to dampen the state space explosion, thus enhancing the spectrum of systems that are tractable for an analysis significantly. <engl.>
Die zunehmende Verwendung verteilter Systeme im alltäglichen Leben für sicherheitskritische Anwendungen stellt besondere Anforderungen an deren Zuverlässigkeit. Stabilisierungstechniken werden in diesem Zusammenhang dazu genutzt, nicht-maskierende Fehlertoleranz einzuführen. Ein System ist selbststabilisierend genau dann, wenn, unabhängig vom initialen Zustand gewährleistet ist, dass das System mit endlich vielen Schritten den legalen Zustandsraum erreicht und diesen ohne Fremdeinwirkung nicht mehr verlässt. Obwohl Selbststabilisierung eine wünschenswerte Eigenschaft für verteilte Algorithmen ist, ist die Beweisbarkeit dieser Eigenschaft nicht trivial. Diese Dissertation befasst sich mit der Entwicklung eines kompositorischen Rahmens für den Entwurf selbststabilisierender verteilter Algorithmen. Die kompositorische Rahmen ausnutzt das Wissen der Ranking-Funktion, die verwendet werden, um die Konvergenz einer Komponente Algorithmus unter seiner ursprünglichen Scheduler zu beweisen. <dt.>
The proliferation of numerous computing devices in the various facets of life has remarkably elevated the premium placed on fault tolerance of the algorithms running on such devices. Self-stabilization is a novel method to provide non-masking fault tolerance. A distributed system is said to be self-stabilizing if and only if 1) it reaches a closed set of legal states in finite time, and 2) does not leave this set voluntarily. However, designing and proving convergence of a self-stabilizing system is not easy. We investigate whether the conditions under which component algorithms are self-stabilizing can be transcended while composing them. To that end, this dissertation presents a suite of compositional methods which can be used to compose self-stabilizing algorithms, though component algorithms themselves might be self-stabilizing under mutually incompatible conditions. <engl.>
HochschulschriftHybrides SystemAsymptotikStabilitätLjapunov-FunktionDekompositionWortbildungSubsystemFunktionInstabilitätKontinuierliches SystemDiskretes System
Hybride Systeme dienen der Beschreibung der Interaktion von zeitkontinuierlichem und zeitdiskretem Verhalten, wie sie beispielsweise in eingebetteten Systemen stattfindet. Ein Beschreibungsmittel für solche Systeme sind hybride Automatenmodelle, endliche Automaten angereichert mit Differentialgleichungen. Im Rahmen dieser Arbeit wird eine wichtige Eigenschaft solcher Systeme untersucht: Stabilität. Stabile Systeme sind in der Lage, temporäre Störungen auszuregeln, indem sie wieder zu einem Arbeitspunkt zurückkehren. Der Hauptbeitrag der Arbeit ist eine Methodik zum automatischen, dekompositionellen Nachweise dieser Eigenschaft. Den Kern bildet hier die graphentheoretische Zerlegung des Automaten mit Hilfe von Ljapunow-Funktionen, welche die Komponierbarkeit sicherstellen. Hiermit ist es möglich, die Komplexität der zu lösenden Stabilitätsbeweise signifikant zu reduzieren, sowie Aussagen über das Ergebnis einer Komposition zweier Automaten zu treffen. <dt.>
Hybrid systems describe the interaction between discrete time and continuous time behavior. For instance, they can be used to model the interactions between physics and digital controllers as they arise in embedded systems. One means for modeling such systems are so-called hybrid automata, consisting of finite automata enriched with differential equations. In the scope of this thesis, one important property of such systems is examined: stability. Stable systems compensate for temporary disturbances by returning to a pre-defined system state as soon as the disturbances cease. The main contribution of the thesis is a method for automated, decompositional stability verification, using graph theoretical methods and Lyapunov functions. The result is a divide-and-conquer approach that significantly reduces the complexity of the individual verification problems, and also can be used to predict the effects of a composition of two stable systems. <engl.>
Proceedings of UBICOMM 2011, The Fifth International Conference on Mobile Ubiquitous Computing, Systems, Services and Technologies, November 20-25, 2011 - Lisbon, Portugal s.l., 2011 (2011)
Auch als elektronisches Dokument verfügbar: http://www.offis.de/uploads/tx_useroffis/20110415032612_fina11.pdf
2011 IEEE workshops of International Conference on Advanced Information Networking and Applications (WAINA 2011) Piscataway, NJ : IEEE, 2011 (2011), Seite 21-27 LXXIII, 919 S.
Seite 7 von 11
