Probabilistic Clock Synchronization
Most of the aforementioned algorithms work with bounded message passing latencies. It has been shown by Landelius and Lynch  that in an ensemble of N clocks, if each clock runs in real-time, then even in the absence of faults, the ensemble cannot be synchronized with a convergence:
where e represents the upper bound of uncertainty in message passing latency. In cases where the message passing latency is unbounded, probabilistic clock synchronization algorithms have been found to be very useful for both external and internal clock synchronizations. For a detailed analysis of such methods the reader is directed to Cristian  and Landelius and Lynch .
NUMERICAL AND ANALYTICAL PROBLEMS
- 2.1. Deduce a relationship between the message passing latency and minimum value of global time granularity. Given a latency jitter of 20 ps, a clock drift rate of 10-5 s/s and a resynchronization interval of 1 s, calculate the precision achievable by a central master algorithm in an ensemble of 10 clocks.
- 2.2. A control system consists of a time-driven sensor that sends data to a controller every 10 ms over a network. The controller is also time-driven and updates data every 10 ms. The maximum latency of data transfer is 100 ps. The drift rate associated with the clocks 10-5 s/s and the resynchronization interval is 100 s. If the convergence of synchronization is 200 ps, by what quantum of time should the controller's timeline be skewed so that the controller in the kth step always picks up the data sent by the sensor during that step? Assume no data loss. What should be the smallest value of a macrotick if two consecutive samples sent by the sensor belong to two consecutive macroticks? Is the timeframe reasonable in this case?
- 2.3. Establish a limit for p for an interactive convergence algorithm in terms of maximum drift rate, resynchronization period, uncertainty bound in reading clocks, and number of faulty clocks. Hint: Look up Lamport and Melliar-Smith .
- 2.4. Prove that in an ensemble of N clocks, if the maximum uncertainty of communication latency is e, then the convergence is e(1 - 1/N) Hint: Look up Landelius and Lynch .
- 1. Kopetz, H. Real-Time Systems: Design Principles for Distributed Embedded Applications. Springer, 1997, ISBN: 0792398947.
- 2. LeapSecond.com. GPS, UTC, and TAI clocks. http://www.leapsecond.com/ java/gpsclock.htm.
- 3. Cristian, F. Probabilistic clock synchronization. Distributed Computing, 3, 146-158, 1989.
- 4. Lamport, L., Shostak, R., and Pease, M. The byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3), 382-401, 1982.
- 5. Pease, M., Shostak, R., and Lamport, L. Reaching agreement in the presence of faults. Journal of the ACM, 27(2), 228-234, 1980.
- 6. Lamport, L. and Melliar-Smith, P. M. Byzantine clock synchronization. ACM Transactions on Programming Languages and Systems, 4(3), 68-74, 1984.
- 7. Landelius, J. and Lynch, N. An upper and lower bound for clock synchronization. Information and Control, 62, 190-204, 1984.