Verteilte Kommunikationssysteme haben in den letzten Jahren enorm an Bedeutung gewonnen, insbesondere durch die Vielzahl von Anwendungen in unserem Alltag. Die Heterogenität der Anwendungen und Anwendungsdomänen spricht für die Komplexität solcher Systeme und verdeutlicht die Herausforderungen, mit denen ihre Entwickler konfrontiert sind. Der Schwerpunkt dieser Arbeit liegt auf der Unterstützung des Entwicklungsprozesses von Anwendungen für verteilte Kommunikationssysteme. Es gibt zwei Aspekte, die dabei berücksichtigt werden müssen. Der erste und offensichtlichste ist die Unterstützung der Entwicklung der Anwendung selbst, die letztendlich auf der vorhandenen verteilten Kommunikationsinfrastruktur bereitgestellt werden soll. Der zweite weniger offensichtliche, aber genauso wichtige Aspekt besteht in der Analyse der Anwendung vor ihrer eigentlichen Installation. Anwendungsentwicklung und analyse sind also "zwei Seiten der gleichen Medaille". Durch die Berücksichtigung beider Aspekt erhöht sich jedoch andererseits der Aufwand bei der Entwicklung. Die Arbeit kombiniert und erweitert vorhandene Technologien entsprechend dem modellgetriebenen Entwicklungsparadigma zu einer einheitlichen Entwicklungsmethode. Die Eigenschaften der Anwendung werden in einer vereinheitlichten Beschreibung erfasst, welche sowohl die automatische Überführung in Installationen auf echten Infrastrukturen erlaubt, als auch die Analyse auf der Basis von Modellen. Darüber hinaus wird der Entwicklungsprozess mit zusätzlicher Unterstützung bei der Visualisierung der Analyse ergänzt. Die Praktikabilität des Ansatzes wird anschließend anhand der Entwicklung und Analyse einer Anwendung zur Erdbebenfrühwarnung unter Beweis gestellt. / Distributed communication systems have gained a substantial importance over the past years with a large set of examples of systems that are present in our everyday life. The heterogeneity of applications and application domains speaks for the complexity of such systems and the challenges that developers are faced with. The focus of this dissertation is on the development of applications for distributed communication systems. There are two aspects that need to be considered during application development. The first and most obvious is the development of the application itself that will be deployed on the existing distributed communication infrastructure. The second and less obvious, but equally important, is the analysis of the deployed application. Application development and analysis are like "two sides of the the same coin". However, the separation between the two increases the cost and effort required during the development process. Existing technologies are combined and extended following the model-driven development paradigm to obtain a unified development method. The properties of the application are captured in a unified description which drives automatic transformation for deployment on real infrastructures and/or analysis. Furthermore, the development process is complemented with additional support for visualization to aid analysis. The defined approach is then used in the development of an alarming application for earthquake early warning.

Das Erstellen von Unterrichtsentwürfen wird als Voraussetzung für effektiven, zielgerichteten Unterricht gesehen. Dies gilt insbesondere für angehende Lehrpersonen. Da viele Aspekte, wie z.B. Methoden, Fachinhalte, Standards und die Charakteristik der Lerngruppe, zur gleichen Zeit berücksichtigt und sinnvoll aufeinander abgestimmt werden müssen, handelt es sich um eine kreative und zugleich anspruchsvolle Aufgabe. Es liegt nahe, diesen aufwändigen Prozess der Planung durch spezialisierte Softwaresysteme zu unterstützen, die nicht nur Routineaufgaben erleichtern, sondern auch zur Reflexion anregen. Basierend auf einem Literatur-Review und Interviews mit Dozierenden, die Lehrpersonen ausbilden, werden Anforderungen an Unterrichtsentwürfe analysiert und diskutiert. Es werden dabei nicht nur die relevanten theoretischen Grundlagen betrachtet, sondern ebenfalls das Vorgehen bei der Planung, genutzte Hilfsmittel und besonders unterstützenswerte Aspekte aus der Praxis. Darauf aufbauend werden Anwendungsfälle und Anforderungen an ein Planungsunterstützungssystem systematisch abgeleitet. Existierende Planungssysteme werden vorgestellt und untersucht, wobei viele bereits elementare Anforderungen nicht erfüllen. Insbesondere gibt es kein System, das adaptives Feedback bereitstellt. Um diese Lücke zu schließen, wird eine graphische, zeitbasierte Notation zur Unterrichtsplanung vorgeschlagen. Weiterhin sind ein Ressourcen-Management, Analyse-Möglichkeiten und automatisches Feedback zentrale Bestandteile des Ansatzes. Der entwickelte Prototyp wurde mit über 100 Personen in mehreren Studien systematisch empirisch evaluiert. Im Fokus stand dabei nicht nur die Untersuchung der Gebrauchstauglichkeit des Ansatzes und des Prototyps, sondern auch wie sich die Nutzung des Prototyps auf die Qualität der Unterrichtsentwürfe auswirkt. Es wird aufgezeigt, dass der beschriebene Ansatz für die Planung von Unterricht geeignet ist und angehende Lehrpersonen auch zur Reflexion angeregt hat. / Developing a lesson plan is considered as a prerequisite for effective, targeted instruction. This is particularly true for prospective teachers. Since many aspects such as methods, subject content, standards, and the characteristics of the learner group have to be taken into account and reasonably compiled, it is a creative as well as a demanding task. It stands to reason that this complex process of planning can be supported by specialized software systems that do not only facilitate routine tasks, but also stimulate reflection. Based on a literature-review and interviews with instructors of prospective teachers, requirements for lesson plans are analyzed and discussed. Not only relevant theoretical principles of lesson planning are considered, but also individual planning steps, tools used and practical aspects that would benefit particularly from further support. Building upon this, use cases and requirements for a lesson planning support system are derived systematically. Existing planning systems are presented and analyzed. It is argued that many systems do not meet even basic requirements. Especially there is no system that offers adaptive feedback. In order to fill this gap, a graphical time-based representation is proposed for lesson planning. Further central aspects of this approach are resource management, analysis capabilities and automatic feedback. A software architecture for a planning support system is presented that implements the aforementioned approach and meets the requirements. The developed prototype was empirically evaluated in several systematic studies involving over 100 participants. The focus to study was the usability of the approach and the prototype on the one hand, and how the use of the prototype affects the quality of the lesson plans on the other hand. In this thesis it is shown that the described approach for lesson planning is adequate and suitable to promote reflective thinking about one''s own planning activities.

Diese Arbeit befasst sich mit der Entwicklung eines echtzeitfähigen Systems zur Erstellung von Tiefeninformation aus Stereobildpaaren, das in einer Reihe von Anwendungen zur dreidimensionalen Vermessung des Raumes herangezogen werden kann. Als Hauptanwendungsgebiete sind in erster Linie mobile Robotikapplikationen vorgesehen, die sehr strenge Anforderungen sowohl bezüglich des Ressourcenverbrauchs als auch im Hinblick auf die Messeigenschaften und das Laufzeitverhalten stellen. Ein Merkmal des in dieser Arbeit entworfenen Systems ist die in Echtzeit stattfindende Ausführung der verwendeten Algorithmen in Kombination mit sehr guten Messeigenschaften. Das verwendete Stereo-Matching-Verfahren basiert auf einem globalen Ansatz und liefert im Vergleich zu den alternativen echtzeitfähigen Methoden sehr gute Ergebnisse. Im Vordergrund steht dabei der Semi-Global-Matching-Algorithmus. Aufgrund der Komplexität globaler Ansätze finden in Echtzeitapplikationen nur lokale Stereo-Verfahren Verwendung. Lokale Verfahren liefern jedoch im Vergleich zu den globalen Methoden qualitativ schlechte Disparitätskarten. Ein neuer globaler Matching-Algorithmus Efficient-Semi-Global-Matching (eSGM) wird vorgestellt und in das Konzept für mobile Robotikanwendungen umgesetzt. Wegen der begrenzten Ressourcen der realen Hardware wurde eine Weiterentwicklung des eSGM-Algorithmus für die Realisierung genutzt. Abschließend wird das System anhand der drei Kerneigenschaften Laufzeit, Ressourcenverbrauch und Qualität der Tiefeninformation gegenüber den Verfahren nach dem Stand der Technik bewertet. Der in dieser Arbeit vorgestellte FPGA-Ansatz, die eingesetzte Entwurfsmethode und die vorgestellten Algorithmen ermöglichten es, ein leistungsfähiges Stereo-Bildverarbeitungssystem zu entwickeln, das den hohen Anforderungen bezüglich des Laufzeitverhaltens und der Qualität des Ergebnisses gerecht wird. / This work presents a realtime stereo image matching system that takes advantage of a global image matching method. The system is designed to provide depth information for mobile robotic applications. Typical tasks of the proposed system are to assist in obstacle avoidance, SLAM and path planning of mobile robots, that pose strong requirements on the size, energy consumption, reliability, frame rate and quality of the calculated depth map. Current available systems either rely on active sensors or on local stereo-image matching algorithms. The first are only suitable in controlled environments while the second suffer from low quality depth-maps. Top ranking quality results are only achieved by an iterative approach using global image matching and colour segmentation techniques which are computationally demanding and therefore difficult to be executed in real time. Attempts were made to still reach real-time performance with global methods by simplifying the routines but led to degraded depth maps which are at the end almost comparable with local methods. An equally named semi-global algorithm was proposed earlier, that shows both very good image matching results and relatively simple execution at the same time. A memory efficient variant of the Semi-Global Matching algorithm is presented and adopted for an implementation based on reconfigurable hardware that is suitable for real-time operations in the field of robotics. It will be shown that the modified version of the efficient Semi-Global matching method is delivering equivalent result compared to the original algorithm. The complete design has been implemented within a hardware development framework that is also reviewed.

Chipkarten sind ein fester Bestandteil unseres täglichen Lebens, das immer stärker von der Zuverlässigkeit derartiger Sicherheitssysteme abhängt, zum Beispiel Bezahlkarten, elektronische Gesundheitskarten oder Ausweisdokumente. Eine Sicherheitspolitik beschreibt die wichtigsten Sicherheitsziele und Sicherheitsfunktionen eines Systems und bildet die Grundlage für dessen zuverlässige Entwicklung. In der Arbeit konzentrieren wir uns auf multi-applikative Chipkartenbetriebssysteme und betrachten neue zusätzliche Sicherheitsziele, die dem Schutz der Kartenanwendungen dienen. Da die Qualität des Betriebssystems von der umgesetzten Sicherheitspolitik abhängt, ist deren Korrektheit von entscheidender Bedeutung. Mit einer Formalisierung können Zweideutigkeiten in der Interpretation ausgeschlossen und formale Beweistechniken angewendet werden. Bisherige formale Verifikationen von Sicherheitspolitiken beinhalten im allgemeinen den Nachweis von Safety-Eigenschaften. Wir verlangen zusätzlich die Betrachtung von Security-Eigenschaften, wobei aus heutiger Sicht beide Arten von Eigenschaften stets getrennt in unterschiedlichen Formalismen verifiziert werden. Die Arbeit stellt eine gemeinsame Spezifikations- und Verifikationsmethodik mit Hilfe von Observer-Modellen vor, die sowohl den Nachweis von Safety-Eigenschaften in einem TLA-Modell als auch den Nachweis von Security-Eigenschaften kryptografischer Protokolle in einem induktiven Modell erlaubt. Da wir alle Spezifikationen und Verifikationen im Werkzeug VSE-II durchführen, bietet das formale Modell der Sicherheitspolitik nicht nur einen abstrakten Blick auf das System, sondern dient gleichzeitig als abstrakte Systemspezifikation, die es in weiteren Entwicklungsschritten in VSE-II zu verfeinern gilt. Die vorgestellte Methodik der Integration beider Systemmodelle in VSE-II führt somit zu einer erhöhten und nachweisbaren Qualität von Sicherheitspolitiken und von Sicherheitssystemen. / Security systems that use smart cards are nowadays an important part of our daily life, which becomes increasingly dependent on the reliability of such systems, for example cash cards, electronic health cards or identification documents. Since a security policy states both the main security objectives and the security functions of a certain security system, it is the basis for the reliable system development. This work focuses on multi-applicative smart card operating systems and addresses new security objectives regarding the applications running on the card. As the quality of the operating system is determined by the underlying security policy, its correctness is of crucial importance. A formalization of it first provides an unambiguous interpretation and second allows for the analysis with mathematical precision. The formal verification of a security policy generally requires the verification of so-called safety properties; but in the proposed security policy we are additionally confronting security properties. At present, safety and security properties of formal system models are verified separately using different formalisms. In this work we first formalize a security policy in a TLA system specification to analyze safety properties and then separately verify security properties using an inductive model of cryptographic protocols. We provide a framework for combining both models with the help of an observer methodology. Since all specifications and proofs are performed with the tool VSE-II, the verified formal model of the security policy is not just an abstract view on the security system but becomes its high level specification, which shall be refined in further development steps also to be performed with the tool. Hence, the integration of the two approaches within the tool VSE-II leads to a new quality level of security policies and ultimately of the development of security systems.

Graphen sind in vielen Bereichen des Lebens zu finden, wobei wir speziell an Graphen in der Biologie interessiert sind. Knoten in solchen Graphen sind chemische Komponenten, Enzyme, Reaktionen oder Interaktionen, die durch Kanten miteinander verbunden sind. Eine effiziente Ausführung von Graphanfragen ist eine Herausforderung. In dieser Arbeit präsentieren wir GRIcano, ein System, das die effiziente Ausführung von Graphanfragen erlaubt. Wir nehmen an, dass Graphen in relationalen Datenbankmanagementsystemen (RDBMS) gespeichert sind. Als Graphanfragesprache schlagen wir eine erweiterte Version der Pathway Query Language (PQL) vor. Der Hauptbestandteil von GRIcano ist ein kostenbasierter Anfrageoptimierer. Diese Arbeit enthält Beiträge zu allen drei benötigten Komponenten des Optimierers, der relationalen Algebra, Implementierungen und Kostenmodellen. Die Operatoren der relationalen Algebra sind nicht ausreichend, um Graphanfragen auszudrücken. Daher stellen wir zuerst neue Operatoren vor. Wir schlagen den Erreichbarkeits-, Distanz-, Pfadlängen- und Pfadoperator vor. Zusätzlich geben wir Regeln für die Umformung von Ausdrücken an. Des Weiteren präsentieren wir Implementierungen für jeden vorgeschlagenen Operator. Der Hauptbeitrag ist GRIPP, eine Indexstruktur, die die effiziente Ausführung von Erreichbarkeitsanfragen auf sehr großen Graphen erlaubt. Wir zeigen, wie GRIPP und die rekursive Anfragestrategie genutzt werden können, um Implementierungen für alle Operatoren bereitzustellen. Die dritte Komponente von GRIcano ist das Kostenmodell, das Kardinalitätsabschätzungen der Operatoren und Kostenfunktionen für die Implementierungen benötigt. Basierend auf umfangreichen Experimenten schlagen wir in dieser Arbeit Funktionen dafür vor. Der neue Ansatz unserer Kostenmodelle ist, dass die Funktionen nur Kennzahlen der Graphen verwenden. Abschließend zeigen wir die Wirkungsweise von GRIcano durch Beispielanfragen auf echten biologischen Graphen. / Graphs occur in many areas of life. We are interested in graphs in biology, where nodes are chemical compounds, enzymes, reactions, or interactions that are connected by edges. Efficiently querying these graphs is a challenging task. In this thesis we present GRIcano, a system that efficiently executes graph queries. For GRIcano we assume that graphs are stored and queried using relational database management systems (RDBMS). We propose an extended version of the Pathway Query Language PQL to express graph queries. The core of GRIcano is a cost-based query optimizer. This thesis makes contributions to all three required components of the optimizer, the relational algebra, implementations, and cost model. Relational algebra operators alone are not sufficient to express graph queries. Thus, we first present new operators to rewrite PQL queries to algebra expressions. We propose the reachability, distance, path length, and path operator. In addition, we provide rewrite rules for the newly proposed operators in combination with standard relational algebra operators. Secondly, we present implementations for each proposed operator. The main contribution is GRIPP, an index structure that allows us to answer reachability queries on very large graphs. GRIPP has advantages over other existing index structures, which we review in this work. In addition, we show how to employ GRIPP and the recursive query strategy as implementation for all four proposed operators. The third component of GRIcano is the cost model, which requires cardinality estimates for operators and cost functions for implementations. Based on extensive experimental evaluation of our proposed algorithms we present functions to estimate the cardinality of operators and the cost of executing a query. The novelty of our approach is that these functions only use key figures of the graph. We finally present the effectiveness of GRIcano using exemplary graph queries on real biological networks.

Zufallsgraphen sind Graphen, die durch einen zufälligen Prozess erzeugt werden. Ein im Zusammenhang mit Zufallsgraphen häufig auftretendes Phänomen ist, dass sich die typischen Eigenschaften eines Graphen durch Hinzufügen einer relativ kleinen Anzahl von zufälligen Kanten radikal verändern. Wir betrachten den Zufallsgraphen G(n,p), der n Knoten enthält und in dem zwei Knoten unabhängig und mit Wahrscheinlichkeit p durch eine Kante verbunden sind. Erdös und Rényi zeigten, dass ein Graph für p = c/n und c < 1 mit hoher Wahrscheinlichkeit aus Komponenten mit O(log n) Knoten besteht. Für p = c/n und c > 1 enthält G(n,p) mit hoher Wahrscheinlichkeit genau eine Komponente mit Theta(n) Knoten, welche viel größer als alle anderen Komponenten ist. Dieser Punkt in der Entwicklung des Graphen, an dem sich die Komponentenstruktur durch eine kleine Erhöhung der Anzahl von Kanten stark verändert, wird Phasenübergang genannt. Wenn p = (1+epsilon)/n, wobei epsilon eine Funktion von n ist, die gegen 0 geht, sind wir in der kritischen Phase, welche eine der interessantesten Phasen der Entwicklung des Zufallsgraphen ist. In dieser Arbeit betrachten wir drei verschiedene Modelle von Zufallsgraphen. In Kapitel 4 studieren wir den Minimalgrad-Graphenprozess. In diesem Prozess werden sukzessive Kanten vw hinzugefügt, wobei v ein zuällig ausgewählter Knoten von minimalem Grad ist. Wir beweisen, dass es in diesem Graphenprozess einen Phasenübergang, und wie im G(n,p) einen Doppelsprung, gibt. Die zwei anderen Modelle sind Zufallsgraphen mit einer vorgeschriebenen Gradfolge und zufällige gerichtete Graphen. Für diese Modelle wurde bereits in den Arbeiten von Molloy und Reed (1995), Karp (1990) und Luczak (1990) gezeigt, dass es einen Phasenübergang bezüglich der Komponentenstruktur gibt. In dieser Arbeit untersuchen wir in Kapitel 5 und 6 die kritische Phase dieser Prozesse genauer, und zeigen, dass sich diese Modelle ähnlich zum G(n,p) verhalten. / Random graphs are graphs which are created by a random process. A common phenomenon in random graphs is that the typical properties of a graph change radically by the addition of a relatively small number of random edges. This phenomenon was first investigated in the seminal papers of Erdös and Rényi. We consider the graph G(n,p) which contains n vertices, and where any two vertices are connected by an edge independently with probability p. Erdös and Rényi showed that if p = c/n$ and c < 1, then with high probability G(n,p) consists of components with O(log n) vertices. If p = c/n$ and c>1, then with high probability G(n,p) contains exactly one component, called the giant component, with Theta(n) vertices, which is much larger than all other components. The point at which the giant component is formed is called the phase transition. If we let $p = (1+epsilon)/n$, where epsilon is a function of n tending to 0, we are in the critical phase of the random graph, which is one of the most interesting phases in the evolution of the random graph. In this case the structure depends on how fast epsilon tends to 0. In this dissertation we consider three different random graph models. In Chapter 4 we consider the so-called minimum degree graph process. In this process edges vw are added successively, where v is a randomly chosen vertex with minimum degree. We prove that a phase transition occurs in this graph process as well, and also that it undergoes a double jump, similar to G(n,p). The two other models we will consider, are random graphs with a given degree sequence and random directed graphs. In these models the point of the phase transition has already been found, by Molloy and Reed (1995), Karp (1990) and Luczak (1990). In Chapter 5 and 6 we investigate the critical phase of these processes, and show that their behaviour resembles G(n,p).

Flugzeug- und satellitengestützte Zeilenkameras ermöglichen eine sehr ökonomische Aufnahme von hoch aufgelösten Luftbildern mit großer Schwadbreite. Eine ungleichförmige Bewegung der Kamera kann sich auf die Bildqualität auswirken. Deswegen ist es unerlässlich, schnelle Orientierungsänderungen der Kamera mit angemessener Genauigkeit und Messrate zu erfassen. Deshalb ist es unerlässlich, die Orientierung der Kamera genau zu messen, um sicher zu stellen, dass die resultierenden Bilder in einem Nachbearbeitungsschritt geometrisch korrigiert werden können. Angemessene High-End-Navigationssysteme sind groß und teuer und ihre Genauigkeit und Messrate dennoch für viele denkbare Anwendungen unzureichend. Aus diesen Gründen besteht ein großes Interesse an Methoden zur Unterstützung der Orientierungsmessung durch die Nutzung optischer Informationen vom Hauptobjektiv bzw. Teleskop. In dieser Arbeit werden zwei unterschiedliche Verfahren vorgestellt, die es erlauben, schnelle Orientierungsänderungen der Kamera auf optischem Wege zu ermitteln. Ersteres basiert auf zusätzlichen Bildsensoren mit kleiner Fläche. Der optische Fluss auf diesen Bildsensoren wird ermittelt und zur Bestimmung von Orientierungsänderungen beliebiger Fernerkundungssysteme verwendet. Das zweite Verfahren beruht ausschließlich auf den Inhalten der Zeilenbilder und der gemessenen Kameratrajektorie. Hierfür macht sich das Verfahren die typische Geometrie multispektraler Zeilenkameras zu Nutze. Zunächst werden homologe Punkte in den möglicherweise stark verzerrten Zeilenbildern unterschiedlicher Spektralbänder extrahiert. Diese Punkte werden dann dazu benutzt, die Orientierungsänderungen der Kamera zu ermitteln. Schließlich wird gezeigt, dass es möglich ist, die absolute Orientierung einer luftgestützten Zeilenkamera anhand der optisch ermittelten Orientierungsänderungen hochgenau zu ermitteln. / Airborne and spaceborne line cameras allow a very economic acquisition of high resolution and wide swath images of the Earth. They generate two-dimensional images while rotating or translating, which causes a non-rigid image geometry. Nonuniform motion of the camera can negatively affect the image quality. Due to this, a key requirement for line cameras is that fast orientation changes have to be measured with a very high rate and precision. Therefore, it is essential to measure the camera’s orientation accurately to ensure that the resulting imagery products can be geometrically corrected in a later processing step. Adequate high-end measurement systems are large and expensive and their angular and temporal resolution can be still too low for many possible applications. Due to these reasons there is great interest in approaches to support the orientation measurement by using optical information received through the main optics or telescope. In this thesis two different approaches are presented that allow the determination of a line camera’s orientation changes optically. One approach to determine fast orientation changes is based on small auxiliary frame image sensors. The optical flow on these sensors is determined and used to derive orientation changes of any remote sensing system. The second approach does not require any additional sensors to determine orientation changes. It relies only on the images of a line camera and a rough estimate of its trajectory by taking advantage of the typical geometry of multi-spectral line cameras. In a first step homologous points are detected within the distorted images of different spectral bands. These points are used to calculate the orientation changes of the camera with a high temporal and angular resolution via bundle adjustment. Finally it is shown how the absolute exterior orientation of an airborne line camera can completely be derived from the optically determined orientation changes.

Verlässliche Dienstbereitstellung ist eines der wichtigsten Ziele in modernen Netzwerken. Da Anbieter und Nutzer Teil einer Informations und Kommunikationstechnologie (IKT) Infrastruktur sind, wird die Verlässlichkeit der Dienste je nach Position der Aktoren variieren, so wie sich die für die Bereitstellung nötigen IKT Geräte ändern. Wir stellen zwei Ansätze zur Quantifizierung nutzerspezifischer Dienstverlässlichkeit vor. Der erste, modellgetriebene Ansatz berechnet momentane Dienstverfügbarkeit. Aus Modellen des Dienstes, der Infrastruktur und einer Abbildung zwischen den beiden, welche die Aktoren der Dienstkommunikation beschreibt, werden durch eine Serie von Modelltransformationen automatisiert Verfügbarkeitsmodelle generiert. Die Realisierbarkeit des Ansatzes wird anhand von Diensten im Netzwerk der Universität Lugano, Schweiz, gezeigt. Der zweite Ansatz behandelt die Responsivität der Dienstfindung, die Wahrscheinlichkeit innerhalb einer Frist Dienstinstanzen zu finden, unter der Annahme von Fehlern. Dies stellt den Hauptteil dieser Arbeit dar. Eine Hierarchie stochastischer Modelle wird vorgestellt, die nutzerspezifische Responsivität auf Basis von Messdaten der Routingebene berechnet. Umfangreiche Experimente wurden im Distributed Embedded Systems (DES) Funktestbett der Freien Universität Berlin durchgefürt. Diese zeigen Probleme aktueller Dienstfindungsprotokolle in modernen, dynamischen Netzwerken. Gleichzeitig dienen sie der Validierung der vorgestellten Modelle. Beide Ansätze zeigen, daß die Verlässlichkeit der Dienstbereitstellung in der Tat deutlich mit der Position von Nutzern und Anbietern variiert, sogar in hochverfügbaren Kabelnetzwerken. Die Ansätze ermöglichen die Optimierung von Dienstnetzwerken anhand bekannter oder erwarteter Nutzungsmuster. Zudem antizipieren sie neuartige Verlässlichkeitsmodelle, welche Dienstfindung, zeitige Bereitstellung, Platzierung und Nutzung kombinieren; Gebiete, die bisher im Allgemeinen getrennt behandelt wurden. / Dependability of service provision is one of the primary goals in modern networks. Since providers and clients are part of a connecting Information and Communications Technology (ICT) infrastructure, service dependability varies with the position of actors as the ICT devices needed for service provision change. We present two approaches to quantify user-perceived service dependability. The first is a model-driven approach to calculate instantaneous service availability. Using input models of the service, the infrastructure and a mapping between the two to describe actors of service communication, availability models are automatically created by a series of model to model transformations. The feasibility of the approach is demonstrated using exemplary services in the network of University of Lugano, Switzerland. The second approach aims at the responsiveness of the service discovery layer, the probability to find service instances within a deadline even in the presence of faults, and is the main part of this thesis. We present a hierarchy of stochastic models to calculate user-perceived responsiveness based on monitoring data from the routing layer. Extensive series of experiments have been run on the Distributed Embedded Systems (DES) wireless testbed at Freie Universität Berlin. They serve both to demonstrate the shortcomings of current discovery protocols in modern dynamic networks and to validate the presented stochastic models. Both approaches demonstrate that the dependability of service provision indeed differs considerably depending on the position of service clients and providers, even in highly reliable wired networks. The two approaches enable optimization of service networks with respect to known or predicted usage patterns. Furthermore, they anticipate novel service dependability models which combine service discovery, timeliness, placement and usage, areas that until now have been treated to a large extent separately.

Die vorliegende Dissertation beinhaltet eine umfassende Untersuchung der Entscheidbarkeit und Komplexität der Probleme, die sich durch eine statische Analyse von monadischem Datalog auf endlichen gefärbten Bäumen stellen. Statische Analyse bedeutet hierbei Anfrageoptimierung ohne Blick auf konkrete Instanzen, aber mit Rücksicht auf deren zugrunde liegende Struktur. Im Kern beinhaltet dies die Lösung der drei folgenden Probleme: das Leerheitsproblem (die Frage, ob eine Anfrage auf jeder Instanz ein leeres Ergebnis liefert), das Äquivalenzproblem (die Frage, ob zwei Anfragen auf jeder Instanz das gleiche Ergebnis liefern) und das Query-Containment-Problem (die Frage, ob das Ergebnis der einen Anfrage auf jeder Datenbank im Ergebnis der anderen Anfrage enthalten ist). Von Interesse ist dabei, ob die Fragen für eine gegebene Anfragesprache entscheidbar sind und wenn ja, welche Komplexität ihnen innewohnt. Wir betrachten diese Probleme für monadisches Datalog auf unterschiedlichen Repräsentationen für endliche gefärbte Bäume. Hierbei unterscheiden wir zwischen ungeordneten und geordneten Bäumen, welche die Achsen child bzw. firstchild und nextsibling und deren Erweiterung um die descendant-Achse nutzen. Außerdem unterscheiden wir Alphabete mit und ohne Rang. Monadisches Datalog ist eine Anfragesprache, die in Abhängigkeit vom gewählten Schema die Ausdrucksstärke der monadischen Logik zweiter Stufe (MSO) erreicht und dennoch effizient ausgewertet werden kann. Wir zeigen, dass unter in der Datenbanktheorie üblichen Mengensemantik die drei genannten Probleme für alle Schemata ohne descendant-Achse EXPTIME-vollständig sind und lösbar in 2EXPTIME, falls die descendant-Achse involviert ist. Eine passende untere Schranke wird für fast alle Schemata gezeigt. Unter Multimengensemantik lassen sich die obigen Ergebnisse für das Leerheitsproblem übertragen, während das Query-Containment-Problem für alle betrachteten Schemata unentscheidbar ist. / This thesis provides a comprehensive investigation into the decidability and complexity of the fundamental problems entailed by static analysis of monadic datalog on finite labeled trees. Static analysis is used for optimizing queries without considering concrete database instances but exploiting information about the represented structure. Static analysis relies on three basic decision problems. First, the emptiness problem, whose task is to decide whether a query returns the empty result on every database. Second, the equivalence problem asking if the result of two given queries always coincides on every database. And finally, the query containment problem where it is to decide whether on every database a given query produces a subset of the results of a second given query. We are interested in finding out whether these problems are decidable and, if so, what their complexity is. We consider the aforementioned problems for monadic datalog on different representations of finite labeled trees. We distinguish unordered and ordered trees which use the axis child, as well as the axes firstchild and nextsibling, respectively. An extension of the schemas by the descendant-axis is also considered. Furthermore, we distinguish ranked and unranked labeling alphabets. Depending on the schema, the query language monadic datalog can reach the expressive power of monadic second order logic but remains efficiently evaluable. Under set semantics, we show EXPTIME-completness for all used schemas where the descendant-axis is omitted. If the descendant-axis is involved, we present an algorithm that solves the problem within 2-fold exponential time. A matching lower bound is proven for virtually all schemas. Finally, we prove that the complexity of the emptiness problem of monadic datalog on finite trees under bag semantics is the same as under set semantics. Furthermore, we show that the query containment problem of monadic datalog under bag semantics is undecidable in general.

Die vorliegende Dissertation besteht aus zwei Teilen, deren gemeinsames Thema in der Frage besteht, wie mächtig Zufall als Berechnungsressource ist. Im ersten Teil beschäftigen wir uns mit zufälligen Strukturen, die -- mit hoher Wahrscheinlichkeit -- Eigenschaften haben können, die von Computeralgorithmen genutzt werden können. In zwei konkreten Fällen geben wir bis dahin unbekannte deterministische Konstruktionen solcher Strukturen: Wir derandomisieren eine randomisierte Reduktion von Alekhnovich und Razborov, indem wir bestimmte unbalancierte bipartite Expandergraphen konstruieren, und wir geben eine Reduktion von einem Problem über bipartite Graphen auf das Problem, den minmax-Wert in Dreipersonenspielen zu berechnen. Im zweiten Teil untersuchen wir die Ausdrucksstärke verschiedener Logiken, wenn sie durch zufällige Relationssymbole angereichert werden. Unser Ziel ist es, Techniken aus der deskriptiven Komplexitätstheorie für die Untersuchung randomisierter Komplexitätsklassen nutzbar zu machen, und tatsächlich können wir zeigen, dass unsere randomisierten Logiken randomisierte Komlexitätsklassen einfangen, die in der Komplexitätstheorie untersucht werden. Unter Benutzung starker Ergebnisse über die Logik erster Stufe und die Berechnungsstärke von Schaltkreisen beschränkter Tiefe geben wir sowohl positive als auch negative Derandomisierungsergebnisse für unsere Logiken. Auf der negativen Seite zeigen wir, dass randomisierte erststufige Logik gegenüber normaler erststufiger Logik an Ausdrucksstärke gewinnt, sogar auf Strukturen mit einer eingebauten Additionsrelation. Außerdem ist sie nicht auf geordneten Strukturen in monadischer zweitstufiger Logik enthalten, und auch nicht in infinitärer Zähllogik auf beliebigen Strukturen. Auf der positiven Seite zeigen wir, dass randomisierte erststufige Logik auf Strukturen mit einem unären Vokabular derandomisiert werden kann und auf additiven Strukturen in monadischer Logik zweiter Stufe enthalten ist. / This thesis is comprised of two main parts whose common theme is the question of how powerful randomness as a computational resource is. In the first part we deal with random structures which possess -- with high probability -- properties than can be exploited by computer algorithms. We then give two new deterministic constructions for such structures: We derandomise a randomised reduction due to Alekhnovich and Razborov by constructing certain unbalanced bipartite expander graphs, and we give a reduction from a problem concerning bipartite graphs to the problem of computing the minmax-value in three-player games. In the second part we study the expressive power of various logics when they are enriched by random relation symbols. Our goal is to bridge techniques from descriptive complexity with the study of randomised complexity classes, and indeed we show that our randomised logics do capture complexity classes under study in complexity theory. Using strong results on the expressive power of first-order logic and the computational power of bounded-depth circuits, we give both positive and negative derandomisation results for our logics. On the negative side, we show that randomised first-order logic gains expressive power over standard first-order logic even on structures with a built-in addition relation. Furthermore, it is not contained in monadic second-order logic on ordered structures, nor in infinitary counting logic on arbitrary structures. On the positive side, we show that randomised first-order logic can be derandomised on structures with a unary vocabulary and is contained in monadic second-order logic on additive structures.