Probabilistic Models of Partial Order Enforcement in Distributed Systems
Modèles probabilistes d’ordonnancement partiel pour les systèmes distribués
Résumé
Distributed systems have managed to extend technology to a broader audience, in both terms of location and numbers. However these geo-replicated systems need to be scalable in order to meet the ever growing demands. Moreover, the system has to be able to process messages in an equivalent order that they were created to avoid unwanted side effects. Partial order enforcement provides an ordering of events that all nodes will follow therefore processing the messages in an adequate order. A system that enforces a partial order simplifies the challenge of developing distributed applications, and ensures that the end-user will not observe causality defying behaviors. In this thesis we present models for different partial order enforcements, using different latency model distributions. While a latency model, which yields the time it takes for a message to go from one node to another, our model builds on it to give the additional time that it takes to enforce a given partial order. We have proposed the following models. First, in a one to many nodes communication, the probability for the message to be delivered in all the nodes before a given time. Second, in a one to many nodes communication from the receivers, the probability that all the other nodes have delivered the message after a given time of him receiving it. Third, in a one to many nodes communication, the probability that the message has arrived to at least a subset of them before a given time. Fourth, applying either FIFO or Causal ordering determining if a message is ready for being delivered, in one node or many. All of this furthers the understanding of how distributed systems with partial orders behave. Furthermore using this knowledge we have built an algorithm that uses the insight of network behavior to provide a reliable causal delivery system. In order to validate our models, we developed a simulation tool that allows to run scenarios tailored to our needs. We can define the different parameters of the latency model, the number of clients, and the clients workloads. This simulation allows us to compare the randomly generated values for each specific configuration with the predicted outcome from our model. One of the applications that can take advantage of our model, is a reliable causal delivery algorithm. It uses causal information to detect missing elements and removes the need of message acknowledgment by contacting other replicas only when the message is assumed missing. This information is provided by our model, that defines waiting timers according to the network statistics and resource consumption. Finally this application has been both tested in the same simulator as the models, with promising results, and then evaluated in a real-life experiment using Amazon EC2 for the platform
Les systèmes distribués ont réussi à étendre la technologie de l’information à un public plus large, en termes d’emplacement et de nombre. Cependant, ces systèmes géo-répliqués doivent être évolutifs afin de répondre aux demandes toujours croissantes. De plus, le système doit pouvoir traiter les messages dans un ordre équivalent à celui de leur création afin d’éviter des effets indésirables. L’exécution suivant des ordres partiels fournit un ordonnancement d’événements que tous les nœuds suivront, ce qui permet donc le traitement des messages dans un ordre adéquat. Un système qui applique un ordre partiel simplifie le développement des applications distribuées et s’assure que l’utilisateur final n’observera pas des comportements défiant la causalité. Dans cette thèse, nous présentons des modèles statistiques pour différentes contraintes d’ordre partiel, en utilisant différentes distributions de modèles de latence. Étant donné un modèle de latence, qui donne le temps qu’il faut pour qu’un message passe d’un nœud à un autre, notre modèle s’appuie sur lui pour donner le temps supplémentaire qu’il faut pour appliquer un ordre partiel spécifique. Nous avons proposé les modèles suivants. Tout d’abord, dans une communication entre un et plusieurs nœuds, la probabilité que le message soit délivré dans tous les nœuds avant un temps donné. Deuxièmement, après la réception d’un message, la probabilité que tous les autres nœuds aient exécuté ce message avant temps donné. Troisièmement, dans une communication de un à plusieurs nœuds, la probabilité que le message soit arrivé à au moins un sous-ensemble d’entre eux avant un temps donné. Quatrièmement, l’ordre FIFO ou causal qui détermine si un message est prêt à être livré, dans un nœud ou plusieurs. Tout cela favorise la compréhension du comportement des systèmes distribués en présence d’ordres partiels. En outre, en utilisant cette connaissance, nous avons construit un algorithme qui utilise ces modèles de comportement du réseau pour établir un système de livraison causal fiable. Afin de valider nos modèles, nous avons développé un outil de simulation qui permet d’exécuter des scénarios adaptés à nos besoins. Nous pouvons définir les différents paramètres du modèle de latence, le nombre de clients et les charges de travail des clients. Cette simulation nous permet de comparer les valeurs générées de façon aléatoire pour chaque configuration spécifique avec les résultats prévus de notre modèle. Une des applications qui peuvent tirer profit de notre modèle, est un algorithme de livraison causale fiable. Il utilise l’information causale pour détecter les éléments manquants et réduit le besoin d’acquittement de message en contactant d’autres répliques seulement lorsque le message est supposé manquant. Cette information est fournie par notre modèle, qui définit les temporisateurs d’attente en fonction des statistiques du réseau et de la consommation des ressources. Enfin, cette application a été testée dans le même simulateur que les modèles, avec des résultats prometteurs, puis évaluée dans une expérience réelle utilisant Amazon EC2 comme plate-forme
Origine : Version validée par le jury (STAR)