Structural modeling and convergence analysis of consensus-based time synchronization algorithms over networks: Non-topological conditions

This paper raises a quite general problem: how to characterize necessary conditions of bounded convergence, namely the divergence conditions, of a consensus-based time synchronization (CBTS) algorithm over a network with random communication delays. We firstly present a unified structural model of CBTS algorithms. Then, we fit different CBTS algorithms, such as DCTS, ATS, WMTS and LSTS, into the same structural model with just different algorithm parameters. To characterize divergence conditions, we focus on the algorithm structure and algorithm parameters rather than the topology graph of the network. By studying the asymptotic property of the relative drift estimation error of CBTS algorithms, we discover (almost sure) divergence conditions and mean-square divergence conditions of CBTS algorithms. Using these conditions we clearly point out that the DCTS algorithm is divergent, the ATS algorithm is divergent almost surely, the WMTS algorithm is mean-square divergent, but the LSTS overcomes all of these divergence conditions. The results of this paper provide a fundamental guideline for designing future time synchronization algorithms.