An upper and a lower bound for tick synchronization
Date
1992Author
Mavronicolas, MariosISBN
0-8186-3195-3978-0-8186-3195-5
Source
Proceedings - Real-Time Systems Symposium1992 Real-Time Systems Symposium, RTSS 1992
Pages
246-255Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
The tick synchronization problem is defined and studied in the semi-synchronous complete network with n processes. An algorithm for the tick synchronization problem enables each process to make an estimate of real time close enough to those of other processes. It is assumed that the (real) time for message delivery is at most d and the time between any two consecutive steps of any process is in the interval [c, 1], where 0 < c ≤ 1. We define the precision of a tick synchronization algorithm to be the maximum difference between estimates of real time made by different processes, and propose it as a worst-case performance measure. We show that no such algorithm can guarantee precision less than [d-2/2c]. We also present an algorithm which achieves a precision of 2(n-1)/n([2d/e]+d/2)+1-e/c d+1. © 1992 IEEE.