Ein drahtloses Multihop-Netzwerk (DMN) ist ein verteiltes Kommunikationssystem, welches vor allem die Fähigkeit zur automatischen Anpassung an sich ständig änderne Umgebungsbedingungen hat. Eine zentrale Fragestellung in DMNen ist, ob das Netzwerk partitioniert ist, ob also nicht mehr jeder Knoten mit jedem anderen Knoten kommunizieren kann. Um festzustellen, ob eine Partitionierung droht werden mit Hilfe von 2-Zusammenhangstests Brücken und Artikulationspunkte im Kommunikationsgraphen gesucht. Daraufhin können anschließend korrektive Aktionen eingeleitet werden um die Partitionierung zu verhindern und somit die Netzwerkverfügbarkeit zu erhöhen. Eine Vielzahl von 2-Zusammenhangstestverfahren wurde bereits erfolgreich bei drahtgebundenen Netzen eingesetzt. Allerdings sind diese Verfahren ungeeignet für drahtlose Netze, da die Ungenauigkeiten durch den häufigen Paketverlust in solchen Systemen bisher nicht berücksichtigt wurden. Mit Hilfe von stochastischen Modellen wird gezeigt, dass Fehler in der Entscheidungsfindung für DMNen bereits bei sehr einfachen Problemen wie der Link-Erkennung signifikant sein können. In dieser Arbeit werden daher verschiedene Verfahren präsentiert, die auch auf Grundlage unsicherer Informationen noch eine verlässliche Entscheidungsfindung ermöglichen. Die Arbeit präsentiert einen neuen verteilten Algorithmus zum Test auf 2-Zusammenhang, welcher Fehler durch Nachrichtenverlust berücksichtigt und gleichzeitig die Anzahl an Nachrichten reduziert. Basierend auf einer umfassenden Analyse der Einflüsse von Kommunikationsfehlern auf den Algorithmus, wurden Abstimmungsprozeduren entwickelt, die die Wahrscheinlichkeit von Fehlentscheidungen nochmals reduzieren. Zur weiteren Analyse werden die Algorithmen erstens in der Motelab-Umgebung und zweitens mit Hilfe von Simulationen untersucht. Die präsentierten Algorithmen zeigen überzeugende Ergebnisse unter variierenden Bedingungen, was ihre Anwendbarkeit in realen Szenarien unterstreicht. / Wireless multi-hop network (WMN) is a distributed communication system composed of autonomous processing nodes that is known for its ability to automatically adjust to rapidly changing conditions in the surrounding environment. Connectivity is one of the basic properties of a network. Removal of a bridge or an articulation point partitions a network. Biconnectivity testing identifies bridges and articulation points in a network, and once they are known corrective actions can be performed in order to improve network''s reliability. Numerous biconnectivity testing algorithms are successfully applied in graphs, wired networks and multiprocessor systems. However, they are inadequate for application in wireless networks since the frequent packet losses introduce uncertainty in the system which these algorithms cannot handle. The stochastic analysis shows that errors in decision-making in WMNs are considerable even for seemingly simple tasks such as the detection of links. The main contribution of this work is to provide means for accurate binary decision-making under uncertainty within the context of biconnectivity testing in WMNs. A distributed algorithm is developed that successfully handles the faults caused by message losses and simultaneously utilizes benefits of wireless communication to reduce message complexity from O(e) to O(n). Based on stochastic analysis of WMN topologies and a comprehensive analysis of impact of communication faults on algorithm''s behavior, the algorithm is extended by voting theory to reduce probability of erroneous decisions. The algorithm and the voting rules are evaluated in experiments in Motelab testbed and in the event-based simulator Jist/SWANS. The algorithm is accurate under various conditions which demonstrates its applicability in reality and capability of successful operation in presence of packet losses.

Vernetzte Standardarbeitsplatzrechner (sog. Cluster) sind eine attraktive Umgebung zur Ausf"uhrung paralleler Programme; f"ur einige Anwendungsgebiete bestehen jedoch noch immer ungel"oste Probleme. Ein solches Problem ist die Verl"asslichkeit und Rechtzeitigkeit der Programmausf"uhrung: In vielen Anwendungen ist es wichtig, sich auf die rechtzeitige Fertigstellung eines Programms verlassen zu k"onnen. Mechanismen zur Kombination dieser Eigenschaften f"ur parallele Programme in verteilten Rechenumgebungen sind das Hauptanliegen dieser Arbeit. Zur Behandlung dieses Anliegens ist eine gemeinsame Metrik f"ur Verl"asslichkeit und Rechtzeitigkeit notwendig. Eine solche Metrik ist die Responsivit"at, die f"ur die Bed"urfnisse dieser Arbeit verfeinert wird. Als Fallstudie werden Calypso und Charlotte, zwei Systeme zur parallelen Programmierung, im Hinblick auf Responsivit"at untersucht und auf mehreren Abstraktionsebenen werden Ansatzpunkte zur Verbesserung ihrer Responsivit"at identifiziert. L"osungen f"ur diese Ansatzpunkte werden zu allgemeineren Mechanismen f"ur (parallele) responsive Dienste erweitert. Im Einzelnen handelt es sich um 1. eine Analyse der Responsivit"at von Calypsos ``eager scheduling'' (ein Verfahren zur Lastbalancierung und Fehlermaskierung), 2. die Behebung eines ``single point of failure,'' zum einen durch eine Responsivit"atsanalyse von Checkpointing, zum anderen durch ein auf Standardschnittstellen basierendes System zur Replikation bestehender Software, 3. ein Verfahren zur garantierten Ressourcenzuteilung f"ur parallele Programme und 4.die Einbeziehung semantischer Information "uber das Kommunikationsmuster eines Programms in dessen Ausf"uhrung zur Verbesserung der Leistungsf"ahigkeit. Die vorgeschlagenen Mechanismen sind kombinierbar und f"ur den Einsatz in Standardsystemen geeignet. Analyse und Experimente zeigen, dass diese Mechanismen die Responsivit"at passender Anwendungen verbessern. / Clusters of standard workstations have been shown to be an attractive environment for parallel computing. However, there remain unsolved problems to make them suitable to some application scenarios. One of these problems is a dependable and timely program execution: There are many applications in which a program should be successfully completed at a predictable point of time. Mechanisms to combine the properties of both dependable and timely execution of parallel programs in distributed computing environments are the main objective of this dissertation. Addressing these properties requires a joint metric for dependability and timeliness. Responsiveness is such a metric; it is refined for the purposes of this work. As a case study, Calypso and Charlotte, two parallel programming systems, are analyzed and their shortcomings on several abstraction levels with regard to responsiveness are identified. Solutions for them are presented and generalized, resulting in widely applicable mechanisms for (parallel) responsive services. Specifically, these solutions are: 1) a responsiveness analysis of Calypso's eager scheduling (a mechanism for load balancing and fault masking), 2) ameliorating a single point of failure by a responsiveness analysis of checkpointing and by a standard interface-based system for replication of legacy software, 3) managing resources in a way suitable for parallel programs, and 4) using semantical information about the communication pattern of a program to improve its performance. All proposed mechanisms can be combined and are suitable for use in standard environments. It is shown by analysis and experiments that these mechanisms improve the responsiveness of eligible applications.

Die Besonderheit der drahtlosen Kommunikation gegenüber den drahtgebundenen Netzwerken liegt im drahtlosen Übertragungsmedium. Aufgrund der Broadcast-Eigenschaft des Übertragungsmediums werden Nachrichten potentiell von allen Netzwerkstationen empfangen, welche sich in der Übertragungsreichweite des Senders aufhalten. Als Konsequenz können bei einem unsynchronisierten Medienzugriff mehrere Nachrichten beim Empfänger kollidieren und nicht korrekt empfangen werden. Dieses Phänomen wird auch als Interferenz bezeichnet. Um solche Interferenzen zu vermeiden, wurden spezielle Protokolle für den Medienzugriff in drahtlosen Netzen entwickelt. Ein solcher Ansatz für drahtlose Maschennetze ist die verteilte Kanalzuweisung. Bei der verteilten Kanalzuweisung werden sich nicht-überlappende Kanäle im verfügbaren Frequenzspektrum für Übertragungen verwendet, die auf dem gleichen Kanal Interferenzen erzeugen würden. Dieser Ansatz ist möglich, da die verwendeten Funktechnologien, wie zum Beispiel IEEE 802.11 (WLAN), mehrere nicht-überlappende Kanäle bereitstellen. Aufgrund der großen Verbreitung von IEEE 802.11, ist eine hohe Dichte von privaten wie kommerziellen Netzen im urbanen Raum die Norm. Diese räumlich überlappenden Netze konkurrieren um den Medienzugriff. Daher ist es für die Leistung von Kanalzuweisungsalgorithmen von großer Bedeutung, die Aktivität der externen Netze mit einzubeziehen. Die Leistung der vorgelegten Arbeit umfasst das Design, die Implementierung und Validierung von Modellen und Algorithmen zur Reduzierung von Interferenzen in drahtlosen Maschennetzen. Die Arbeit beinhaltet die Entwicklung eines Messungs-basierten Interferenzmodells, mit dem Interferenzabhängigkeiten der Maschenrouter untereinander effizient bestimmt werden können. Weiterhin wurde ein Algorithmus für die verteilte Kanalzuweisung entwickelt, der die Aktivität von externen Netzen berücksichtigt. Die Gesamtlösung wurde in einem großen drahtlosen Maschennetz experimentell validiert. / Due to the broadcast nature of the shared medium, wireless transmissions are potentially received by all network stations in the communication range of the sender. With an unsynchronized medium access, multiple transmissions may be active at the same time and thus interfere with each other. In consequence, multiple transmissions may collide at the receiver side and cannot be properly decoded. For this reason, protocols have been developed on the MAC layer to synchronize the medium access and thus reduce interference effects. One of these approaches in wireless mesh networks is channel assignment. The idea of channel assignment is to minimize the network-wide interference by utilizing non-overlapping channels for otherwise interfering wireless transmissions. This is feasible, since wireless mesh routers are usually equipped with multiple radios and commonly used wireless network technologies, such as IEEE 802.11, provide multiple non-overlapping channels. Since IEEE 802.11 operates in the unlicensed frequency spectrum, the dense distribution of private and commercial network deployments of WLANs in urban areas poses a new challenge. Co-located networks compete for the wireless medium, thus decreasing the achievable network performance in terms of throughput and latency. Therefore, an important issue for efficient channel assignment is to also address external interference The contributions of this dissertation comprise the design, implementation, and validation of models and algorithms to enable wireless multi-hop networks to become interference-aware. This includes a measurement-based interference model suitable for large-scale network deployments. A distributed channel assignment algorithm has been developed that considers external sources of interference. The overall solution has been experimentally validated in a large-scale wireless multi-hop multi-radio testbed and has significantly increased the network performance with regard to the network capacity.

Diese Habilitationsschrift richtete auf zwei diskrete Strukturen aus: planare Strukturen und zufällige Graphen-Prozesse. Zunächst werden zufällige planare Strukturen untersucht, mit folgende Gesichtspunkte: - Wieviele planare Strukturen gibt es? - Wie kann effizient eine zufällige planare Struktur gleichverteilt erzeugt werden? - Welche asymptotischen Eigenschaften hat eine zufällige planare Struktur mit hoher Wahrscheinlichkeit? Um diese Fragen zu beantworten, werden die planaren Strukturen in Teile mit höherer Konnektivität zerlegt. Für die asymptotische Enumeration wird zuerst die Zerlegung als das Gleichungssystem der generierenden Funktionen interpretiert. Auf dem Gleichungssystem wird dann Singularitätenanalyse angewendet. Für die exakte Enumeration und zufällige Erzeugung wird die rekursive Methode verwendet. Für die typischen Eigenschaften wird die probabilistische Methode auf asymptotischer Anzahl angewendet. Des Weiteren werden zufällige Graphen-Prozesse untersucht. Zufällige Graphen wurden zuerst von Erdos und Renyi eingeführt und untersucht weitgehend seitdem. Ein zufälliger Graphen-Prozess ist eine Markov-Kette, deren Zustandsraum eine Menge der Graphen mit einer gegebenen Knotenmenge ist. Der Prozess fängt mit isolierten Konten an, und in jedem Ablaufschritt entsteht ein neuer Graph aus dem aktuellen Graphen durch das Hinzufügen einer neuen Kante entsprechend einer vorgeschriebenen Regel. Typische Fragen sind: - Wie ändert sich die Wahrscheinlichkeit, dass ein von einem zufälligen Graphen-Prozess erzeugter Graph zusammenhängend ist? - Wann erfolgt der Phasenübergang? - Wie groß ist die größte Komponente? In dieser Habilitationsschrift werden diese Fragen über zufällige Graphen-Prozesse mit Gradbeschränkungen beantwortet. Dafür werden probabilistische Methoden, insbesondere Differentialgleichungsmethode, Verzweigungsprozesse, Singularitätsanalyse und Fourier-Transformationen, angewendet. / This thesis focuses on two kinds of discrete structures: planar structures, such as planar graphs and subclasses of them, and random graphs, particularly graphs generated by random processes. We study first planar structures from the following aspects. - How many of them are there (exactly or asymptotically)? - How can we efficiently sample a random instance uniformly at random? - What properties does a random planar structure have, with high probability? To answer these questions we decompose the planar structures along the connectivity. For the asymptotic enumeration we interpret the decomposition in terms of generating functions and derive the asymptotic number, using singularity analysis. For the exact enumeration and the uniform generation we use the recursive method. For typical properties of random planar structures we use the probabilistic method, together with the asymptotic numbers. Next we study random graph processes. Random graphs were first introduced by Erdos and Renyi and studied extensively since. A random graph process is a Markov chain whose stages are graphs on a given vertex set. It starts with an empty graph, and in each step a new graph is obtained from a current graph by adding a new edge according to a prescribed rule. Recently random graph processes with degree restrictions received much attention. In the thesis, we study random graph processes where the minimum degree grows quite quickly with the following questions in mind: - How does the connectedness of a graph generated by a random graph process change as the number of edges increases? - When does the phase transition occur? - How big is the largest component? To investigate the random graph processes we use the probabilistic method, Wormald''s differential equation method, multi-type branching processes, and the singularity analysis.

Die Anwendung von Methodiken und Technologien aus dem Bereich der Softwaretechnik auf den Bereich der Umweltmodellierung ist eine gemeinhin akzeptierte Vorgehensweise. Im Rahmen der "modellgetriebenen Entwicklung"(MDE, model-driven engineering) werden Technologien entwickelt, die darauf abzielen, Softwaresysteme vorwiegend auf Basis von im Vergleich zu Programmquelltexten relativ abstrakten Modellen zu entwickeln. Ein wesentlicher Bestandteil von MDE sind Techniken zur effizienten Entwicklung von "domänenspezifischen Sprachen"( DSL, domain-specific language), die auf Sprachmetamodellen beruhen. Die vorliegende Arbeit zeigt, wie modellgetriebene Entwicklung, und insbesondere die metamodellbasierte Beschreibung von DSLs, darüber hinaus Aspekte der Pragmatik unterstützen kann, deren Relevanz im erkenntnistheoretischen und kognitiven Hintergrund wissenschaftlichen Forschens begründet wird. Hierzu wird vor dem Hintergrund der Erkenntnisse des "modellbasierten Forschens"(model-based science und model-based reasoning) gezeigt, wie insbesondere durch Metamodelle beschriebene DSLs Möglichkeiten bieten, entsprechende pragmatische Aspekte besonders zu berücksichtigen, indem sie als Werkzeug zur Erkenntnisgewinnung aufgefasst werden. Dies ist v.a. im Kontext großer Unsicherheiten, wie sie für weite Teile der Umweltmodellierung charakterisierend sind, von grundsätzlicher Bedeutung. Die Formulierung eines sprachzentrierten Ansatzes (LCA, language-centered approach) für die Werkzeugunterstützung konkretisiert die genannten Aspekte und bildet die Basis für eine beispielhafte Implementierung eines Werkzeuges mit einer DSL für die Beschreibung von Zellulären Automaten (ZA) für die Umweltmodellierung. Anwendungsfälle belegen die Verwendbarkeit von ECAL und der entsprechenden metamodellbasierten Werkzeugimplementierung. / The application of methods and technologies of software engineering to environmental modeling and simulation (EMS) is common, since both areas share basic issues of software development and digital simulation. Recent developments within the context of "Model-driven Engineering" (MDE) aim at supporting the development of software systems at the base of relatively abstract models as opposed to programming language code. A basic ingredient of MDE is the development of methods that allow the efficient development of "domain-specific languages" (DSL), in particular at the base of language metamodels. This thesis shows how MDE and language metamodeling in particular, may support pragmatic aspects that reflect epistemic and cognitive aspects of scientific investigations. For this, DSLs and language metamodeling in particular are set into the context of "model-based science" and "model-based reasoning". It is shown that the specific properties of metamodel-based DSLs may be used to support those properties, in particular transparency, which are of particular relevance against the background of uncertainty, that is a characterizing property of EMS. The findings are the base for the formulation of an corresponding specific metamodel- based approach for the provision of modeling tools for EMS (Language-centered Approach, LCA), which has been implemented (modeling tool ECA-EMS), including a new DSL for CA modeling for EMS (ECAL). At the base of this implementation, the applicability of this approach is shown.

Beim Graphisomorphieproblem geht es um die Frage, ob zwei Graphen bis auf Knotenumbenennungen die gleiche Struktur haben. Es ist eines der wenigen verbleibenden natürlichen Probleme, für die weder ein Polynomialzeitalgorithmus noch NP-Härte bekannt ist. Aus dieser Situation ist ein Forschungszweig erwachsen, der effiziente Isomorphiealgorithmen für eingeschränkte Graphklassen entwickelt. Der Hauptbeitrag dieser Arbeit besteht in Logspace-Algorithmen, die das Isomorphieproblem für k-Bäume, Intervallgraphen, sowie Helly- und Proper-Kreisbogengraphen lösen. Dies verbessert zuvor bekannte parallele Algorithmen und führt zu einer vollständigen Klassifikation der Komplexität dieser Probleme, da für sie auch Logspace-Härte nachgewiesen wird. Tatsächlich leisten die vorgestellten Algorithmen mehr: Im Fall der k-Bäume berechnet der Algorithmus kanonische Knotenbenennungen mit O(k log n) Platz. Eine alternative Implementation des Algorithmus kommt mit O((k+1)!n) Zeit aus – hierbei ist n die Anzahl der Knoten – und ist damit der schnellste bekannte FPT-Algorithmus für Isomorphie von k-Bäumen. Die Algorithmen für Intervall- und Kreisbogengraphen berechnen kanonische Repräsentationen – das heißt, sie weisen jedem Knoten ein Intervall (beziehungsweise einen Kreisbogen) zu, sodass diese sich genau dann schneiden, wenn die zugehörigen Knoten benachbart sind, und isomorphe Eingabegraphen das gleiche Intervallmodell (beziehungsweise Kreisbogenmodell) erhalten. Außerdem werden auch Logspace-Algorithmen angegeben, die Intervallrepräsentationen mit zusätzlichen Eigenschaften berechnen – oder erkennen, dass dies nicht möglich ist: Für die resultierenden Intervallmodelle kann gefordert werden, dass sie proper sind (also kein Intervall ein anderes enthält), dass sie unit sind (also alle Intervalle die gleiche Länge haben) oder dass die Längen der paarweisen Schnitte (und optional der einzelnen Intervalle) vorgegebenen Werten entsprechen. / The graph isomorphism problem deals with the question if two graphs have the same structure up to renaming their vertices. It is one of the few remaining natural problems for which neither a polynomial-time algorithm nor NP-hardness is known. This situation has led to a branch of research that develops efficient algorithms for special cases of the graph isomorphism problem, where the input graphs are required to be from restricted graph classes. The main contribution of this thesis comprises of logspace algorithms that solve the isomorphism problem for k-trees, interval graphs, Helly circular-arc graphs and proper circular-arc graphs. This improves previously known parallel algorithms and leads to a complete classification of the complexity of these problems, as they are also shown to be hard for logspace. In fact, these algorithms achieve more: In the case of k-trees, the algorithm computes canonical labelings in space O(k log n). An alternative implementation runs in time O((k+1)!n), where n is the number of vertices, yielding the fastest known FPT algorithm for k-tree isomorphism. The algorithms for interval and circular-arc graphs actually compute canonical representations, i.e., each vertex is assigned an interval (or arc) such that these intersect each other if and only if the corresponding vertices are adjacent, and isomorphic input graphs receive the same interval (or arc) model. This thesis also presents logspace algorithms that compute interval representations with additional properties, or detect that this is not possible: The resulting interval models can be required to be proper (no interval contains another), unit (all intervals have the same length), or to satisfy prescribed lengths for pairwise intersections (and possibly prescribed lengths of intervals).

Gesten sind ein Kommunikationsweg, der einem Betrachter Informationen oder Absichten übermittelt. Daher können sie effektiv in der Mensch-Roboter-Interaktion, oder in der Mensch-Maschine-Interaktion allgemein, verwendet werden. Sie stellen eine Möglichkeit für einen Roboter oder eine Maschine dar, um eine Bedeutung abzuleiten. Um Gesten intuitiv benutzen zukönnen und Gesten, die von Robotern ausgeführt werden, zu verstehen, ist es notwendig, Zuordnungen zwischen Gesten und den damit verbundenen Bedeutungen zu definieren -- ein Gestenvokabular. Ein Menschgestenvokabular definiert welche Gesten ein Personenkreis intuitiv verwendet, um Informationen zu übermitteln. Ein Robotergestenvokabular zeigt welche Robotergesten zu welcher Bedeutung passen. Ihre effektive und intuitive Benutzung hängt von Gestenerkennung ab, das heißt von der Klassifizierung der Körperbewegung in diskrete Gestenklassen durch die Verwendung von Mustererkennung und maschinellem Lernen. Die vorliegende Dissertation befasst sich mit beiden Forschungsbereichen. Als eine Voraussetzung für die intuitive Mensch-Roboter-Interaktion wird zunächst ein Aufmerksamkeitsmodell für humanoide Roboter entwickelt. Danach wird ein Verfahren für die Festlegung von Gestenvokabulare vorgelegt, das auf Beobachtungen von Benutzern und Umfragen beruht. Anschliessend werden experimentelle Ergebnisse vorgestellt. Eine Methode zur Verfeinerung der Robotergesten wird entwickelt, die auf interaktiven genetischen Algorithmen basiert. Ein robuster und performanter Gestenerkennungsalgorithmus wird entwickelt, der auf Dynamic Time Warping basiert, und sich durch die Verwendung von One-Shot-Learning auszeichnet, das heißt durch die Verwendung einer geringen Anzahl von Trainingsgesten. Der Algorithmus kann in realen Szenarien verwendet werden, womit er den Einfluss von Umweltbedingungen und Gesteneigenschaften, senkt. Schließlich wird eine Methode für das Lernen der Beziehungen zwischen Selbstbewegung und Zeigegesten vorgestellt. / Gestures consist of movements of body parts and are a mean of communication that conveys information or intentions to an observer. Therefore, they can be effectively used in human-robot interaction, or in general in human-machine interaction, as a way for a robot or a machine to infer a meaning. In order for people to intuitively use gestures and understand robot gestures, it is necessary to define mappings between gestures and their associated meanings -- a gesture vocabulary. Human gesture vocabulary defines which gestures a group of people would intuitively use to convey information, while robot gesture vocabulary displays which robot gestures are deemed as fitting for a particular meaning. Effective use of vocabularies depends on techniques for gesture recognition, which considers classification of body motion into discrete gesture classes, relying on pattern recognition and machine learning. This thesis addresses both research areas, presenting development of gesture vocabularies as well as gesture recognition techniques, focusing on hand and arm gestures. Attentional models for humanoid robots were developed as a prerequisite for human-robot interaction and a precursor to gesture recognition. A method for defining gesture vocabularies for humans and robots, based on user observations and surveys, is explained and experimental results are presented. As a result of the robot gesture vocabulary experiment, an evolutionary-based approach for refinement of robot gestures is introduced, based on interactive genetic algorithms. A robust and well-performing gesture recognition algorithm based on dynamic time warping has been developed. Most importantly, it employs one-shot learning, meaning that it can be trained using a low number of training samples and employed in real-life scenarios, lowering the effect of environmental constraints and gesture features. Finally, an approach for learning a relation between self-motion and pointing gestures is presented.

Die Theorie disjunkter NP-Paare, die auf natürliche Weise statt einzelner Sprachen Paare von NP-Mengen zum Objekt ihres Studiums macht, ist vor allem wegen ihrer Anwendungen in der Kryptografie und Beweistheorie interessant. Im Zentrum dieser Dissertation steht die Analyse der Beziehung zwischen disjunkten NP-Paaren und aussagenlogischen Beweissystemen. Haben die Anwendungen der NP-Paare in der Beweistheorie maßgeblich das Verständnis aussagenlogischer Beweissysteme gefördert, so beschreiten wir in dieser Arbeit gewissermaßen den umgekehrten Weg, indem wir Methoden der Beweistheorie zur genaueren Untersuchung des Verbands disjunkter NP-Paare heranziehen. Insbesondere ordnen wir jedem Beweissystem P eine Klasse DNPP(P) von NP-Paaren zu, deren Disjunktheit in dem Beweissystem P mit polynomiell langen Beweisen gezeigt werden kann. Zu diesen Klassen DNPP(P) zeigen wir eine Reihe von Resultaten, die illustrieren, dass robust definierten Beweissystemen sinnvolle Komplexitätsklassen DNPP(P) entsprechen. Als wichtiges Hilfsmittel zur Untersuchung aussagenlogischer Beweissysteme und der daraus abgeleiteten Klassen von NP-Paaren benutzen wir die Korrespondenz starker Beweissysteme zu erststufigen arithmetischen Theorien, die gemeinhin unter dem Schlagwort beschränkte Arithmetik zusammengefasst werden. In der Praxis trifft man statt auf zwei häufig auf eine größere Zahl konkurrierender Bedingungen. Daher widmen wir uns der Erweiterung der Theorie disjunkter NP-Paare auf disjunkte Tupel von NP-Mengen. Unser Hauptergebnis in diesem Bereich besteht in der Charakterisierung der Fragen nach der Existenz optimaler Beweissysteme und vollständiger NP-Paare mit Hilfe disjunkter Tupel. / Disjoint NP-pairs are an interesting complexity theoretic concept with important applications in cryptography and propositional proof complexity. In this dissertation we explore the connection between disjoint NP-pairs and propositional proof complexity. This connection is fruitful for both fields. Various disjoint NP-pairs have been associated with propositional proof systems which characterize important properties of these systems, yielding applications to areas such as automated theorem proving. Further, conditional and unconditional lower bounds for the separation of disjoint NP-pairs can be translated to results on lower bounds to the length of propositional proofs. In this way disjoint NP-pairs have substantially contributed to the understanding of propositional proof systems. Conversely, this dissertation aims to transfer proof-theoretic knowledge to the theory of NP-pairs to gain a more detailed understanding of the structure of the class of disjoint NP-pairs and in particular of the NP-pairs defined from propositional proof systems. For a proof system P we introduce the complexity class DNPP(P) of all disjoint NP-pairs for which the disjointness of the pair is efficiently provable in the proof system P. We exhibit structural properties of proof systems which make the previously defined canonical NP-pairs of these proof systems hard or complete for DNPP(P). Moreover, we demonstrate that non-equivalent proof systems can have equivalent canonical pairs and that depending on the properties of the proof systems different scenarios for DNPP(P) and the reductions between the canonical pairs exist. As an important tool for our investigation we use the connection of propositional proof systems and disjoint NP-pairs to theories of bounded arithmetic.

Peer-Daten-Management-Systeme (PDMS) bestehen aus einer hochdynamischen Menge heterogener, autonomer Peers. Die Peers beantworten Anfragen einerseits gegen lokal gespeicherte Daten und reichen sie andererseits nach einer Umschreibung anhand von Schema-Mappings an benachbarte Peers weiter. Solche aufgrund fehlender zentraler Komponenten eigentlich hoch- flexiblen Systeme leiden bei zunehmender Anzahl von Peers unter erheblichen Effi- zienzproblemen. Die Gründe hierfür liegen in der massiven Redundanz der Pfade im Netzwerk der Peers und im Informationsverlust aufgrund von Projektionen entlang von Mapping-Pfaden. Anwender akzeptieren in hochskalierten Umgebungen zum Datenaustausch in vielen Anwendungsszenarien Konzessionen an die Vollständigkeit der Anfrageergebnisse. Unser Ansatz sieht in der Vollständigkeit ein Optimierungsziel und verfolgt einen Kompromiß zwischen Nutzen und Kosten der Anfragebearbeitung. Hierzu schlagen wir mehrere Strategien für Peers vor, um zu entscheiden, an welche Nachbar-Peers Anfragen weitergeleitet werden. Peers schließen dabei Mappings von der Anfragebearbeitung aus, von denen sie ein geringes Verhältnis von Ergebnisgröße zu Kosten, also geringe Effizienz erwarten. Als Basis dieser Schätzungen wenden wir selbstadaptive Histogramme über die Ergebniskardinalität an und weisen nach, daß diese in dieser hochdynamischen Umgebung ausreichende Genauigkeit aufweisen. Wir schlagen einen Kompromiß zwischen der Nutzung von Anfrageergebnissen zur Anpassung dieser Metadaten-Statistiken und der Beschneidung von Anfrageplänen vor, um den entsprechenden Zielkonflikt aufzulösen. Für eine Optimierungsstrategie, die das für die Anfragebearbeitung verwendete Zeit-Budget limitiert, untersuchen wir mehrere Varianten hinsichtlich des Effizienzsteigerungspotentials. Darüber hinaus nutzen wir mehrdimensionale Histogramme über die Überlappung zweier Datenquellen zur gezielten Verminderung der Redundanz in der Anfragebearbeitung. / Peer data management systems (PDMS) consist of a highly dynamic set of autonomous, heterogeneous peers connected with schema mappings. Queries submitted at a peer are answered with data residing at that peer and by passing the queries to neighboring peers. PDMS are the most general architecture for distributed integrated information systems. With no need for central coordination, PDMS are highly flexible. However, due to the typical massive redundancy in mapping paths, PDMS tend to be very inefficient in computing the complete query result as the number of peers increases. Additionally, information loss is cumulated along mapping paths due to selections and projections in the mappings. Users usually accept concessions on the completeness of query answers in large-scale data sharing settings. Our approach turns completeness into an optimization goal and thus trades off benefit and cost of query answering. To this end, we propose several strategies that guide peers in their decision to which neighbors rewritten queries should be sent. In effect, the peers prune mappings that are expected to contribute few data. We propose a query optimization strategy that limits resource consumption and show that it can drastically increase efficiency while still yielding satisfying completeness of the query result. To estimate the potential data contribution of mappings, we adopted self-tuning histograms for cardinality estimation. We developed techniques that ensure sufficient query feedback to adapt these statistics to massive changes in a PDMS. Additionally, histograms can serve to maintain statistics on data overlap between alternative mapping paths. Building on them, redundant query processing is reduced by avoiding overlapping areas of the multi-dimensional data space.

Inhalt der Dissertation ist die Untersuchung der Evolutionsprozesse zufälliger diskreter Strukturen. Solche Evolutionsprozesse lassen sich üblicherweise wie folgt beschreiben. Anfangs beginnt man mit einer sehr einfachen Struktur (z.B. dem Graphen auf n Ecken, der keine Kanten hat) und einer Menge von ``Bausteinen'' (z.B. der Kantenmenge des vollständigen Graphen auf n Ecken). Mit zunehmender Zeit werden zufällig mehr und mehr Bausteine eingefügt. Die grundlegende Frage, mit der sich diese Dissertation beschäftigt, ist die folgende: Wie sieht zu einem gegebenen Zeitpunkt die durch den Prozess erzeugte Struktur mit hoher Wahrscheinlichkeit aus? Obwohl das Hauptthema der Dissertation die Evolution zufälliger diskreter Strukturen ist, lassen sich die erzielten Ergebnisse auch unter den folgenden Gesichtspunkten zusammenfassen: Zufällige Greedy-Algorithmen: Es wird ein zufälliger Greedy-Algorithmus untersucht, der für einen gegebenen Graphen H einen zufälligen H-freien Graphen erzeugt. Extremale Ergebnisse: Es wird die Existenz von Graphen mit hoher Taillenweite und hoher chromatischer Zahl bewiesen, wobei bestehende Schranken verbessert werden. Asymptotische Enumeration: Es werden präzise asymptotische Schranken für die Anzahl dreiecksfreier Graphen mit n Ecken und m Kanten bewiesen. ``Probabilistische'' Versionen klassischer S"atze: Es wird eine probabilistische Version des Satzes von Sperner bewiesen. / In this thesis, we study the evolution of random discrete structures. Such evolution processes usually fit into the following general framework. Initially (say at time 0), we start with a very simple structure (e.g. a graph on n vertices with no edges) and a set of ``building blocks'' (e.g. the set of edges of the complete graph on n vertices). As time increases, we randomly add more and more elements from our set of building blocks. The basic question which we shall investigate is the following: what are the likely properties of the random structure produced by the process at any given time? Although this thesis is concerned with the evolution of random discrete structures, the results obtained can also be summarized according to the following keywords: Random greedy algorithms: we study the output of a random greedy algorithm which, for a given graph H, produces a random H-free graph. Extremal results: improving on previous bounds, we prove the existence of graphs with high girth and high chromatic number. Asymptotic enumeration: we prove sharp asymptotic bounds on the number of triangle-free graphs with n vertices and m edges for a large range of m. Probabilistic versions of ``classical'' theorems: we prove a probabilistic version of Sperner's theorem on finite sets.