Skip to Main content Skip to Navigation

Modélisation et validation des algorithmes non-déterministes de synchronisation des horloges

Abstract : This thesis addresses the problem of analyzing and designing non-deterministic clock synchronization algorithms in distributed systems. Non-deterministic algorithms are a promising solution to the clock synchronization problem, which can be testified by the attention they have received in recent years. Non-determinist dock synchronization 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 synchronize 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, especially because we lack a common ground to establish comparisons. We propose an analytical model for the behaviour of non-deterministic dock synchronization 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 synchronize to the desired precision and probability of success. This result is a Sufficient Condition for Synchronization, 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.
Document type :
Complete list of metadata
Contributor : Thèses Ul Connect in order to contact the contributor
Submitted on : Thursday, March 29, 2018 - 12:32:13 PM
Last modification on : Monday, April 16, 2018 - 10:42:32 AM
Long-term archiving on: : Friday, September 14, 2018 - 2:57:42 PM


Files produced by the author(s)


  • HAL Id : tel-01749906, version 1



Pedro Nicolau Faria Da Fonseca. Modélisation et validation des algorithmes non-déterministes de synchronisation des horloges. Autre [cs.OH]. Institut National Polytechnique de Lorraine, 1999. Français. ⟨NNT : 1999INPL038N⟩. ⟨tel-01749906⟩



Record views


Files downloads