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

Protocol composition frameworks and modular group communication : models, algorithms and architectures

Mena de la Cruz, Sergio ; Schiper, André (Dir.)

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

Add to personal list
    Summary
    It is noticeable that our society is increasingly relying on computer systems. Nowadays, computer networks can be found at places where it would have been unthinkable a few decades ago, supporting in some cases critical applications on which human lives may depend. Although this growing reliance on networked systems is generally perceived as technological progress, one should bear in mind that such systems are constantly growing in size and complexity, to such an extent that assuring their correct operation is sometimes a challenging task. Hence, dependability of distributed systems has become a crucial issue, and is responsible for an important body of research over the last years. No matter how much effort we put on ensuring our distributed system's correctness, we will be unable to prevent crashes. Therefore, designing distributed systems to tolerate rather than prevent such crashes is a reasonable approach. This is the purpose of fault-tolerance. Among all techniques that provide fault tolerance, replication is the only one that allows the system to mask process crashes. The intuition behind replication is simple: instead of having one instance of a service, we run several of them. If one of the replicas crashes, the rest can take over so that the crash does not prevent the system from delivering the expected service. A replicated service needs to keep all its replicas consistent, and group communication protocols provide abstractions to preserve such consistency. Group communication toolkits have been present since the late 80s. At the beginning, they were monolithic and later on they became modular. Modular group communication toolkits are composed of a set of off-the-shelf protocol modules that can be tailored to the application's needs. Composing protocols requires to set up basic rules that define how modules are composed and interact. Sometimes, these rules are devised exclusively for a particular protocol suite, but it is more sensible to agree on a carefully chosen set of rules and reuse them: this is the essence of protocol composition frameworks. There is a great diversity of protocol composition frameworks at present, and none is commonly considered the best. Furthermore, any attempt to defend a framework as being the best finds strong opposition with plenty of arguments pointing out its drawbacks. Given the complexity of current group communication toolkits and their configurability requirements, we believe that research on modular group communication and protocol composition frameworks must go hand-in-hand. The main goal of this thesis is to advance the state of the art in these two fields jointly and demonstrate how protocols can benefit from frameworks, as well as frameworks can benefit from protocols. The thesis is structured in three parts. Part I focuses on issues related to protocol composition frameworks. Part II is devoted to modular group communication. Finally, Part III presents our modular group communication prototype: Fortika. Part III combines the results of the two previous parts, thereby acting as the convergence point. At the beginning of Part I, we propose four perspectives to describe and compare frameworks on which we base our research on protocol frameworks. These perspectives are: composition model (how the composition looks like), interaction model (how the components interact), concurrency model (how concurrency is managed within the framework), and interaction with the environment (how the framework communicates with the outside world). We compare Appia and Cactus, two relevant protocol composition frameworks with a very different design. Overall, we cannot tell which framework is better. However, a thorough comparison using the four perspectives mentioned above showed that Appia is better in certain aspects, while Cactus is better in other aspects. Concurrency control to avoid race conditions and deadlocks should be ensured by the protocol framework. However this is not always the case. We survey the concurrency model of eight protocol composition frameworks and propose new features to improve concurrency management. Events are the basic mechanism that protocol modules use to communicate with each other. Most protocol composition frameworks include events at the core of their interaction model. However, events are seemingly not as good as one may expect. We point out the drawbacks of events and propose an alternative interaction scheme that uses message headers instead of events: the header-driven model. Part II starts by discussing common features of traditional group communication toolkits and the problems they entail. Then, a new modular group communication architecture is presented. It is less complex, more powerful, and more responsive to failures than traditional architectures. Crash-recovery is a model where crashed processes can be restarted and continue where they were executing just before they crashed. This requires to log the state to disk periodically. We argue that current specifications of atomic broadcast (an important group communication primitive) are not satisfactory. We propose a novel specification that intends to overcome the problems we spotted in existing specifications. Additionally, we come up with two implementations of our atomic broadcast specification and compare their performance. Fortika is the main prototype of the thesis, and the subject of Part III. Fortika is a group communication toolkit written in Java that can use third-party frameworks like Cactus or Appia for composition. Fortika was the testbed for architectures, models and algorithms proposed in the thesis. Finally, we performed software-based fault injection on Fortika to assess its fault-tolerance. The results were valuable to improve the design of Fortika.
    Résumé
    Chacun sait que notre société dépend de plus en plus des systèmes informatiques. De nos jours, on peut trouver des réseaux informatiques dans des endroits où cela aurait été impensable quelques décennies auparavant, ces réseaux offrant dans certains cas une infrastructure critique puisque des vies humaines peuvent en dépendre. Bien que ce recours grandissant aux systèmes en réseau soit généralement perçu comme un progrès technique, il faudrait toutefois être conscient que de tels systèmes voient leur taille et leur complexité augmenter constamment, à tel point que le fait d'assurer leur fonctionnement correct est parfois une tâche exigeante. En conséquence, la sûreté de fonctionnement des systèmes distribués est devenue une question capitale, qui a suscité un nombre important de recherches ces dernières années. Quel que soit l'effort que nous déployons à assurer la correction de notre système distribué, nous serons incapables d'empêcher des défaillances. Par conséquent, concevoir notre système distribué de manière à ce qu'il tolère des pannes plutôt qu'il les empêche est une approche raisonnable. C'est le but de la tolérance aux pannes. Parmi toutes les techniques qui fournissent de la tolérance aux pannes, la réplication est la seule qui permette au système de masquer les défaillances. L'intuition derrière le concept de réplication est simple : au lieu d'avoir une seule instance d'un service, on en exécute plusieurs. Si une des répliques tombe en panne, celles qui restent peuvent reprendre le travail de manière à ce que la panne n'empêche pas le système de fournir le service attendu. Un service répliqué a besoin de maintenir toutes ses répliques dans un état cohérent, et les protocoles de communication de groupe fournissent des abstractions permettant de maintenir une telle cohérence. Les outils de communication de groupe existent depuis la fin des années quatre-vingts. Au début, ils étaient monolithiques et plus tard ils sont devenus modulaires. Les outils de communication modulaires sont composés d'un ensemble de protocoles déjà prêts qui peuvent être combinés selon les besoins de l'application. La composition de protocoles requiert de mettre en place des règles définissant la manière dont les modules sont composés et interagissent. Parfois, ces règles sont conçues uniquement pour quelques protocoles particuliers, mais il est plus sensé de se mettre d'accord sur un ensemble de règles soigneusement choisies et de les réutiliser : ceci est l'essence des cadriciels (frameworks) de composition de protocoles. De nos jours, il y a une grande diversité de cadriciels de composition de protocoles, et aucun ne fait l'unanimité. De plus, n'importe quelle tentative de présenter un cadriciel comme étant le meilleur rencontre immédiatement une forte opposition avec un grand nombre d'arguments démontrant ses points faibles. Étant donné la complexité des outils de communication de groupe et leurs besoins de configurabilité, nous estimons que la recherche dans le domaine de la communication de groupe modulaire et des cadriciels de composition de protocoles doit être menée en parallèle. L'objectif principal de cette thèse est de faire avancer l'état de l'art conjointement dans ces deux domaines et de démontrer à quel point les protocoles peuvent améliorer la conception des cadriciels, en même temps que les cadriciels améliorent la conception des protocoles. La thèse est structurée en trois parties. La partie I met l'accent sur des questions relatives aux cadriciels de composition de protocoles. La partie II est consacrée à la communication de groupe modulaire. Finalement, la partie III présente notre prototype de communication de groupe modulaire : Fortika. La partie III combine les résultats des deux parties précédentes, constituant ainsi leur point de convergence. Au début de la partie I, nous proposons quatre perspectives pour décrire et comparer les cadriciels sur lesquels nous basons notre recherche en cadriciels de composition de protocoles. Ces perspectives sont : le modèle de composition (à quoi ressemble la composition), le modèle d'interaction (comment les composants interagissent entre eux), le modèle de concurrence (comment la concurrence est gérée à l'intérieur du cadriciel), et l'interaction avec l'environnement (comment le cadriciel communique avec le monde extérieur). Nous comparons Appia et Cactus, deux cadriciels de composition de protocoles significatifs, mais très différents l'un de l'autre. De manière générale, nous ne pouvons pas dire lequel est le meilleur : une comparaison minutieuse utilisant les quatre perspectives mentionnées plus haut a montré qu'Appia est meilleur pour certains aspects, tandis que Cactus est meilleur pour d'autres aspects. Les cadriciels de composition de protocoles devraient assurer un contrôle de la concurrence afin d'éviter des conflits d'accès et des situations d'interbloquage. Malheureusement, ce n'est pas toujours le cas. Nous examinons le modèle de concurrence des huit cadriciels de composition de protocoles et nous proposons de nouvelles idées pour améliorer la gestion de la concurrence. Les événements sont le mécanisme de base que les protocoles utilisent pour communiquer entre eux. La plupart des cadriciels de composition de protocoles utilisent des événements au coeur de leur modèle d'interaction. Cependant, les événements ne sont apparemment pas aussi bons que l'on pourrait s'y attendre. Nous mentionnons les inconvénients des événements et nous proposons un nouveau modèle d'interaction qui utilise les en-têtes des messages à la place d'événements : le modèle "dirigé par les en-têtes". La partie II commence par un examen des caractéristiques communes aux outils traditionnels de communication de groupe et des problèmes qu'ils occasionnent. Une nouvelle architecture de communication de groupe modulaire est ensuite présentée. Cette dernière est moins complexe, plus puissante et réagit mieux aux défaillances que les architectures traditionnelles. Crash-recovery est un modèle où les processus tombés en panne peuvent être redémarrés et continuer leur exécution à l'endroit où ils étaient juste avant qu'ils ne tombent en panne. L'idée consiste à enregistrer périodiquement leur état sur disque. Nous défendons le point de vue que les spécifications de diffusion atomique (une primitive de communication de groupe importante) actuelles ne sont pas satisfaisantes. Nous proposons une nouvelle spécification visant à corriger les problèmes des spécifications existantes. De plus, nous avons réalisé deux implémentations de notre spécification de diffusion atomique, et nous comparons leur performance. Fortika est le principal prototype de cette thèse, ainsi que le sujet de la partie III. Fortika est un outil de communication de groupe écrit en Java et pouvant utiliser des plates-formes comme Cactus ou Appia. Fortika constitue le banc d'essai des architectures, des modèles et des algorithmes proposés dans cette thèse. Finalement, nous avons soumis Fortika à des injections de fautes afin d'évaluer sa robustesse. Les résultats ont contribué à améliorer Fortika de manière significative.