| Resumo: | 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.
|
|---|