Stuttgart, Univ., Diss., 2003.

University, Diss., 2005--Kassel.

In dieser Diplomarbeit wird eine Möglichkeit für die Abarbeitung von verteilten Workflows konzeptuell erarbeitet und prototypisch implementiert. Dabei werden als Grundlage des Konzepts die Standards der Workflow Management Coalition zur Beschreibung von Workflows und Workflow Management Systemen verwendet. Für die verteilte Abarbeitung von Prozessen wurde eine RMI-basierte Abwandlung des ASAP-Protokolls implementiert. Die Implementierung nutzt Enhydra Shark als Laufzeitumgebung und die Schnittstellen für die verteilte Abarbeitung sind für dieses System angepasst. Anhand von Beispielen und Testfällen wird die Funktionsweise des erstellten Konzepts und seiner Realisierung verdeutlicht.

Heutige Systeme für die Fertigungssteuerung müssen viele unterschiedliche Problemstellungen lösen. Vor allem die Komplexität der Anforderungen sowie die unterschiedlichen Interessen am Ablaufplan, wie hohe Termintreue, kurze Durchlaufzeiten und geringe Produktionskosten, gilt es zu beachten. Erschwert wird dies durch kurze Planungsfristen und hohe Flexibilitätsanforderungen. Komplexe Problemstellungen werden in der künstlichen Intelligenz unter anderem durch den Einsatz von Multiagentensystemen gelöst. Ein solches System zeichnet sich durch eine hohe Flexibilität sowie schnelle Reaktion auch auf unbekannte und nicht spezifizierte Ereignisse aus. Im Rahmen dieser Arbeit werden beide Forschungsgebiete miteinander verknüpft und so der Ansatz des agentenbasierten Fertigungsmanagements verfolgt. Der Schwerpunkt wird dabei auf die Ablaufplanung mit Anwendung auf produzierende Unternehmen gelegt. Vorgestellt wird ein Konzept, das auf Basis der Multiagenten-Technologie neue Aufträge möglichst schnell einplant und das eine Reparatur zur Herstellung der Konsistenz des Planes binnen Sekunden durchführt. Weiterhin findet die Vorstellung einer Planoptimierung statt, welche die vom Bediener spezifizierten Optimalitätsbedingungen umsetzt. Alle diese Verfahren laufen dezentral durch die Agenten ab und werden nur grob durch einen speziellen Agenten gesteuert. Grundlage des Systems ist ein Bewertungssystem, das den Plan anhand verschiedener Kriterien beurteilt. Zur Überprüfung der Funktion des erarbeiteten Konzeptes wurde ein Prototyp implementiert und anschließend analysiert. Trotz der Anwendung auf die Fertigungssteuerung sind alle Ansätze allgemein gehalten und können somit auch auf andere Bereiche, in denen eine Planung erforderlich ist, angewendet werden.

Die vorliegende Arbeit untersucht die Anwendung des Groupware Systems cAR/PE!, das auf der Mixed Reality Technologie basiert. cAR/PE! wurde im Forschungszentrum Ulm der Daimler- Chrysler AG speziell für Ingenieure entwickelt, die in verteilten Gruppen zusammenarbeiten. Im Rahmen zweier Studien fand eine Testung der Software in verschiedenen Werken der DaimlerChrysler AG statt. Interviews mit verteilt arbeitenden Ingenieuren als auch deren Beobachtung bei Projektmeetings bildeten die Grundlage für die Konzeption beider Studien. In der ersten Studie wurde der erste Prototyp von cAR/PE! untersucht. Hierbei zeigte sich kein signifikanter Unterschied in der Lösungsgüte von Gruppen, die eine Aufgabe mit geringer Komplexität in cAR/PE! oder in einem realen Meeting zu bearbeiten hatten. Bei der Bearbeitung der komplexen Konstruktionsaufgabe schnitten Gruppen in realen Meetings besser als cAR/PE!-Meeting Gruppen ab. Auf Grundlage der Ergebnisse dieser ersten Studie wurde cAR/PE! Zu cAR/PE!2 weiterentwickelt und in einer zweiten Studie wiederum evaluiert. Die zweite Studie bestand aus zwei Forschungsbedingungen, in denen die Gruppen die komplexe Konstruktionsaufgabe amphibious car bearbeiten mussten. Unter der ersten Forschungsbedingung schnitten reale Meetings2 Gruppen weiterhin signifikant besser als cAR/PE!2-Gruppen ab. Der Problemlöseprozess dieser Gruppen war vergleichbar und somit nicht mehr - wie in der ersten Studie - strukturell unterschiedlich. Die Unterschiede in der Lösungsgüte lassen sich vielmehr auf die stärkere softwarebedingte Beeinträchtigung durch die Nutzung von cAR/PE!2 zurückführen. Unter der zweiten Forschungsbedingung wurde der Einfluss der Arbeitsumgebung auf die Qualität der Gruppenarbeit untersucht. Die Arbeitsumgebung weist einen direkten, allerdings nicht signifikanten Einfluss auf den Problemlöseprozess der Gruppen auf. Somit konnte abgeleitet werden, dass die Arbeitsumgebung für eine erfolgreiche Kommunikation lediglich relevante Informationen für die Problemlösung und die Bestimmung des Sprecherortes beinhalten sollte. Auf der theoretischen Ebene konnte das mit task awareness erweiterte Rahmenmodell von Vertegaal et al. (1997) untermauert werden. Außerdem erwies sich das Model for the elements of distributed group work als sehr geeignet zur strukturierten Darstellung von Unterschieden in Gruppenarbeit. Auf der praktischen Ebene wurde cAR/PE! durch die Ergebnisse beider Studien weiterentwickelt und etablierte sich als Groupware System in den Werken bei der Daimler-Chrysler AG zwischen Sindelfingen und Bremen. / The aim of this thesis is to examine the use of the groupware system cAR/PE!, which is based on Mixed Reality technology. cAR/PE! was developed at the DaimlerChrylser Research Center in Ulm dedicated to distributed engineering group work and subsequently tested in two studies at various plants of DaimlerChrysler AG. Interviews and observations of engineer meetings in distributed project groups provided the basis for the conception of the two empirical studies. In the first study the first cAR/PE! prototype was tested. The study confirmed that less complex tasks could be solved equally well in both a conventional meeting room and in cAR/PE! Meetings. However, when solving a complex task, the conventional meeting was more favorable than cAR/PE!. These results were exploited for further developments of cAR/PE! resulting in cAR/PE!2. In the second study, the modifications were evaluated under two conditions to solve the complex design task amphibious car. Under the first condition, groups were still better at solving a complex task under the conventional meeting2 condition compared with cAR/PE!2, even the problem-solving processes were comparable and no longer structurally different than in the first study. The differences in the group results were caused by the software when using cAR/PE!2. Under the second condition, the influence of the meeting workspace was tested; this had a direct influence on the problem-solving processes of the groups, but the result was not significant. However, from this outcome it was deduced that only the relevant information for the tasks and the physical placement of the speaker leads to a successful conversation. On the theoretical level, the enhancement of the framework developed by Vertegaal et al. (1997) introducing the concept of task awareness and the appropriateness of the Model for the elements of distributed group work were confirmed. On the practical level, cAR/PE!2 was improved based on the results of both studies, then implemented and established as a permanent running groupware system between DaimlerChrysler´s plants in Sindelfingen and Bremen.

Ziel dieser Arbeit ist es, die Entwicklung von RDF-Wissensbasen in verteilten kollaborativen Szenarien zu unterstützen. In dieser Arbeit wird eine neue Methodik für verteiltes kollaboratives Knowledge Engineering – „Quit“ – vorgestellt. Sie geht davon aus, dass es notwendig ist, während des gesamten Kooperationsprozesses Dissens auszudrücken und individuelle Arbeitsbereiche für jeden Mitarbeiter bereitzustellen. Der Ansatz ist von der Git-Methodik zum kooperativen Software Engineering inspiriert und basiert auf dieser. Die Analyse des Standes der Technik zeigt, dass kein System die Git-Methodik konsequent auf das Knowledge Engineering überträgt. Die Hauptmerkmale der Quit-Methodik sind unabhängige Arbeitsbereiche für jeden Benutzer und ein gemeinsamer verteilter Arbeitsbereich für die Zusammenarbeit. Während des gesamten Kollaborationsprozesses spielt die Data-Provenance eine wichtige Rolle. Zur Unterstützung der Methodik ist der Quit-Stack als eine Sammlung von Microservices implementiert, die es ermöglichen, die Semantic-Web-Datenstruktur und Standardschnittstellen in den verteilten Kollaborationsprozess zu integrieren. Zur Ergänzung der verteilten Datenerstellung werden geeignete Methoden zur Unterstützung des Datenverwaltungsprozesses erforscht. Diese Managementprozesse sind insbesondere die Erstellung und das Bearbeiten von Daten sowie die Publikation und Exploration von Daten. Die Anwendung der Methodik wird in verschiedenen Anwendungsfällen für die verteilte Zusammenarbeit an Organisationsdaten und an Forschungsdaten gezeigt. Weiterhin wird die Implementierung quantitativ mit ähnlichen Arbeiten verglichen. Abschließend lässt sich feststellen, dass der konsequente Ansatz der Quit-Methodik ein breites Spektrum von Szenarien zum verteilten Knowledge Engineering im Semantic Web ermöglicht.:Preface by Thomas Riechert Preface by Cesare Pautasso 1 Introduction 2 Preliminaries 3 State of the Art 4 The Quit Methodology 5 The Quit Stack 6 Data Creation and Authoring 7 Publication and Exploration 8 Application and Evaluation 9 Conclusion and Future Work Bibliography Web References List of Figures List of Tables List of Listings List of Definitions and Acronyms List of Namespace Prefixes / The aim of this thesis is to support the development of RDF knowledge bases in a distributed collaborative setup. In this thesis, a new methodology for distributed collaborative knowledge engineering – called Quit – is presented. It follows the premise that it is necessary to express dissent throughout a collaboration process and to provide individual workspaces for each collaborator. The approach is inspired by and based on the Git methodology for collaboration in software engineering. The state-of-the-art analysis shows that no system is consequently transferring the Git methodology to knowledge engineering. The key features of the Quit methodology are independent workspaces for each user and a shared distributed workspace for the collaboration. Throughout the whole collaboration process data provenance plays an important role. To support the methodology the Quit Stack is implemented as a collection of microservices, that allow to integrate the Semantic Web data structure and standard interfaces with the distributed collaborative process. To complement the distributed data authoring, appropriate methods to support the data management process are researched. These management processes are in particular the creation and authoring of data as well as the publication and exploration of data. The application of the methodology is shown in various use cases for the distributed collaboration on organizational data and on research data. Further, the implementation is quantitatively compared to the related work. Finally, it can be concluded that the consequent approach followed by the Quit methodology enables a wide range of distributed Semantic Web knowledge engineering scenarios.:Preface by Thomas Riechert Preface by Cesare Pautasso 1 Introduction 2 Preliminaries 3 State of the Art 4 The Quit Methodology 5 The Quit Stack 6 Data Creation and Authoring 7 Publication and Exploration 8 Application and Evaluation 9 Conclusion and Future Work Bibliography Web References List of Figures List of Tables List of Listings List of Definitions and Acronyms List of Namespace Prefixes

Die vorliegende Arbeit untersucht die Anwendung des Groupware Systems cAR/PE!, das auf der Mixed Reality Technologie basiert. cAR/PE! wurde im Forschungszentrum Ulm der Daimler- Chrysler AG speziell für Ingenieure entwickelt, die in verteilten Gruppen zusammenarbeiten. Im Rahmen zweier Studien fand eine Testung der Software in verschiedenen Werken der DaimlerChrysler AG statt. Interviews mit verteilt arbeitenden Ingenieuren als auch deren Beobachtung bei Projektmeetings bildeten die Grundlage für die Konzeption beider Studien. In der ersten Studie wurde der erste Prototyp von cAR/PE! untersucht. Hierbei zeigte sich kein signifikanter Unterschied in der Lösungsgüte von Gruppen, die eine Aufgabe mit geringer Komplexität in cAR/PE! oder in einem realen Meeting zu bearbeiten hatten. Bei der Bearbeitung der komplexen Konstruktionsaufgabe schnitten Gruppen in realen Meetings besser als cAR/PE!-Meeting Gruppen ab. Auf Grundlage der Ergebnisse dieser ersten Studie wurde cAR/PE! Zu cAR/PE!2 weiterentwickelt und in einer zweiten Studie wiederum evaluiert. Die zweite Studie bestand aus zwei Forschungsbedingungen, in denen die Gruppen die komplexe Konstruktionsaufgabe amphibious car bearbeiten mussten. Unter der ersten Forschungsbedingung schnitten reale Meetings2 Gruppen weiterhin signifikant besser als cAR/PE!2-Gruppen ab. Der Problemlöseprozess dieser Gruppen war vergleichbar und somit nicht mehr - wie in der ersten Studie - strukturell unterschiedlich. Die Unterschiede in der Lösungsgüte lassen sich vielmehr auf die stärkere softwarebedingte Beeinträchtigung durch die Nutzung von cAR/PE!2 zurückführen. Unter der zweiten Forschungsbedingung wurde der Einfluss der Arbeitsumgebung auf die Qualität der Gruppenarbeit untersucht. Die Arbeitsumgebung weist einen direkten, allerdings nicht signifikanten Einfluss auf den Problemlöseprozess der Gruppen auf. Somit konnte abgeleitet werden, dass die Arbeitsumgebung für eine erfolgreiche Kommunikation lediglich relevante Informationen für die Problemlösung und die Bestimmung des Sprecherortes beinhalten sollte. Auf der theoretischen Ebene konnte das mit task awareness erweiterte Rahmenmodell von Vertegaal et al. (1997) untermauert werden. Außerdem erwies sich das Model for the elements of distributed group work als sehr geeignet zur strukturierten Darstellung von Unterschieden in Gruppenarbeit. Auf der praktischen Ebene wurde cAR/PE! durch die Ergebnisse beider Studien weiterentwickelt und etablierte sich als Groupware System in den Werken bei der Daimler-Chrysler AG zwischen Sindelfingen und Bremen. / The aim of this thesis is to examine the use of the groupware system cAR/PE!, which is based on Mixed Reality technology. cAR/PE! was developed at the DaimlerChrylser Research Center in Ulm dedicated to distributed engineering group work and subsequently tested in two studies at various plants of DaimlerChrysler AG. Interviews and observations of engineer meetings in distributed project groups provided the basis for the conception of the two empirical studies. In the first study the first cAR/PE! prototype was tested. The study confirmed that less complex tasks could be solved equally well in both a conventional meeting room and in cAR/PE! Meetings. However, when solving a complex task, the conventional meeting was more favorable than cAR/PE!. These results were exploited for further developments of cAR/PE! resulting in cAR/PE!2. In the second study, the modifications were evaluated under two conditions to solve the complex design task amphibious car. Under the first condition, groups were still better at solving a complex task under the conventional meeting2 condition compared with cAR/PE!2, even the problem-solving processes were comparable and no longer structurally different than in the first study. The differences in the group results were caused by the software when using cAR/PE!2. Under the second condition, the influence of the meeting workspace was tested; this had a direct influence on the problem-solving processes of the groups, but the result was not significant. However, from this outcome it was deduced that only the relevant information for the tasks and the physical placement of the speaker leads to a successful conversation. On the theoretical level, the enhancement of the framework developed by Vertegaal et al. (1997) introducing the concept of task awareness and the appropriateness of the Model for the elements of distributed group work were confirmed. On the practical level, cAR/PE!2 was improved based on the results of both studies, then implemented and established as a permanent running groupware system between DaimlerChrysler´s plants in Sindelfingen and Bremen.

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.

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.