Search

Energy conservation is a major concern in todays data centers, which are the 21st century data processing factories, and where large and complex software systems such as distributed data management stores run and serve billions of users. The two main drivers of this major concern are the pollution impact data centers have on the environment due to their waste heat, and the expensive cost data centers incur due to their enormous energy demand. Among the many subsystems of data centers, the storage system is one of the main sources of energy consumption. Among the many types of storage systems, key/value stores happen to be the widely used in the data centers. In this work, I investigate energy saving techniques that enable a consistent hash based key/value store save energy during low activity times, and whenever there is an opportunity to reuse the waste heat of data centers.

We present simple deterministic algorithms for subgraph finding and enumeration in the broadcast CONGEST model of distributed computation: -- For any constant $k$, detecting $k$-paths and trees on $k$ nodes can be done in $O(1)$ rounds. -- For any constant $k$, detecting $k$-cycles and pseudotrees on $k$ nodes can be done in $O(n)$ rounds. -- On $d$-degenerate graphs, cliques and $4$-cycles can be enumerated in $O(d + \log n)$ rounds, and $5$-cycles in $O(d^2 + \log n)$ rounds. In many cases, these bounds are tight up to logarithmic factors. Moreover, we show that the algorithms for $d$-degenerate graphs can be improved to optimal complexity $O(d/\log n)$ and $O(d^2/\log n)$, respectively, in the supported CONGEST model, which can be seen as an intermediate model between CONGEST and the congested clique.

The design of microprocessors is undergoing radical changes that affect the performance and reliability of hardware and will have a high impact on software development. Future systems will depend on a deep collaboration between software and hardware to cope with the current and predicted system design challenges. Instead of higher frequencies, the number of processor cores per chip is growing. Eventually, processors will be composed of cores that run at different speeds or support specialized features to accelerate critical portions of an application. Performance improvements of software will only result from increasing parallelism and introducing asymmetric processing. At the same time, substantial enhancements in the energy efficiency of hardware are required to make use of the increasing transistor density. Unfortunately, the downscaling of transistor size and power will degrade the reliability of the hardware, which must be compensated by software. In this thesis, we present new algorithms and tools that exploit speculative and asymmetric execution to address the performance and reliability challenges of multicore architectures. Our solutions facilitate both the assimilation of software to the changing hardware properties as well as the adjustment of hardware to the software it executes. We use speculation based on transactional memory to improve the synchronization of multi-threaded applications. We show that shared memory synchronization must not only be scalable to large numbers of cores but also robust such that it can guarantee progress in the presence of hardware faults. Therefore, we streamline transactional memory for a better throughput and add fault tolerance mechanisms with a reduced overhead by speculating optimistically on an error-free execution. If hardware faults are present, they can manifest either in a single event upset or crashes and misbehavior of threads. We address the former by applying transactions to checkpoint and replicate the state such that threads can correct and continue their execution. The latter is tackled by extending the synchronization such that it can tolerate crashes and misbehavior of other threads. We improve the efficiency of transactional memory by enabling a lightweight thread that always wins conflicts and significantly reduces the overheads. Further performance gains are possible by exploiting the asymmetric properties of applications. We introduce an asymmetric instrumentation of transactional code paths to enable applications to adapt to the underlying hardware. With explicit frequency control of individual cores, we show how applications can expose their possibly asymmetric computing demand and dynamically adjust the hardware to make a more efficient usage of the available resources.

The Doctoral Workshop on Distributed Systems has been held at Kandersteg, Switzerland, from June 3-5, 2014. Ph.D. students from the Universities of Neuchâtel and Bern as well as the University of Applied Sciences of Fribourg presented their current research work and discussed recent research results. This technical report includes the extended abstracts of the talks given during the workshop.

Exploiting thread-level parallelism has become a part of mainstream programming in recent years. Many approaches to parallelization require threads executing in parallel to also synchronize occassionally (i.e., coordinate concurrent accesses to shared state). Transactional Memory (TM) is a programming abstraction that provides the concept of database transactions in the context of programming languages such as C/C++. This allows programmers to only declare which pieces of a program synchronize without requiring them to actually implement synchronization and tune its performance, which in turn makes TM typically easier to use than other abstractions such as locks. I have investigated and implemented the building blocks that are required for a high-performance, practical, and realistic TM. They host several novel algorithms and optimizations for TM implementations, both for current hardware and future hardware extensions for TM, and are being used in or have influenced commercial TM implementations such as the TM support in GCC.

International audience; Nous étudions la diffusion massive de contenus en déplaçant une partie du trafic du réseau d'infrastructure 3G vers un réseau opportuniste sans pour autant sacrifier la fiabilité. Dans ce papier, nous étudions un modèle de propagation de messages dans un réseau opportuniste afin de pouvoir prédire l'évolution de la prochaine propagation et calculer le nombre optimal de copies à injecter dans le réseau au début d'une diffusion.

International audience; A self-stabilizing protocol has the capacity to recover a legitimate behavior whatever is its initial state. The majority of works in self-stabilization assume a shared memory model or a communication using reliable and FIFO channels. In this article, we interest in self-stabilizing systems using bounded but non reliable and non FIFO channels. We propose a stabilizing communication protocol with optimal fault resilience. In more details, this protocol simulates a reliable and FIFO channel and ensures a minimal number of looses, duplications, creations, and re-ordering of messages.; Un protocole auto-stabilisant a la capacité de converger vers un comportement correct quel que soit son état initial. La grande majorité des travaux en auto-stabilisation supposent une communication par mémoire partagée ou bien à travers des canaux de communication fiables et FIFO. Dans cet article, nous nous intéressons aux systèmes auto-stabilisants à passage de messages à travers des canaux de capacité bornée mais non fiables et non FIFO. Nous proposons un protocole de communication (entre voisins) stabilisant et offrant une tolérance optimale. Plus précisèment, ce protocole simule un canal de communication fiable et FIFO garantissant un nombre minimal de pertes, de duplications, de créations et de ré-ordonnancements de messages.

Ensemble des communications d'ALGOTEL 2011 : http://hal.inria.fr/ALGOTEL2011/fr/; International audience; La construction d'un objet partagé entre plusieurs processus nécessite la résolution du consensus. De ce fait, la résolution du consensus est un sujet central et récurrent dans le domaine des systèmes répartis. Dans un article récent, L. Lamport suggère de prendre en compte la commutativité des accès concurrents à un objet partagé afin d'améliorer la vitesse de résolution du consensus. Cet article introduit notamment Generalized Paxos, un algorithme qui résout le consensus dans les systèmes répartis par passage de messages en deux étapes de communication si les accès concurrents sont commutatifs ou spontanément ordonnés par le réseau. Toutefois, si une collision se produit, c'est à dire que deux accès concurrents et non-commutatifs ont lieu, Generalized Paxos exécute quatre étapes de communication supplémentaires. L'algorithme devient alors moins performant que les solutions classiques. Dans cet article nous décrivons une nouvelle solution au consensus généralisé: FGGC. FGGC est optimal au regard des fautes et de la vitesse d'exécution car: (i) pour tolérer f pannes franches, FGGC utilise 2f+1 processus, (ii) si toutes les commandes sont commutatives, ou spontanément ordonnées par le réseau, FGGC résout le consensus en deux étapes de communication, (iii) les collisions sont résolues en une seule étape de communication, et (iv) FGGC utilise seulement f+1 processus pour progresser.

International audience; Compact routing schemes address the fundamental tradeoff between the memory space required to store the routing table entries and the length of the routing paths they produce. This paper introduces a dynamic compact routing scheme that allows the distribution of traffic from any source to any set of leaf nodes along a point-to-multipoint routing path referred to as multicast (traffic) distribution tree. By means of the proposed scheme, a multicast distribution tree can dynamically evolve according to the arrival of leaf-initiated join/leave requests. We evaluate by means of simulation the performance of the proposed scheme and analyze the tradeoffs between the stretch of the produced routing paths, the size and the number of routing table entries, and the communication cost.

International audience; L'arbre couvrant de poids minimum offre une solution de routage ayant le double avantage de donner une structure de communication simple et économique. Dans ce papier, nous présentons un nouvel algorithme auto-stabilisant pour la construction d'un arbre couvrant de poids minimum dans un système distribué et asynchrone. Notre solution améliore l'existant en permettant d'atteindre un meilleur compromis entre le temps de convergence, $O(n^2)$, et la complexité en mémoire nécessaire sur chaque noeud du réseau, $O(\log^2 n)$. Le temps de convergence est amélioré d'un facteur multiplicatif $\Theta(n)$ au prix d'un facteur multiplicatif de $O(\log n)$ sur la mémoire. La clé de voûte de ce travail est l'utilisation d'une méthode de nommage auto-stabilisante permettant d'identifier pour toute paire de noeuds le plus proche ancêtre commun dans l'arbre.

International audience; Les modèles de Yield management ou revenue management ont connu un grand succès auprès des compagnies aériennes. Peu de travaux de recherche ont porté sur les télécommunications. Cet article traite d'un nouveau problème de maximisation des revenus d'un opérateur de télécommunications en optimisant les prix de ses services. Une stratégie tarifaire dynamique en fonction du taux d'occupation des ressources est adoptée. Un modèle de programmation entière mixte est utilisé pour formaliser le problème. Des résultats numériques préliminaires qui montrent la difficulté du problème sont présentés.

International audience; Cet article est consacré à la vérification basée sur le modèle model-checking du modèle des protocoles de population introduit par Angluin et al.~\cite{AngluinADFP2006}. Ces deux dernières années, la vérification des protocoles de population par model-checking a fait l'objet denombreuses études et de nouveaux outils ont été proposés. Nous montrons dans cet article que, dans une certaine mesure, les outils classiques de model-checking tels que Spin et Prism peuvent être utilisés pour effectuer les vérifications. Pour cela, nous appliquons la technique d'abstraction par comptage pour obtenir des modèles abstraits de protocoles de population qui peuvent être vérifiés efficacement par les outils de model-checking existants. Le problème essentiel pour la complexité de la vérification des protocoles de population concerne la condition d'équité forte. Cette dernière ne peut être utilisée directement avec Spin même pour des exemples de relativement petite taille. Nous montrons qu'on peut cependant remplacer dans de nombreux cas cette équité par une équité faible efficacement vérifiable en Spin. Plus notable encore, nous montrons que la vérification avec la condition d'équité forte est équivalente à un problème de vérification d'un modèle probabiliste. Ainsi, le model-checker probabiliste Prism s'avère être un outil de vérification adapté aux protocoles de population.

International audience; Nous étudions le problème d'optimisation énergétique dans les réseaux sans fil fixes dans le cas d'une faible demande de trafic par rapport à la capacité du réseau. Nous proposons un programme linéaire pour résoudre le problème, puis nous présentons une heuristique permettant de trouver rapidement une bonne solution.

International audience; Dans cet article, nous nous intéressons aux plates-formes de grande échelle comme BOINC, qui sont constituées d'un ensemble de ressources hétérogènes utilisant Internet comme réseau de communication. Dans ce contexte, nous étudions un problème d'agrégation de ressources dans lequel l'objectif est de construire des groupes de ressources, de telle sorte que chaque groupe ait une capacité totale supérieure à une certaine valeur, et tels qu'au sein d'un même groupe, deux ressources ne soient pas trop éloignées (en terme de latence) l'une de l'autre. Dans de telles plateformes, il n'est pas réaliste de supposer connaître la latence pour l'intégralité des couples de noeuds. Il est donc nécessaire d'avoir recours à des outils de plongement comme Vivaldi ou Sequoia. Ces outils permettent de travailler dans des espaces métriques spécifiques et dans lesquels la distance entre deux noeuds peut être obtenue directement à partir d'une petite quantité d'informations disponible à chaque noeud. Nous étudions le problème "Bin Covering" avec Contrainte de Distance (BCCD) et utilisons des algorithmes dédiés dans les espaces métriques induits par plusieurs outils de plongement pour proposer une comparaison de ces algorithmes en nous appuyant sur des mesures de latences réelles. Cette comparaison nous permet de décider quel couple (algorithme,outil de plongement) est en pratique le plus efficace pour ce problème d'agrégation de ressources.

International audience; AreaCast est un mécanisme d'adressage logique dans un voisinage visant à améliorer la robustesse à tout type de protocole unicast. AreaCast se base sur la notion de relai implicite tandis que le relayage unicast se base sur le choix explicite du relais. Tout en étant indépendant du protocole de routage choisi, AreaCast utilise des informations topologiques et de routage pour permettre une communication par zone : un nœud relai explicite choisi comme prochain saut par la couche routage et k nœuds relais implicites qui s'auto-sélectionnent en fonction de leur proximité au nœud relai explicite. Ce mécanisme utilise la "sur-écoute" pour exploiter la communication de type "broadcast" inhérente aux transmissions sans fil. Sans changer le protocole de routage ni échange de paquets supplémentaires, AreaCast permet de contourner dynamiquement un nœud défectueux ou un lien instable. Les résultats de simulation, modélisant finement la consommation énergétique, montrent qu'AreaCast améliore significativement le taux de livraison tout en étant un bon compromis entre efficacité et consommation énergétique.

International audience; Les réseaux mobiles LTE de quatrième génération (Long Term Evolution) sont considérés comme la principale solution pour les télécommunications futures. Une des caractéristiques spécifiques de l'architecture de ces nouveaux réseaux réside dans le fait que deux stations de bases voisines sont directement reliées par un lien logique appelé "X2", lien permettant de transférer les données de l'utilisateur durant le processus de handover. D'un autre côté, chaque station de base est également reliée au réseau coeur via un lien appelé "S1". Le but de ce papier est de quantifier l'impact de la mobilité des utilisateurs sur le lien X2. Grâce à un modèle analytique, nous en déduisons alors des règles simples et robustes de dimensionnement. Par ailleurs, la relation entre les liens X2 et S1 sera étudiée, cette dernière ayant une importance pratique du point de vue des planificateurs du réseau.

We consider Kleinberg's celebrated small-world model (2000). This model is based on a d-dimensional grid graph of n nodes, augmented by a constant number of ''long-range links'' per node. It is known that this graph has diameter Θ(log n), and that a simple greedy search algorithm visits an expected number of O(log^2 n) nodes, which is asymptotically optimal over all decentralized search algorithms. Besides the number of nodes visited, a relevant measure is the length of the path constructed by the search algorithm. A decentralized algorithm by Lebhar and Schabanel (2003) constructs paths of expected length O(log n * (loglog n)^2) by visiting the same number of nodes as greedy search. A natural question, posed by Kleinberg (2006), is whether there are decentralized algorithms that construct paths of length O(log n) while visiting only a poly-logarithmic number of nodes. In this paper we resolve this question. For grid dimension d=1, we answer the question in the negative, by showing that any decentralized algorithm that visits a poly-logarithmic number of nodes constructs paths of expected length Ω(log n * loglog n). Further we show that this bound is tight; a simple variant of the algorithm by Lebhar and Schabanel matches this bound. For dimension d ≥ 2, however, we answer the question in the affirmative; the bound is achieved by essentially the same algorithm we used for d=1. This is the first time that such a dichotomy, based on the dimension d, has been observed for an aspect of this model. Our results may be applicable to the design of peer-to-peer networks, where the length of the path along which data are transferred is critical for the network's performance., Dans cet article, nous apporterons une réponse exacte (asymptotiquement) et surprenante à une question ouverte depuis plusieurs années dans le domaine de la modélisation des comportements sociaux: est-il possible de naviguer dans un graphe petit-monde de Kleinberg en temps optimal ? C'est-à-dire, est-il possible de suivre un chemin optimal d'un point à un autre en utilisant seulement les informations disponibles localement. Cette question a clairement des applications dans le design de tables de routage et de protocoles pair-à-pair. La réponse que nous apportons est la suivante: si la dimension sous-jacente du graphe petit-monde est 1, la réponse est non, les chemins optimaux sont de longueur Θ(log n) alors que le mieux que l'on puisse faire à partir des informations locales est Θ(log n * loglog n); lorsque la dimension sous-jacente est ≥ 2, on démontre qu'un simple algorithme de parcours en largeur réussit à naviguer optimalement.

International audience; Les réseaux de capteurs sont utilisés afin de collecter un grand nombre de données de l'environnement. Ces données sont délivrées au travers de l'interface de communication sans fil des capteurs par des communications multi-sauts jusqu'au puits traitant l'information. Le placement de ce puits influe sur les performances des réseaux de capteurs en ce qui concerne le délai et la consommation énergétique, en particulier celle des capteurs intermédiaires servant de relais. L'optimisation de la collecte des données est donc un aspect important dans l'étude des réseaux de capteurs sans fil. Notre article s'intéresse à la collecte de données utilisant des puits mobiles. Nous proposons un modèle permettant d'étudier le compromis entre la consommation énergétique du réseau et le délai de collecte des données.

International audience; Le problème de déploiement optimal d'un réseau FTTH (Fiber To The Home) consiste à concevoir un plan d'installation de fibres optiques de coût minimal permettant de connecter un ensemble de clients à un noeud de raccordement via un ensemble de coupleur. Nous présentons une modélisation de ce problème basée sur le concept de flot avec multiplicateurs et nous montrons comment obtenir par génération de colonnes une solution optimale fractionnaire du programme linéaire correspondant. Cette approche nécessite de résoudre à chaque itération un problème de plus court chemin généralisé multi-contraint. Pour cela, nous décrivons un algorithme pseudo-polynomial qui généralise au cas avec multiplicateurs l'algorithme de plus court chemin multi-contraint introduit dans [DS88].

International audience; Dans cet article, nous étudions le problème joint du routage et de l'ordonnancement dans les réseaux radio maillés où la demande des utilisateurs est incertaine. Nous présentons un modèle d'optimisation robuste basé sur le prix de la robustesse qui permet d'ajuster le niveau de conservatisme de la solution robuste.

Mesurer avec pr\'ecision la dynamique des graphes de terrain est une t\^ache difficile, car les propri\'et\'es observ\'ees peuvent \^etre biais\'ees pour diff\'erentes raisons, en particulier le fait que la p\'eriode de mesure soit finie. Dans ce papier, nous introduisons une m\'ethodologie g\'en\'erale qui nous permet de savoir si la fen\^etre d'observation est suffisamment longue pour caract\'eriser une propri\'et\'e donn\'ee dans n'importe quel syst\`eme dynamique. Nous appliquons cette m\'ethodologie \`a l'\'etude des dur\'ees de sessions et des dur\'ees de vie des fichiers sur deux jeux de donn\'ees P2P. Nous montrons que le comportement des propri\'et\'es est diff\'erent : pour les dur\'ees de sessions, notre m\'ethodologie nous permet de caract\'eriser avec pr\'ecision la forme de leur distribution. Par contre, pour les dur\'ees de vie des fichiers, nous montrons que cette propri\'et\'e ne peut pas \^etre caract\'eris\'ee, soit parce qu'elle n'est pas stationnaire, soit parce que la dur\'ee de notre mesure est trop courte.

Event stream processing (ESP) applications enable the real-time processing of continuous flows of data. Algorithmic trading, network monitoring, and processing data from sensor networks are good examples of applications that traditionally rely upon ESP systems. In addition, technological advances are resulting in an increasing number of devices that are network enabled, producing information that can be automatically collected and processed. This increasing availability of on-line data motivates the development of new and more sophisticated applications that require low-latency processing of large volumes of data. ESP applications are composed of an acyclic graph of operators that is traversed by the data. Inside each operator, the events can be transformed, aggregated, enriched, or filtered out. Some of these operations depend only on the current input events, such operations are called stateless. Other operations, however, depend not only on the current event, but also on a state built during the processing of previous events. Such operations are, therefore, named stateful. As the number of ESP applications grows, there are increasingly strong requirements, which are often difficult to satisfy. In this dissertation, we address two challenges created by the use of stateful operations in a ESP application: (i) stateful operators can be bottlenecks because they are sensitive to the order of events and cannot be trivially parallelized by replication; and (ii), if failures are to be tolerated, the accumulated state of an stateful operator needs to be saved, saving this state traditionally imposes considerable performance costs. Our approach is to evaluate the use of speculation to address these two issues. For handling ordering and parallelization issues in a stateful operator, we propose a speculative approach that both reduces latency when the operator must wait for the correct ordering of the events and improves throughput when the operation in hand is parallelizable. In addition, our approach does not require that user understand concurrent programming or that he or she needs to consider out-of-order execution when writing the operations. For fault-tolerant applications, traditional approaches have imposed prohibitive performance costs due to pessimistic schemes. We extend such approaches, using speculation to mask the cost of fault tolerance.:1 Introduction 1 1.1 Event stream processing systems ......................... 1 1.2 Running example ................................. 3 1.3 Challenges and contributions ........................... 4 1.4 Outline ...................................... 6 2 Background 7 2.1 Event stream processing ............................. 7 2.1.1 State in operators: Windows and synopses ............................ 8 2.1.2 Types of operators ............................ 12 2.1.3 Our prototype system........................... 13 2.2 Software transactional memory.......................... 18 2.2.1 Overview ................................. 18 2.2.2 Memory operations............................ 19 2.3 Fault tolerance in distributed systems ...................................... 23 2.3.1 Failure model and failure detection ...................................... 23 2.3.2 Recovery semantics............................ 24 2.3.3 Active and passive replication ...................... 24 2.4 Summary ..................................... 26 3 Extending event stream processing systems with speculation 27 3.1 Motivation..................................... 27 3.2 Goals ....................................... 28 3.3 Local versus distributed speculation ....................... 29 3.4 Models and assumptions ............................. 29 3.4.1 Operators................................. 30 3.4.2 Events................................... 30 3.4.3 Failures .................................. 31 4 Local speculation 33 4.1 Overview ..................................... 33 4.2 Requirements ................................... 35 4.2.1 Order ................................... 35 4.2.2 Aborts................................... 37 4.2.3 Optimism control ............................. 38 4.2.4 Notifications ............................... 39 4.3 Applications.................................... 40 4.3.1 Out-of-order processing ......................... 40 4.3.2 Optimistic parallelization......................... 42 4.4 Extensions..................................... 44 4.4.1 Avoiding unnecessary aborts ....................... 44 4.4.2 Making aborts unnecessary........................ 45 4.5 Evaluation..................................... 47 4.5.1 Overhead of speculation ......................... 47 4.5.2 Cost of misspeculation .......................... 50 4.5.3 Out-of-order and parallel processing micro benchmarks ........... 53 4.5.4 Behavior with example operators .................... 57 4.6 Summary ..................................... 60 5 Distributed speculation 63 5.1 Overview ..................................... 63 5.2 Requirements ................................... 64 5.2.1 Speculative events ............................ 64 5.2.2 Speculative accesses ........................... 69 5.2.3 Reliable ordered broadcast with optimistic delivery .................. 72 5.3 Applications .................................... 75 5.3.1 Passive replication and rollback recovery ................................ 75 5.3.2 Active replication ............................. 80 5.4 Extensions ..................................... 82 5.4.1 Active replication and software bugs ..................................... 82 5.4.2 Enabling operators to output multiple events ........................ 87 5.5 Evaluation .................................... 87 5.5.1 Passive replication ............................ 88 5.5.2 Active replication ............................. 88 5.6 Summary ..................................... 93 6 Related work 95 6.1 Event stream processing engines ......................... 95 6.2 Parallelization and optimistic computing ................................ 97 6.2.1 Speculation ................................ 97 6.2.2 Optimistic parallelization ......................... 98 6.2.3 Parallelization in event processing .................................... 99 6.2.4 Speculation in event processing ..................... 99 6.3 Fault tolerance .................................. 100 6.3.1 Passive replication and rollback recovery ............................... 100 6.3.2 Active replication ............................ 101 6.3.3 Fault tolerance in event stream processing systems ............. 103 7 Conclusions 105 7.1 Summary of contributions ............................ 105 7.2 Challenges and future work ............................ 106 Appendices Publications 107 Pseudocode for the consensus protocol 109

In this thesis I describe my research activities and results of the last 4 years. I also provide an outlook and guidelines on how to proceed with our project, that we named SEDNS - Security-Enhanced Domain Name System. This project’s ambitions are to complement DNS, the Domain Name System, in a way that allows us to keep using it in the future. The main reason for this strategy is, that it has proven to be difficult to change any part of the Internet infrastructure, such as parts of the protocols stack or well established Internet authorities, like ICANN or IANA. The main problems of DNS are twofold. (1) The DNS protocol does not contain any measures to prevent data from being tampered with. (2) Furthermore, it is difficult to configure DNS correctly since most of the configuration is done within the DNS data itself, e.g., delegating authority. It is well known that DNS problems lead to reduced availability of Internet-based services in many different ways. In this thesis, I present four main results. All of them contribute to improvements and deeper understanding of DNS’ dependability issues. First, I discuss, how well established cryptographic tools can be used to enhance DNS’ security without getting into the same problems that prevent DNSSEC from being globally deployed. These problems are explained as well. This is an important topic for the Internet and DNS community, since at the moment most of the protocol improvements are connected to DNSSEC. Second, I thoroughly discuss the technique that was used in the recent years to overcome any problems related to client-server architectures, i.e., peer-to-peer systems. Such solutions have been proposed to improve DNS’ availability and reduce configuration effort. I show, that those systems do not keep up with the expectations, neither as client side tools nor as server infrastructure replacement. To reach this conclusion, a novel DHT scheme has been developed. The evaluation of it is shown as well. Third, results of our DNS data mining show that it is useful to improve the quality of DNS data and therefore, to protect clients from malicious or erroneous information. And fourth, an outlook is presented, which combines all the results of the first three points to suggest an architecture that indeed can improve our supply with DNS data, omitting the shortcomings of the classical client-server-architecture and its peer-to-peer replacements. Note, that although the development of future DNS standards and protocols is subject to political struggle, e.g., on whether or not an international organization should maintain the root zone instead of the USA, this thesis focuses only on technical aspects. In dieser Dissertation beschreibe ich meine Forschungsaktivitäten und Ergebnisse der letzten 4 Jahre. Ich gebe auch einen Ausblick und Hinweise, wie unser Project, das wir SEDNS - Security-Enhanced Domain Name System genannt haben, fortgesetzt werden sollte. Die Ambitionen dieses Projektes sind, DNS, das Domain Name System, zu in einer Art und Weise zu erweitern, die es uns erlauben soll, dieses System auch in der Zukunft weiter zu benutzen. Der Hauptgrund für diese Strategie ist, dass es sich in der Vergangenheit als schwierig erwiesen hat, Teile der Internet-Infrastruktur, wie zum Beispiel Teile des Protokollstapels oder gut etablierte Internet-Behörden wie ICANN oder IANA, zu ändern bzw. auszutauschen. Daher wollen wir nicht versuchen, DNS komplett zu ersetzen. DNS hat zwei Hauptprobleme: (1) Das DNS Protokoll bietet keinerlei Möglichkeiten, Daten vor Verfälschung zu schützen, und (2) es ist schwierig, DNS korrekt zu konfigurieren, weil ein Großteil der Konfiguration direkt innerhalb der DNS Daten selbst stattfindet, wie zum Beispiel die Delegation von Verantwortungsbereichen, und diese oft nicht global konsistent und korrekt sind. Diese Probleme sind umso bedeutender, weil es allgemein bekannt ist, dass DNS Probleme auf verschiedene Art und Weisen zu reduzierter Verfügbarkeit von wichtigen Internet-basierten Diensten führen. In dieser Arbeit präsentiere ich vier Hauptergebnisse. Zuerst diskutiere ich, wie gut etablierte kryptographische Werkzeuge benutzt werden können um die Sicherheit von DNS zu verbessern, ohne dabei auf dieselben Probleme zu stoßen, die DNSSEC davon abhalten, weltweit benutzt zu werden. Diese Probleme werden dabei erläutert. Es handelt sich dabei um ein wichtiges Thema für die Internet- und DNS-Community, weil im Moment die meisten Weiterentwicklungen des DNS Protokolls mit DNSSEC zusammenhängen. Als zweites diskutiere ich im Detail die Technik, die in den vergangenen Jahren benutzt wurde um Probleme beliebiger Client-Server Anwendungen zu überwinden: Peer-to-Peer Systeme. Derartige Lösungen wurden vorgeschlagen, um DNS' Verfügbarkeit zu verbessern und Konfigurationsaufwand zu reduzieren. Ich zeige allerdings, dass solche Lösungen nicht die in sie gesetzten Erwartungen erfüllen, weder als Client-seitige Tools noch als Ersatz für die Server-Infrastruktur. Um diesen Schluss zu ziehen, wurde ein neues, auf die Bedürfnisse von DNS zugeschnittenes DHT Schema entwickelt und evaluiert im Vergleich zu DNS und existierenden Systemen. Als drittes werden DNS Data Mining Ergebnisse präsentiert, die zeigen, wie sinnvoll es ist, die Qualität der DNS Daten zu verbessern, und somit Clients vor bösartigen oder fehlerhaften Informationen zu schützen. Als viertes wird ein Ausblick präsentiert, der die Ergebnisse der vorherigen drei Punkte kombiniert und eine Architektur vorschlägt, die unsere Versorgung mit DNS Daten tatsächlich verbessern kann und die Nachteile der klassischen Client-Server-Architektur und ihrer Peer-to-Peer Nachfolger vermeidet. Zu beachten ist, dass obwohl die Entwicklung zukünftiger DNS Standards und Protokolle Gegenstand politischer Konflikte ist, z.B. darüber ob anstelle der USA eine internationale Organisation die Root-Zone verwalten sollte, diese Arbeit nur auf die technischen Aspekte ausgerichtet ist.