## 6 Fully-Distributed Clock Synchronization Algorithms
### Fully-Distributed Clock Synchronization Algorithms under Gaussian Delays
#### 6.2.1 Belief-Based Synchronization Algorithms
Furthermore, the belief of each node is initially set as its prior distribution, _i.e._, \(b_{i}^{(0)}(\theta_{i})=p(\theta_{i})\). Beliefs and messages are then iteratively updated at variable nodes and factor nodes, respectively. After convergence, the belief at each node reaches the posterior distribution exactly when the network topology is loop free and approximately when the network topology presents loops [48]. Thus, the maximum _a posteriori_ probability (MAP) estimate is obtained by maximizing the converged belief at each node. Since each node runs the same algorithm only with its neighbors, the estimates are achieved in a fully-distributed manner. However, only the problem of clock offset estimation is investigated in [46]. Moreover, the algorithm is performed in a synchronous way, _i.e._, every node updates its belief only after receiving messages from all of its neighboring factor nodes. Due to the random packet dropouts, the synchronous algorithm may converge slowly. To account for these aspects, [PERSON] _et al._[47] generalized the belief-based algorithm to jointly estimate the clock offset and skew under Gaussian random delays using both synchronous and asynchronous algorithms. In the asynchronous algorithm, some nodes are allowed to update their beliefs more frequently as long as they receive messages from their neighbors within a preset time period. Following the two-way message exchange model in Equations (45) and (46), the authors in [47] eliminated the fixed delay \(d\) by adding these two equations together. It turns out that:  
\[\mathbf{A}_{j,i}\beta_{j}+\mathbf{A}_{i,j}\beta_{i}=z_{j,i} \tag{53}\]  
where \(\mathbf{A}_{j,i}\) and \(\mathbf{A}_{i,j}\) are \(N\)-by-two matrices with the \(n\)-th row representing \([c_{j}(t_{n}^{2})+c_{j}(t_{n}^{3}),-2]\) and \(-[c_{i}(t_{n}^{1})+c_{i}(t_{n}^{4}),-2]\), respectively, \(\beta_{j}\stackrel{{\triangle}}{{=}}[1/f_{j},\theta_{j}/f_{j}]^{T}\), \(\beta_{i}\stackrel{{\triangle}}{{=}}[1/f_{i},\theta_{i}/f_{i}]^{T}\) and \(z_{j,i}=[X_{j,1}-Y_{j,1},\cdots,X_{j,N}-Y_{j,N}]^{T}\). Thus, the likelihood function can be obtained from Equation (53), and it is denoted by \(p(\mathbf{A}_{i,j},\mathbf{A}_{j,i}|\beta_{i},\beta_{j})\). The message passing procedure adopted in [47] is slightly different from the one in [46]. In Step 1, instead of broadcasting the belief to all of its neighboring factor nodes, the message transmitted from variable node \(\theta_{i}\) to factor node \(\gamma_{ij}\) is evaluated via:  
\[m_{\theta_{i}\rightarrow\gamma_{i,j}}^{(l)}(\beta_{i})=\prod_{k\in\beta_{i} \setminus j}m_{\gamma_{i,k}\rightarrow\theta_{i}}^{(l-1)}(\beta_{i}) \tag{54}\]  
Figure 5: The factor graph of nodes \(i\) and \(j\). which is simply the product of the incoming messages on the other links. Thus, in Step 2, the message from a factor node \(\gamma_{ij}\) to a variable node \(\theta_{i}\) is updated via:  
Figure 4:0  
and the belief is further updated as:  
Figure 4:1  
It is illustrated analytically in [47] that the asynchronous algorithm converges regardless of the network topology, and the MSE of the estimation parameters achieves the centralized CRLB asymptotically. Simulation results further show that the asynchronous algorithm converges faster than the synchronous one. In parallel to the work in [47], [PERSON] _et al._[22] proposed a BP algorithm and a mean field (MF) algorithm and adopted a Bayesian model with Gaussian random delays. The MAP estimates of clock offset and skew are derived using some simplifications of the measurement likelihoods and prior distributions. The message update rule in the BP algorithm is analogous to the one in [47] (see, e.g., Equations (54) and (55)). As concerns the implementation of the MF algorithm, each variable node \(\theta_{i}\) broadcasts its current belief \(b^{(l)}_{i}(\theta_{i})\) to all of its neighboring factor nodes, and the same step as in [46] is followed.