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

Agreement-related problems : from semi-passive replication to totally ordered broadcast

Défago, Xavier ; Schiper, André (Dir.)

Thèse sciences Ecole polytechnique fédérale de Lausanne EPFL : 2000 ; no 2229.

Ajouter à la liste personnelle
    Summary
    Agreement problems constitute a fundamental class of problems in the context of distributed systems. All agreement problems follow a common pattern: all processes must agree on some common decision, the nature of which depends on the specific problem. This dissertation mainly focuses on three important agreements problems: Replication, Total Order Broadcast, and Consensus. Replication is a common means to introduce redundancy in a system, in order to improve its availability. A replicated server is a server that is composed of multiple copies so that, if one copy fails, the other copies can still provide the service. Each copy of the server is called a replica. The replicas must all evolve in manner that is consistent with the other replicas. Hence, updating the replicated server requires that every replica agrees on the set of modifications to carry over. There are two principal replication schemes to ensure this consistency: active replication and passive replication. In Total Order Broadcast, processes broadcast messages to all processes. However, all messages must be delivered in the same order. Also, if one process delivers a message m, then all correct processes must eventually deliver m. The problem of Consensus gives an abstraction to most other agreement problems. All processes initiate a Consensus by proposing a value. Then, all processes must eventually decide the same value v that must be one of the proposed values. These agreement problems are closely related to each other. For instance, Chandra and Toueg [CT96] show that Total Order Broadcast and Consensus are equivalent problems. In addition, Lamport [Lam78] and Schneider [Sch90] show that active replication needs Total Order Broadcast. As a result, active replication is also closely related to the Consensus problem. The first contribution of this dissertation is the definition of the semi-passive replication technique. Semi-passive replication is a passive replication scheme based on a variant of Consensus (called Lazy Consensus and also defined here). From a conceptual point of view, the result is important as it helps to clarify the relation between passive replication and the Consensus problem. In practice, this makes it possible to design systems that react more quickly to failures. The problem of Total Order Broadcast is well-known in the field of distributed systems and algorithms. In fact, there have been already more than fifty algorithms published on the problem so far. Although quite similar, it is difficult to compare these algorithms as they often differ with respect to their actual properties, assumptions, and objectives. The second main contribution of this dissertation is to define five classes of total order broadcast algorithms, and to relate existing algorithms to those classes. The third contribution of this dissertation is to compare the expected performance of the various classes of total order broadcast algorithms. To achieve this goal, we define a set of metrics to predict the performance of distributed algorithms.
    Résumé
    Les problèmes d'accord forment une classe fondamentale de problèmes dans le contexte des systèmes répartis. Les problèmes d'accord suivent un schéma commun: tous les processus doivent arriver à une décision commune, laquelle dépend de la nature exacte du problème. Cette thèse met principalement l'accent sur trois importants problèmes d'accord: la réplication, la diffusion totalement ordonnée, ainsi que le consensus. La réplication est une technique usuelle permettant d'introduire de la redondance dans un système, afin d'en garantir une meilleure disponibilité. Un serveur répliqué est un serveur qui est constitué de plusieurs copies afin que, si l'une d'entre elles tombe en panne, les autres puissent continuer à fournir le service. Les copies d'un serveur répliqué sont appelées des réplicas. Ces réplicas doivent évoluer de manière cohérente. Ainsi, la modification du serveur répliqué nécessite aux réplicas de se mettre d'accord sur l'ensemble des modifications à apporter à leurs états respectifs. On considère principalement deux approches générales permettant de maintenir cette cohérence: la réplication active et la réplication passive. La diffusion totalement ordonnée est un autre problème d'accord. Des processus diffusent des messages à tous les processus avec la contrainte que tous les messages doivent impérativement être reçus dans le même ordre par tous les processus. De surcroît, si un processus reçoit un message m, alors le problème exige que tous les processus corrects aient la garantie de recevoir le message m de manière inéluctable. Le problème du consensus fournit une abstraction à la plupart des autres problèmes d'accord. Tous les processus débutent un consensus en proposant une valeur. Puis, tous les processus doivent finalement sélectionner la même valeur v, qui doit être la valeur proposée initialement par l'un des processus. Ces problèmes d'accord sont liés les uns aux autres. Par exemple, Chandra et Toueg [CT96] ont montré que la diffusion totalement ordonnée et le consensus sont des problèmes équivalents. Lamport [Lam78] et Schneider [Sch90] ont aussi montré que la réplication active a besoin de la diffusion totalement ordonnée. Ceci signifie que la réplication active est aussi intimement liée au problème du consensus. La première contribution de cette thèse a été de définir la technique de réplication semi-passive. Il s'agit d'une technique de réplication passive basée sur une variante du problème de consensus: consensus paresseux (Lazy Consensus; aussi définie dans ce document). Le résultat est tout d'abord important d'un point de vue conceptuel, car il permet d'éclaircir la relation qui existe entre la réplication passive et le problème du consensus. D'un point de vue pratique, ceci permet de concevoir des systèmes qui réagissent plus rapidement en cas de panne. Le problème de la diffusion totalement ordonnée est bien connu dans le domaine des systèmes et de l'algorithmique répartis. A tel point que plus d'une cinquantaine d'algorithmes on été publiés jusqu'à présent. Malgré leurs similarités, il est difficile de comparer ces algorithmes tant ils diffèrent par leurs propriétés, leurs hypothèses et leurs objectifs. La deuxième contribution de cette recherche a consisté à définir cinq classes d'algorithmes de diffusion totalement ordonnée, et de rattacher les algorithmes existants à ces classes. La troisième contribution de cette recherche a été de comparer les performances supposées des diverses classes d'algorithmes de diffusion totalement ordonnée. Afin d'atteindre cet objectif, il a été nécessaire de définir un ensemble de métriques permettant de prédire les performances d'algorithmes répartis.