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.

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.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.

No description available.