Modelização e validação dos algoritmos não determinísticos de sincronização de relógios

Esta tese aborda o problema da análise e da concepção de algoritmos de sincronização de relógios não determinísticos. Os algoritmos não-determinísticos constituem uma solução promissora para o problema da sincronização de relógios, sendo prova disso o interesse que estes têm despertado nos últimos anos. Os algoritmos de sincronização não-determinísticos utilizam técnicas estatísticas ou probabilísticas para a obtenção do resultado. Obtém-se assim uma melhor precisão do que com os algoritmos determinísticos. O preço a pagar é uma (pequena) probabilidade que o sistema não consiga sincronizar com a precisão desejada. Pode-se tornar esta probabilidade de insucesso tão pequena quanto necessário através da utilização de um número de mensagens suficientemente grande. Infelizmente, a comparação e a avaliação das diferentes soluções propostas é difícil, principalmente devido à inexistência duma base comum para estabelecer essas comparações. Nesta tese, propomos um modelo analítico para o funcionamento dos algoritmos de sincronização não-determinísticos. O objectivo é obter uma expressão que permita calcular o número de mensagens necessárias para um determinado algoritmo, de modo a que a sincronização ocorra com a precisão e a probabilidade especificadas. Este resultado é a Condição de Garantia de Sincronização, que define uma condição suficiente para garantir o sucesso da sincronização não-determinística sob as condições especificadas de precisão e probabilidade de sucesso. Esta condição é estabelecida a partir de parâmetros locais de um nó e de parâmetros do sistema que são facilmente calculáveis, tais como o número de nós ou os parâmetros que descrevem o atraso de comunicação como uma variável aleatória. As condições subjacentes ao modelo proposto são verificadas experimentalmente. Para tal, desenvolveu-se uma plataforma baseada na rede CAN (Controller Area Network). As experiências realizadas permitiram verificar a validade das hipóteses associadas ao modelo.Cette thèse traite le problème d’analyse et de conception des algorithmes de synchronisation nondeterministes dans les systèmes repartis. Les algorithmes non-deterministes constituent une solution intéressante pour le problème de la synchronisation des horloges, ce qui est témoigné par l'interet qui leur a été porté pendant les dernières années. Les algorithmes de synchronisation non-deterministes utilisent des techniques statistiques ou probabilistes et permettent d'obtenir une meilleure precision par rapport aux algorithmes deterministes, le prix à payer étant la probabilité que le système ne réussisse pas a se synchroniser avec la précision souhaitée. Cette probabilité d'échec tend vers zéro avec le nombre de messages échangés et elle peut être réduite a une valeur aussi petite qu'on le souhaite avec un nombre de messages suffisamment grand. Malheureusement, I’évaluation des différentes propositions publiées dans la littérature est difficile, principalement à cause de l’inexistence d’une base commune pour établir les comparaisons. Nous proposons un modèle analytique pour le fonctionnement des algorithmes de synchronization non-déterministes. Le but est de trouver une expression que le concepteur d'un système distribué puisse utiliser pour calculer le nombre de messages requis pour un certain algorithme, de façon à fournir la synchronisation avec la précision et la probabilité spécifiées. Ce résultat est la Condition de Garantie de Synchronisation, qui définit une condition suffisante qui garantit le succès de la synchronisation non-deterministe sous les conditions spécifiées. Cette condition est établie a partir de paramètres locaux d'un site et de paramètres du système qui sont facilement calculables, tel que le nombre de sites et les paramètres qui décrivent le délai comme une variable aléatoire. Les conditions sous-jacentes au modèle proposé sont vérifiées experimentalement à l'aide d’une plate-forme basée sur le reseau CAN que nous avons dévelopée. Le test des algorithms sur cette plate-forme a permis de vérifier la validité des hypothèses qui sont associées au modèle.This thesis addresses the problem of analysing and designing non-deterministic clock synchronization algorithms in distributed systems. Non-deterministic algorithms are a promising solution to the clock synchronisation problem, which can be testified by the attention they have received in recent years. Non-determinist clock synchronisation algorithms use statistical or probabilistic techniques and they allow a better precision than with deterministic ones; the price to pay is a small probability that the system will fail to synchronise to the desired precision. This probability of failure can be made as small as desired by sending a sufficiently large number of messages. Unfortunately assessing different algorithms is a difficult task, specially because we lack a common ground to establish comparisons. We propose an analytical model for the behaviour of non-deterministic clock synchronisation algorithms. The aim is to find an expression that the distributed systems designer can use to estimate the required number of messages in order to guarantee that a certain algorithm will synchronise to the desired precision and probability of success. This result is a Sufficient Condition for Synchronisation, which states the conditions that must be fulfilled in order to guarantee the desired precision and probability of success. This condition is based on local parameters and on system parameters that are easily computed, such as the number of sites and the description of the delay as a random variable. The underlying assumptions are experimentally verified. For this purpose, we developed a test-bed based on the Controller Area Network. The results validate the assumptions used for the model.Junta Nacional de Investigação Científica e Tecnológica/ Fundação para a Ciência e Tecnologia.Programa Doutoral em Engenharia Eletrotécnic