Understanding Probabilistic Clock Synchronization

This post is meant to discuss the probabilistic clock synchronization technique. The main goal of this technique is to bound the difference between systems by setting up an upper bound. Formally, we define the problem as \(|P(t)-Q(t)|\leq \varepsilon\), or the difference between clocks across the network. We will go over the technical detains and discuss what these symbols represent in later sections. Most of these materials are from Prof. Mok’s slides on dependable systems classes.

Perfect Synchronization

The motivation behind this technique is that synchronization always involves overheads. In a perfect environment where network delay and request processing time are both 0, the clocks can be synchronized with ease. A slave P will send ‘‘Time = ?’’ at global time \(t\) to master Q and master Q replies ‘‘Time = Q(t)’’ instantaneously at global time \(t\). Then P will adjust its clock P(t) according to Q(t). However, such case only exists in imagination.

Amortization

Suppose the difference between the clock of P and Q is \(\Delta\) at synchronization, our goal is to adjust P’s logical clock C(t) to mitigate the difference. The adjustment is simple:

\[C(t)=H(t)+A(t)...