In dieser Arbeit wird die Möglichkeit der Unterstützung des Hardwareentwurfs mit VHDL durch ein Hardwarebetriebssystem untersucht. Durch die Wiederverwendung von Betriebssystemmodulen sollen die Entwicklungszeit verkürzt, die Nachnutzbarkeit von Entwürfen verbessert und die Zuverlässigkeit erhöht werden. Um ein Betriebssystemkonzept umzusetzen, müssen spezielle Anforderungen an die Programmiersprache gestellt werden. Diese werden von VHDL nicht erfüllt. Daher wird ein Strukturcompiler vorgestellt, der unter Beibehaltung der Syntax der Sprache VHDL den zusätzlichen Anforderungen gerecht wird. Der Strukturcompiler verbindet das Anwendungsprogramm mit den Betriebssystemmodulen und erzeugt daraus ein VHDL-Programm, das mit den typischen FPGA-Entwicklungswerkzeugen simuliert oder synthetisiert werden kann. Bei der Entwicklung des Betriebssystems für konfigurierbare Hardware hat sich herausgestellt, dass sich dieses nur eingebettet in ein Gesamtkonzept für den Entwurf von heterogene Systeme sinnvoll anwenden lässt. Deshalb wird in dieser Arbeit eine Methode für die Entwicklung von heterogenen Systemen auf Basis eines Signalflussgraphen diskutiert. Angewendet wurde das Betriebssystemkonzept auf verschiedenen FPGA-Karten, sowohl käuflich erworbene als auch Eigenentwicklungen. Das für diese Karten erstellte Betriebssystem umfasst dabei Module zur Kommunikation zwischen FPGA und PC sowie zur Anbindung verschiedener externer Peripheriegeräte, wie z.B. Speicher. Es wurde ebenfalls untersucht wie Prozessoren als Bestandteil der konfigurierbaren Hardware in das Betriebssystemkonzept integriert werden können. Im Rahmen dieser Arbeit wurden auch viele Beispielanwendungen untersucht. Diese wurden einerseits zum Testen des Strukturcompilers und der Betriebssystemmodule benutzt. Andererseits fand das Betriebssystemkonzept für konfigurierbare Hardware auch Anwendung in verschiedenen Projekten. / This work investigates the possibility of describing a hardware design independent of special hardware. This is realized with the concept of an operating system. The re-use of operating system modules reduces the time of development and also increases the reliability. Additionally, the change of a development platform has no influence on the application algorithm anymore. In order to apply the concept of an operating system special constraints have to be fulfilled by the hardware description language, which is not supported by VHDL. For that reason a structure compiler has been developed. The structure compiler connects the application program with the operating system modules and produces a VHDL program, which can be used to simulate or to program the FPGA with the typical VHDL development tools. In the progress of developing the operating system concept for reconfigurable hardware it was realized that such a concept can only be used in connection with a design methodology for heterogeneous systems. In this work a design methodology based on a declarative language represented as signal flow graph is discussed. The operating system concept for reconfigurable hardware was tested on different FPGA boards. For these cards an operating system was developed. The operating system contains modules for the communication with the PC over different interfaces as well as modules for accessing different exterior peripheries, i.e. memory. Additionally, the integration of processors as part of the configurable hardware within the operating system concept was investigated. For the verification of the structure compiler and the operating system modules some examples have been developed. The operating system concept for configurable hardware was also applied in different projects.

Diese Arbeit untersucht den Einfluss von Daten auf das Verhalten und die Korrektheit eines verteilten Systems. Ein verteiltes System besteht aus mehreren Services. Ein Service ist eine selbständige, plattformunabhängige Einheit, die anderen Services eine bestimmte Funktionalität über eine wohldefinierte Schnittstelle zur Verfügung stellt. In dieser Arbeit betrachten wir die Interaktion von jeweils genau zwei Services miteinander. Zwei Services, die erfolgreich miteinander zusammenarbeiten können, nennen wir Partner. Ein Service heißt bedienbar, wenn er mindestens einen Partner hat. Ziel der Arbeit ist es, zu untersuchen, wann zwei Services Partner sind, und für einen Service zu entscheiden, ob dieser bedienbar ist. Aufgrund der Daten kann der Zustandsraum eines Service sehr groß oder sogar unendlich groß werden. Wir untersuchen zwei Klassen von Services mit unendlich vielen Zuständen. Für diese Klassen stellen wir Algorithmen vor, welche zu einem gegebenen Service einen Partner synthetisieren, falls ein solcher existiert. Auf diese Weise entscheiden wir konstruktiv die Bedienbarkeit eines Service. Weiterhin stellen wir Transformationsregeln für Partner vor und untersuchen, wie viel Speicherplatz ein Partner eines Services mindestens benötigt. / This thesis studies the influence of data on the behavior and the correctness of a distributed system. A distributed system consists of several services. A service is a self-contained, platform-independent entity which provides a certain functionality to other services via a well-defined interface.In this thesis, we consider the interaction of exactly two services. Two services that can successfully cooperate with each other are called partners. We call a service controllable, if the service has at least one partner. The goal of this thesis is to study the conditions for which two services are partners and to decide whether a given service is controllable. Due to the data, the state space of a service may be very large or even infinite. We investigate two classes of services with infinitely many states. For these classes, we present algorithms that synthesize a partner of a service, if it exists. This allows us to decide the controllability of a service constructively. Furthermore, we present transformation rules for partners and investigate the minimum amount of memory that a partner of a service needs.

Fairneß (d.h. faire Konfliktlösung), Randomisierung (d.h. Münzwürfe) und partielle Synchronie sind verschiedene Konzepte, die häufig zur Lösung zentraler Synchronisations- und Koordinationsprobleme in verteilten Systemen verwendet werden. Beispiele für solche Probleme sind das Problem des wechselseitigen Ausschlusses (kurz: Mutex-Problem) sowie das Konsens-Problem. Für einige solcher Probleme wurde bewiesen, daß ohne die oben genannten Konzepte keine Lösung für das betrachtete Problem existiert. Unmöglichkeitsresultate dieser Art verbessern unser Verständnis der Wirkungsweise verteilter Algorithmen sowie das Verständnis des Trade-offs zwischen einem leicht analysierbaren und einem ausdrucksstarken Modell für verteiltes Rechnen. In dieser Arbeit stellen wir zwei neue Unmöglichkeitsresultate vor. Darüberhinaus beleuchten wir ihre Hintergründe. Wir betrachten dabei Modelle, die Randomisierung einbeziehen, da bisher wenig über die Grenzen der Ausdrucksstärke von Randomisierung bekannt ist. Mit einer Lösung eines Problems durch Randomisierung meinen wir, daß das betrachtete Problem mit Wahrscheinlichkeit 1 gelöst wird. Im ersten Teil der Arbeit untersuchen wir die Beziehung von Fairneß und Randomisierung. Einerseits ist bekannt, daß einige Probleme (z.B. das Konsens- Problem) durch Randomisierung nicht aber durch Fairneß lösbar sind. Wir zeigen nun, daß es andererseits auch Probleme gibt (nämlich das Mutex-Problem), die durch Fairneß, nicht aber durch Randomisierung lösbar sind. Daraus folgt, daß Fairneß nicht durch Randomisierung implementiert werden kann. Im zweiten Teil der Arbeit verwenden wir ein Modell, das Fairneß und Randomisierung vereint. Ein solches Modell ist relativ ausdrucksstark: Es erlaubt Lösungen für das Mutex-Problem, das Konsens-Problem, sowie eine Lösung für das allgemeine Mutex-Problem. Beim allgemeinen Mutex-Problem (auch bekannt als Problem der speisenden Philosophen) ist eine Nachbarschaftsrelation auf den Agenten gegeben und ein Algorithmus gesucht, der das Mutex-Problem für jedes Paar von Nachbarn simultan löst. Schließlich betrachten wir das ausfalltolerante allgemeine Mutex-Problem -- eine Variante des allgemeinen Mutex-Problems, bei der Agenten ausfallen können. Wir zeigen, daß sogar die Verbindung von Fairneß und Randomisierung nicht genügt, um eine Lösung für das ausfalltolerante allgemeine Mutex-Problem zu konstruieren. Ein Hintergrund für dieses Unmöglichkeitsresultat ist ein unerwünschtes Phänomen, für das in der Literatur der Begriff Konspiration geprägt wurde. Konspiration wurde bisher nicht adäquat charakterisiert. Wir charakterisieren Konspiration auf der Grundlage nicht-sequentieller Abläufe. Desweiteren zeigen wir, daß Konspiration für eine große Klasse von Systemen durch die zusätzliche Annahme von partieller Synchronie verhindert werden kann, d.h. ein konspirationsbehaftetes System kann zu einem randomisierten System verfeinert werden, das unter Fairneß und partieller Synchronie mit Wahrscheinlichkeit 1 konspirationsfrei ist. Partielle Synchronie fordert, daß alle relativen Geschwindigkeiten im System durch eine Konstante beschränkt sind, die jedoch den Agenten nicht bekannt ist. Die Darstellung der Unmöglichkeitsresultate und die Charakterisierung von Konspiration wird erst durch die Verwendung nicht-sequentieller Abläufe möglich. Ein nicht-sequentieller Ablauf repräsentiert im Gegensatz zu einem sequentiellen Ablauf kausale Ordnung und nicht zeitliche Ordnung von Ereignissen. Wir entwickeln in dieser Arbeit eine nicht-sequentielle Semantik für randomisierte verteilte Algorithmen, da es bisher keine in der Literatur gibt. In dieser Semantik wird kausale Unabhängigkeit durch stochastische Unabhängigkeit widergespiegelt. / Concepts such as fairness (i.e., fair conflict resolution), randomization (i.e., coin flips), and partial synchrony are frequently used to solve fundamental synchronization- and coordination-problems in distributed systems such as the mutual exclusion problem (mutex problem for short) and the consensus problem. For some problems it is proven that, without such concepts, no solution to the particular problem exists. Impossibilty results of that kind improve our understanding of the way distributed algorithms work. They also improve our understanding of the trade-off between a tractable model and a powerful model of distributed computation. In this thesis, we prove two new impossibility results and we investigate their reasons. We are in particular concerned with models for randomized distributed algorithms since little is yet known about the limitations of randomization with respect to the solvability of problems in distributed systems. By a solution through randomization we mean that the problem under consideration is solved with probability 1. In the first part of the thesis, we investigate the relationship between fairness and randomization. On the one hand, it is known that to some problems (e.g. to the consensus problem), randomization admits a solution where fairness does not admit a solution. On the other hand, we show that there are problems (viz. the mutex problem) to which randomization does not admit a solution where fairness does admit a solution. These results imply that fairness cannot be implemented by coin flips. In the second part of the thesis, we consider a model which combines fairness and randomization. Such a model is quite powerful, allowing solutions to the mutex problem, the consensus problem, and a solution to the generalized mutex problem. In the generalized mutex problem (a.k.a. the dining philosophers problem), a neighborhood relation is given and mutual exclusion must be achieved for each pair of neighbors. We finally consider the crash-tolerant generalized mutex problem where every hungry agent eventually becomes critical provided that neither itself nor one of its neighbors crashes. We prove that even the combination of fairness and randomization does not admit a solution to the crash-tolerant generalized mutex problem. We argue that the reason for this impossibility is the inherent occurrence of an undesirable phenomenon known as conspiracy. Conspiracy was not yet properly characterized. We characterize conspiracy on the basis of non-sequential runs, and we show that conspiracy can be prevented by help of the additional assumption of partial synchrony, i.e., we show that every conspiracy-prone system can be refined to a randomized system which is, with probability 1, conspiracy-free under the assumptions of partial synchrony and fairness. Partial synchrony means that each event consumes a bounded amount of time where, however, the bound is not known. We use a non-sequential semantics for distributed algorithms which is essential to some parts of the thesis. In particular, we develop a non-sequential semantics for randomized distributed algorithms since there is no such semantics in the literature. In this non-sequential semantics, causal independence is reflected by stochastic independence.

In der Ramsey Theorie fuer Graphen haben Burr und Erdos vor nunmehr fast dreissig Jahren zwei Vermutungen formuliert, die sich als richtungsweisend erwiesen haben. Es geht darum diejenigen Graphen zu charakterisieren, deren Ramsey Zahlen linear in der Anzahl der Knoten wachsen. Diese Vermutungen besagen, dass Ramsey Zahlen linear fuer alle degenerierten Graphen wachsen und dass die Ramsey Zahlen von Wuerfeln linear wachsen. Ein Ziel dieser Dissertation ist es, abgeschwaechte Varianten dieser Vermutungen zu beweisen. In der topologischen Ramseytheorie bewies Kojman vor kurzem eine topologische Umkehrung des Satzes von Hindman und fuehrte gleichzeitig sogenannte Hindman-Raeume und van der Waerden-Raeume ein (beide sind eine Teilmenge der folgenkompakten Raeume), die jeweils zum Satz von Hindman beziehungsweise zum Satz von van der Waerden korrespondieren. In der Dissertation wird zum einen eine Verstaerkung der Umkehrung des Satzes von van der Waerden bewiesen. Weiterhin wird der Begriff der Differentialkompaktheit eingefuehrt, der sich in diesem Zusammenhang ergibt und der eng mit Hindman-Raeumen verknuepft ist. Dabei wird auch die Beziehung zwischen Differentialkompaktheit und anderen topologischen Raeumen untersucht. Im letzten Abschnitt des zweiten Teils werden kompakte dynamische Systeme verwendet, um ein klassisches Ramsey-Ergebnis von Brown und Hindman et al. ueber stueckweise syndetische Mengen ueber natuerlichen Zahlen und diskreten Halbgruppen auf lokal zusammenhaengende Halbgruppen zu verallgemeinern. / In graph Ramsey theory, Burr and Erdos in 1970s posed two conjectures which may be considered as initial steps toward the problem of characterizing the set of graphs for which Ramsey numbers grow linearly in their orders. One conjecture is that Ramsey numbers grow linearly for all degenerate graphs and the other is that Ramsey numbers grow linearly for cubes. Though unable to settle these two conjectures, we have contributed many weaker versions that support the likely truth of the first conjecture and obtained a polynomial upper bound for the Ramsey numbers of cubes that considerably improves all previous bounds and comes close to the linear bound in the second conjecture. In topological Ramsey theory, Kojman recently observed a topological converse of Hindman's theorem and then introduced the so-called Hindman space and van der Waerden space (both of which are stronger than sequentially compact spaces) corresponding respectively to Hindman's theorem and van der Waerden's theorem. In this thesis, we will strengthen the topological converse of Hindman's theorem by using canonical Ramsey theorem, and introduce differential compactness that arises naturally in this context and study its relations to other spaces as well. Also by using compact dynamical systems, we will extend a classical Ramsey type theorem of Brown and Hindman et al on piecewise syndetic sets from natural numbers and discrete semigroups to locally connected semigroups.

Dienstorientierte Architekturen (SOA = Service Oriented Architecture) dienen dem Aufbau von lose miteinander verbundenen, verteilten Systemen, deren Komponenten eine minimale gemeinsame Systemsicht haben. Die wichtigsten Bausteine der SOA sind Dienste. Dienste sind selbstbeschreibende, eigenständige, plattform-unabhängige und frei verfügbare Komponenten, die über das Netzwerk interagieren. Das Hauptziel der SOA ist die transparente, flexible und dynamische Interaktion von Diensten und deren Benutzern innerhalb mehrerer zusammenhängender Domänen. Während die nativen Fähigkeiten von dienstorientierten Architekturen, wie Beschreibung, Entdeckung, Kommunikation und Bindung, bereits gut erfasst und standardisiert worden sind, ist das Problem der Dienstkomposition bisher noch nicht zufriedenstellend gelöst worden. Diese Dissertation hinterfragt die Grundvoraussetzung der SOA, die darin besteht, dass lediglich die Grundfunktionsweise von Diensten offen gelegt werden sollte, und demonstriert, dass auf der Grundlage einer semantischen Dienstbeschreibung (einschließlich funktionaler und nichtfunktionaler Eigenschaften) eine praktikable Lösung zur Dienstkomposition entwickelt werden kann (komponierbare Dienstarchitektur). Diese Lösung erfordert 1) erweiterte deskriptive Fähigkeiten und Suchmöglichkeiten durch die Entwicklung einer vertragsbasierten Beschreibungssprache einschließlich nichtfunktionaler Eigenschaften wie Sicherheit, Verlässlichkeit und Rechtzeitigkeit; 2) das Feststellen der Kompositionskorrektheit durch die Modellierung von Diensten als abstrakte Maschinen und die Entwicklung einer formalen Kompositionssprache und 3) automatische Dienstkomposition, indem Suchalgorithmen für die automatisierte und dynamische Selektion von Kompositionspartnern entwickelt werden. Abschließend wird der Prototyp eines Kompositionsservers für Web Services einschließlich Design und Implementierung beschrieben, um die Realisierbarkeit der vorgeschlagenen Architektur aufzuzeigen. / Service-oriented architecture (SOA) is focused on building loosely coupled distributed systems with minimal shared understanding among system components. The main building blocks in SOA are services. Services are self-descriptive, self-contained, platform-independent and openly-available components that interact over the network. The main goal of SOA is transparent, flexible and dynamic interaction of services and their clients over multiple interconnected domains. While native capabilities of service-oriented architectures, such as description, discovery, communication and binding, have been well understood and standardized, the issue of service composition has not yet been satisfactorily solved. This dissertation challenges the SOA postulate that service should disclose only basic functional signature, and demonstrates that based on semantic service description, including functional and non-functional properties, a viable solution for service composition can be developed (composable service architecture), that supports: 1) Extended descriptive and search capabilities by developing contract-based description language including non-functional properties such as security, dependability, timeliness; 2) Verification of composition correctness by modeling services as abstract machines and developing a formal composition language, and 3) Automatic service composition by treating automated and dynamic selection of composition partners as a search problem and developing search algorithms for that purpose. Finally, in order to show the viability of the proposed architectural solution, a prototype of Web Services composition server is described including design and implementation.

Der Trend zu immer mehr parallelen Recheneinheiten innerhalb eines Prozessors stellt an die Softwareentwicklung neue Herausforderungen. Um die vorhandenen Ressourcen auszulasten und die stetige Steigerung der Parallelität in einen Leistungszuwachs umzusetzen, muss Software von der sequentiellen Verarbeitung in eine hochgradig parallele Verarbeitung übergehen. Diese Arbeit untersucht, wie solch eine parallele Verarbeitung in Bezug auf Relationale Datenbankmanagementsysteme umzusetzen ist. Dazu wird zunächst der gesamte Prozess der Anfragebearbeitung betrachtet und vier Problembereiche identifiziert, die für das Ziel der parallelen Anfragebearbeitung auf Mehrkern-Rechnerarchitekturen maßgeblich sind. Diese Bereiche sind die Hardware selbst, das physische Datenmodell sowie die Anfrageausführung und -optimierung. Diese vier Bereiche werden innerhalb eines Rahmenwerkes betrachtet. Nach einer Einführung, wird sich die Arbeit zunächst mit Grundlagen befassen. Dazu werden die Hardwarebestandteile Speicher und Prozessor betrachtet und ihre Funktionsweise erläutert. Auf diesem Wissen aufbauend, wird ein Hardwaremodell definiert. Es ermöglicht eine von der jeweiligen Hardwarearchitektur unabhängige Softwareentwicklung, ohne den Verlust an Funktionalität und Leistung. Im Weiteren wird das physische Datenmodell untersucht und analysiert, wie das physische Datenmodell eine optimale Anfrageausführung unterstützen kann. Die verwendeten Datenstrukturen müssen dafür einen effizienten und parallelen Zugriff erlauben. Die Analyse führt zur Entwicklung eines neuartigen Indexes, der die datenparallele Abarbeitung nutzt. Gefolgt wird dieser Teil von der Anfrageausführung, in der ein neues Anfrageausführungsmodell entwickelt wird, das auf der Verwendung des Taskkonzepts beruht und eine hohe und sehr leicht gewichtige Parallelität erlaubt. Den Abschluss stellt die Anfrageoptimierung dar, worin verschiedene Ideen für die Optimierung der Ressourcenverwaltung präsentiert werden. / The upcoming generation of many-core architectures poses several new challenges for software development: Software design and software implementation has to change from sequential execution to a highly parallel execution, such that it takes full advantage of the steadily growing number of cores on a single processor. With this thesis, we investigate such highly parallel program execution in the context of relational database management systems (RDBMSs). We consider the complete process of query processing and identify four problem areas which are crucial for efficient parallel query processing on many-core architectures. These four areas are: Hardware, physical data model, query execution, and query optimization. Furthermore, we present a framework which covers all four parts, one after another. First, we give a detailed survey of computer hardware with a special focus on memory and processors. Based on this survey we propose a hardware model. Our abstraction aims to simplify the task of software development on many-core hardware. Based on the hardware model, we investigate physical data models and evaluate how the physical data model may support optimal query execution by providing efficient and parallelizable data structures. Additionally, we design a new index structure that utilizes data parallel execution by using SIMD operations. The next layer within our framework is query execution, for which we present a new task based query execution model. Our query execution model allows for a lightweight parallelism. Finally, we cover query optimization by explaining approaches for optimizing resource utilization on a query local point of view as well as query global point of view.

Textmining beschäftigt sich mit der automatisierten Annotierung von Texten und der Extraktion einzelner Informationen aus Texten, die dann für die Weiterverarbeitung zur Verfügung stehen. Texte können dabei kurze Zusammenfassungen oder komplette Artikel sein, zum Beispiel Webseiten und wissenschaftliche Artikel, umfassen aber auch textuelle Einträge in sonst strukturierten Datenbanken. Diese Dissertationsschrift bespricht zwei wesentliche Themen des biomedizinischen Textmining: die Extraktion von Zusammenhängen zwischen biologischen Entitäten ---das Hauptaugenmerk liegt dabei auf der Erkennung von Protein-Protein-Interaktionen---, und einen notwendigen Vorverarbeitungsschritt, die Erkennung von Proteinnamen. Diese Schrift beschreibt Ziele, Herausforderungen, sowie typische Herangehensweisen für alle wesentlichen Komponenten des biomedizinischen Textmining. Wir stellen eigene Methoden zur Erkennung von Proteinnamen sowie der Extraktion von Protein-Protein-Interaktionen vor. Zwei eigene Verfahren zur Erkennung von Proteinnamen werden besprochen, eines basierend auf einem Klassifikationsproblem, das andere basierend auf Suche in Wörterbüchern. Für die Extraktion von Interaktionen entwickeln wir eine Methode zur automatischen Annotierung großer Mengen von Text im Bezug auf Relationen; diese Annotationen werden dann zur Mustererkennung verwendet, um anschließend die gefundenen Muster auf neuen Text anwenden zu können. Um Muster zu erkennen, berechnen wir Ähnlichkeiten zwischen zuvor gefundenen Sätzen, die denselben Typ von Relation/Interaktion beschreiben. Diese Ähnlichkeiten speichern wir als sogenannte `consensus patterns''. Wir entwickeln eine Alignmentstrategie, die mehrschichtige Annotationen pro Position im Muster erlaubt. In Versuchen auf bekannten Benchmarks zeigen wir empirisch, dass unser vollautomatisches Verfahren Resultate erzielt, die vergleichbar sind mit existierenden Methoden, welche umfangreiche Eingriffe von Experten voraussetzen. / Text mining deals with the automated annotation of texts and the extraction of facts from textual data for subsequent analysis. Such texts range from short articles and abstracts to large documents, for instance web pages and scientific articles, but also include textual descriptions in otherwise structured databases. This thesis focuses on two key problems in biomedical text mining: relationship extraction from biomedical abstracts ---in particular, protein--protein interactions---, and a pre-requisite step, named entity recognition ---again focusing on proteins. This thesis presents goals, challenges, and typical approaches for each of the main building blocks in biomedical text mining. We present out own approaches for named entity recognition of proteins and relationship extraction of protein-protein interactions. For the first, we describe two methods, one set up as a classification task, the other based on dictionary-matching. For relationship extraction, we develop a methodology to automatically annotate large amounts of unlabeled data for relations, and make use of such annotations in a pattern matching strategy. This strategy first extracts similarities between sentences that describe relations, storing them as consensus patterns. We develop a sentence alignment approach that introduces multi-layer alignment, making use of multiple annotations per word. For the task of extracting protein-protein interactions, empirical results show that our methodology performs comparable to existing approaches that require a large amount of human intervention, either for annotation of data or creation of models.

Die Entwicklung effizienter Desktop Publishing Systeme wird behindert durch den Mangel an leistungsfähigen, automatischen Layoutalgorithmen. Aktuelle Algorithmen zum Layout ganzer Dokumente oder einzelner Seiten erfordern entweder die Formulierung des Layoutproblems in einer formalen Beschreibungssprache, oder sie benötigen fertige, detaillierte Layouttemplates. Layoutprobleme mit schwacher Semantik lassen sich schlecht in formale Sprachen umsetzen, Layout Templates verschieben den manuellen Aufwand nur vom Endnutzer zum Template Designer. Das erste Ergebnis dieser Dissertation ist ein Layoutalgorithmus, der ein allgemeines Layoutproblem löst, in dem er es als Ressourcenallokationsproblem interpretiert. Die Fläche einer einzelnen Seite ist eine Ressource, die zwischen den visuellen Elementen einer Seite verteilt wird. Das Layoutproblem wird in ein lexikographisches min-ordering Optimierungsproblem übersetzt, das durch lineare Optimierung in Echtzeit gelöst wird. Die Lösungen manuell erzeugter Layoutprobleme sind häufig über- oder unterbestimmt. Wenn das Problem überbestimmt ist, also keine gültige Lösung besitzt, muss der Algorithmus die Lösung finden, die am n\"achsten an der intendierten Lösung ist. Der Algorithmus erkennt nicht eindeutig definierte Probleme mit unbefriedigenden Lösungen und fügt die minimal notwendige Anzahl von Constraints hinzu um das vom Nutzer beabsichtigte Layout zu erzeugen. Das zweite Ergebnis ist die Entwicklung einer intuitiven Benutzerschnittstelle, die es erlaubt, die vorhergehend beschriebenen Layoutprobleme zu erzeugen. Sie verbirgt die Komplexität des Constraintsystems und vermeidet die Komplexität constraint-basierter Grafikanwendungen der Vergangenheit. Diese Benutzerschnittstelle macht formale Beschreibungssprachen und manuell erzeugte Layouttemplates überflüssig. Die Evaluation zeigt, dass die besten Tabellenlayoutalgorithmen keine signifikant besseren Ergebnisse produzieren als der allgemeinere ICBM Layout Algorithmus. / The efficiency of desktop publishing is severely limited by the lack of sophisticated automatic document layout systems. State-of-the-art algorithms either require the input to be written in a description language such as HTML and LaTeX, or to be a manually designed layout template. However, description languages are ill-suited to express layout problems with weak semantics and layout templates shift the burden from the end user to the template designer. The first contribution of this thesis is an algorithm that solves a general class of layout problems by treating them as equitable resource allocation problems. The available document area is a resource that is distributed among inter-element gaps. The layout problem is transformed into a lexicographic min-ordering optimization problem that is solved using linear programming techniques in real-time. If the layout problem is over-constrained, the quality of the solution layout degrades gracefully. The layout algorithm finds the solution layout with the most equitable distribution of constraint errors among the soft layout constraints, i.e., the solution closest to the user''s original intent. Conversely, the layout algorithm detects the under-constrained subproblems that adversely affect the solution layout. It adds the minimal number of constraints required to achieve the fully specified layout problem that is closest to the user''s input. The second contribution is the creation of an intuitive direct manipulation user interface that lets users create the aforementioned class of general constrained layout problems. It hides the complexity of the constraint system and avoids the usability problems that have plagued constraint drawing applications. It eliminates the need of document description languages and manually-created layout templates. In the evaluation, we show that the best state-of-the-art specialized table layout algorithms do not outperform the general ICBM layout algorithm by any significant margin.

Um Entwurf und Verifikation komplizierter verteilter Algorithmen leichter und verständlicher zu machen, wird oft eine Verfeinerungsmethode verwendet. Dabei wird ein einfacher Algorithmus, der gewünschte Eigenschaften erfüllt, schrittweise zu einem komplizierten Algorithmus verfeinert. In jedem Schritt sollen die gewünschten Eigenschaften erhalten bleiben. Für nachrichtenbasierte verteilte Algorithmen haben wir eine neue Verfeinerungsmethmode entwickelt. Wir beginnen mit einem Anfangsalgorithmus, der Aktionen enthält, die gemeinsame Aufgaben mehrerer Agenten beschreiben. In jedem Schritt verfeinern wir eine dieser Aktionen zu einem Netz, das nur solche Aktionen enthält, die die Aufgaben einzelner Agenten beschreiben. Jeder Schritt ist also eine Verteilung einer unverteilten Aktion. Die Analyse solcher Verfeinerungsschritte wird mit Hilfe eines neuen Verfeinerungsbegriffs - der verteilenden Verfeinerung - durchgeführt. Entscheidend dabei ist das Erhaltenbleiben der Halbordnungen des zu verfeinernden Algorithmus. Dies ist durch Kausalitäten der Aktionen der Agenten im lokalen Verfeinerungsnetz zu erreichen. Die Kausalitäten im lokalen Verfeinerungsnetz lassen sich einerseits beim Entwurf direkt durch Nachrichtenaustausch realisieren. Andererseits kann man bei der Verifikation die Gültigkeit einer Kausalität im lokalen Verfeinerungsnetz direkt vom Netz ablesen. Daher ist diese Methode leicht zu verwenden. Die Anwendung der Methode wird in der Arbeit an verschiedenen nicht trivialen Beispielen demonstriert. / In order to make design and verification of complicated distributed algorithms easier and more understandable, a refinement method is often used. A simple algorithm, which fulfills desired properties, is refined stepwise to a complicated algorithm. In each step the desired properties are preserved. For messages-based distributed algorithms we have developed a new refinement method. We begin with an initial algorithm, which contains actions, which describe common tasks of several agents. In each step we refine one of these actions to a net, which contains only such actions, which describe the tasks of individual agents. Thus, each step is a distribution of an undistributed action. The analysis of such refinement steps is accomplished with the help of a new refinement notation - the distributing refinement. Preservation of the partial order of the refined algorithm is important. This can be achieved by causalities of the actions of the agents in the local refinement net. Causalities in the local refinement net can be realized on the one hand at design directly by messages passing. On the other hand, at verification one can read the validity of causality in the local refinement net directly from the net. Therefore, this method is easy to use. The application of the method is demonstrated by several nontrivial examples in this thesis.

Viele moderne Dateisysteme unterstützen Snapshots zur Erzeugung konsistenter Online-Backups, zur Wiederherstellung verfälschter oder ungewollt geänderter Dateien, sowie zur Rückverfolgung von Änderungen an Dateien und Verzeichnissen. Während frühere Arbeiten zu Snapshots in Dateisystemen vorwiegend lokale Dateisysteme behandeln, haben moderne Trends wie Cloud- oder Cluster-Computing dazu geführt, dass die Datenhaltung in verteilten Speichersystemen an Bedeutung gewinnt. Solche Systeme umfassen häufig eine Vielzahl an Speicher-Servern, was besondere Herausforderungen mit Hinblick auf Skalierbarkeit, Verfügbarkeit und Ausfallsicherheit mit sich bringt. Diese Arbeit beschreibt einen Snapshot-Algorithmus für großangelegte verteilte Dateisysteme und dessen Integration in XtreemFS, ein skalierbares objektbasiertes Dateisystem für Grid- und Cloud-Computing-Umgebungen. Die zwei Bausteine des Algorithmus sind ein System zur effizienten Erzeugung und Verwaltung von Dateiinhalts- und Metadaten-Versionen, sowie ein skalierbares, ausfallsicheres Verfahren zur Aggregation bestimmter Versionen in einem Snapshot. Um das Problem einer fehlenden globalen Zeit zu bewältigen, implementiert der Algorithmus ein weniger restriktives, auf Zeitstempeln lose synchronisierter Server-Uhren basierendes Konsistenzmodell für Snapshots. Die wesentlichen Beiträge der Arbeit sind: 1) ein formales Modell von Snapshots und Snapshot-Konsistenz in verteilten Dateisystemen; 2) die Beschreibung effizienter Verfahren zur Verwaltung von Metadaten- und Dateiinhalts-Versionen in objektbasierten Dateisystemen; 3) die formale Darstellung eines skalierbaren, ausfallsicheren Snapshot-Algorithmus für großangelegte objektbasierte Dateisysteme; 4) eine detaillierte Beschreibung der Implementierung des Algorithmus in XtreemFS. Eine umfangreiche Auswertung belegt, dass der vorgestellte Algorithmus die Nutzerdatenrate kaum negativ beeinflusst, und dass er mit großen Zahlen an Snapshots und Versionen skaliert. / Snapshots are present in many modern file systems, where they allow to create consistent on-line backups, to roll back corruptions or inadvertent changes of files, and to keep a record of changes to files and directories. While most previous work on file system snapshots refers to local file systems, modern trends like cloud and cluster computing have shifted the focus towards distributed storage infrastructures. Such infrastructures often comprise large numbers of storage servers, which presents particular challenges in terms of scalability, availability and failure tolerance. This thesis describes snapshot algorithm for large-scale distributed file systems and its integration in XtreemFS, a scalable object-based file system for grid and cloud computing environments. The two building blocks of the algorithm are a version management scheme, which efficiently records versions of file content and metadata, as well as a scalable and failure-tolerant mechanism that aggregates specific versions in a snapshot. To overcome the lack of a global time in a distributed system, the algorithm implements a relaxed consistency model for snapshots, which is based on timestamps assigned by loosely synchronized server clocks. The main contributions of the thesis are: 1) a formal model of snapshots and snapshot consistency in distributed file systems; 2) the description of efficient schemes for the management of metadata and file content versions in object-based file systems; 3) the formal presentation of a scalable, fault-tolerant snapshot algorithm for large-scale object-based file systems; 4) a detailed description of the implementation of the algorithm as part of XtreemFS. An extensive evaluation shows that the proposed algorithm has no severe impact on user I/O, and that it scales to large numbers of snapshots and versions.