Département d'informatique, Institut d'informatique fondamentale IIF (Laboratoire de systèmes répartis LSR)

Conception and implementation of a toolkit for building fault-tolerant distributed applications in large scale networks

Malloth, Christoph Peter ; Schiper, André (Dir.)

Thèse Ecole polytechnique fédérale de Lausanne EPFL : 1996 ; no 1557.

Ajouter à la liste personnelle
    Summary
    Large scale systems are becoming more and more common today. Many distributed applications are emerging that use the capability of world-wide internetworking. Since many applications require availability and consistency in the presence of failures, an adequate support for fault-tolerance is necessary. This can be provided by different paradigms and their implementations. Unfortunately, most of these implementations consider only local area networks, whereas this thesis describes a system, called Phoenix, which aims at large scale networks where additional types of failure have to be taken into account. This thesis gives a complete description of Phoenix, a toolkit for building fault-tolerant, distributed applications in large scale networks. Fault-tolerance in Phoenix is achieved using replicated process groups, and consistency within one process group is achieved by using view synchronous communication. The particularity of Phoenix is the provision of this fault-tolerance and consistency in a large scale environment, where large scale is two-fold: (1) the wide geographical distribution of the replicated processes, and (2) a high number of participating processes in the system. The description of Phoenix given here is based on its architecture. Each layer of Phoenix focuses on a particular problem and proposes a solution. Lower layers are responsible for the geographical large scale aspects and their problems, whereas higher layers provide high order communication and deal with numerical large scale aspects. In large scale networks, in addition to the increased unpredictable latency of messages, communication protocols have to deal with link failures, which are often only transient. The dynamic routing layer in the Phoenix architecture tries to mask these link failures by rerouting. This rerouting not only gives increased reliability of communication, but also a more stable and accurate image of the reachability of the processes. On top of the dynamic routing layer, the reliable communication layer provides eventually reliable channels, i.e. messages sent are eventually delivered at the destination provided that the sender and the destination processes are correct. This layer takes into account different parameters of large scale networks, such as (1) increased, unpredictable latency, and (2) non-negligible packet desequencing and (3) important packet loss. The consistency among the replicas is based on a new implementation of the virtually synchronous communication paradigm. The implementation is part of the view synchronous communication layer and is based on a modified consensus protocol together with the eventually reliable channels of the reliable communication layer. The modified consensus protocol itself is based on an unstable suspicion model, where incorrectly suspected processes can be considered alive at a later point. This will be exploited to make the protocol alive whenever a majority of replicas can communicate with each other. The situation where a distributed system is cut into smaller subsystems, and none of these subsystems contains a majority, is not uncommon in large scale, but is often only transient. Further, the dynamic routing layer already does a maximum to avoid this situation. Based on the view synchronous communication layer, the ordered multicast communication layer provides different ordering primitives based on solid, theoretical definitions, allowing the implementation of different total and uniform orders. The numerical large scale is considered by assigning different roles to the processes of a distributed system without leaving the context of groups. The idea is to concentrate the fault-tolerant aspect to a small set of core processes, whilst still guaranteeing convenient and efficient access semantics to processes outside these core processes.
    Résumé
    Les systèmes répartis à grande échelle sont de plus en plus courants aujourd'hui, et un grand nombre d'applications exploitent déjà les possibilités des réseaux de communication mondiaux interconnectés. Parmi ces applications, certaines doivent proposer un comportement cohérent en cas de pannes, ainsi qu'une disponibilité permanente nécessitant un support adéquat pour la tolérance aux fautes. Cette tolérance aux fautes peut être fournie par l'intermédiaire de différents paradigmes. Malheureusement, la mise en oeuvre de la plupart de ces paradigmes ne considère que des réseaux locaux, ou affaiblissent considérablement les garanties fournies par le système pour une utilisation à grande échelle. L'originalité du système Phoenix, décrit dans cette thèse, est de tenir compte de la grande échelle et des nouveaux problèmes introduits dans ce contexte, sans affaiblir les garanties. Cette thèse donne une description complète de Phoenix, une boîte à outils conçue pour le développement d'applications réparties tolérantes aux fautes à grande échelle. La tolérance aux fautes est réalisée au moyen de groupes de processus dupliqués, et la cohérence entre les processus d'un groupe est garantie par le paradigme de la communication virtuellement synchrone. La particularité de Phoenix consiste à proposer de la tolérance aux fautes et de la cohérence dans un contexte à grande échelle. La grande échelle est vue à travers les deux dimensions suivantes: (1) la répartition géographique des processus dupliqués, et (2) un grand nombre de processus au niveau de l'application. La description de Phoenix dans cette thèse est basée sur son architecture. Chaque couche de Phoenix se concentre sur un problème particulier et propose une solution. Dans cette architecture, les couches basses sont responsables des aspects liés à la grande échelle géographique, tandis que les couches hautes proposent des primitives d'ordonnancement, ainsi qu'une couche qui s'occupe de la grande échelle du point de vue du nombre de participants. Dans des réseaux à grande échelle, mise à part le délai plus grand et imprévisible de la transmission de messages, un protocole de communication doit également s'occuper des pannes de liens, celles-ci n'étant souvent que de caractère temporaire. La couche de routage dynamique dans l'architecture de Phoenix tente de masquer ces pannes de liens en reroutant des messages. Ce reroutage ne propose pas seulement une communication plus fiable, mais aussi une information plus stable et précise de l'accessibilité d'autres processus. La couche de communication fiable, mise en oeuvre au-dessus de la couche de routage dynamique, propose des canaux finalement fiables, qui assurent qu'un message est reçu par la destination à condition que l'émetteur et le récepteur soient corrects. En plus de la fiabilité, cette couche tient compte des différents paramètres influençant cette fiabilité, comme (1) un délai plus grand et imprévisible, (2) un déséquencement non-négligeable de messages, et (3) la perte importante de paquets. La cohérence des duplicas d'un service est basée sur une nouvelle mise en oeuvre du paradigme de la communication virtuellement synchrone. L'implémentation de ce paradigme est basée sur un protocole de consensus modifié, utilisant les canaux finalement fiables de la couche de communication fiable. Le protocole de consensus modifié se base sur un modèle de suspicion instable, c-à-d un processus qui a été suspecté à tort, peut être reconsidéré correct plus tard. Ceci est exploité par le protocole, garantissant le progrès à une majorité de processus pouvant communiquer. La situation où un système réparti est partitionné en plusieurs sous-systèmes et où aucun des sous-systèmes ne contient une majorité, est possible, mais en général temporaire. La couche de routage dynamique tente d'ailleurs d'éviter au maximum de telles situations. La couche de communication ordonnée propose différentes primitives pour l'ordonnancement de messages. Ces primitives, toutes basées sur la couche de communication virtuellement synchrone, mettent en oeuvre des ordres totaux, uniformes ainsi que des combinaisons des deux. Dans un système à grande échelle, le nombre de participants peut être considérable et sans support adéquat, la vivacité et la performance d'un tel système peut se dégrader rapidement. En affectant différents rôles aux participants, le problème peut être géré de manière efficace. L'idée de base consiste à concentrer les aspects de la tolérance aux fautes sur un petit sous-ensemble de processus, tout en garantissant aux autres processus un accès adéquat et rapide à l'information gérée par le sous-ensemble.