Analysis of Bounds on Hybrid Vector Clocks

• Published in: IEEE transactions on parallel and distributed systems 2018-09, Vol.29 (9), p.1947-1960
• Main Authors: Yingchareonthawornchai, Sorrachai, Nguyen, Duong N., Kulkarni, Sandeep S., Demirbas, Murat
• Format: Article
• Language: English
• Subjects: Analytical models; Clocks; Communication; Communications systems; Computer networks; Computer simulation; Delay; Delays; Differential equations; distributed systems; logical clocks; Mathematical model; Parameter uncertainty; physical clocks; Synchronization; Uncertainty; Upper bounds; Vector clocks; Windows (intervals)
• ISSN: 1045-9219; 1558-2183
• DOI: 10.1109/TPDS.2018.2818700

Hybrid vector clock(s) (HVC) provide a mechanism to combine the theory and practice of distributed systems. Improving on traditional vector clock(s) (VC), HVC utilizes synchronized physical clocks to reduce the size by focusing only on causality where the physical time associated with two events is within a given uncertainty window ε and letting physical clock alone determine the order of events that are outside the uncertainty window. In this paper, we develop a model for determining the bounds on the size of HVC. Our model uses four parameters, ε: uncertainty window, 8: message delay, a: communication frequency and n: number of nodes in the system. We derive the size of HVC in terms of a delay differential equation, and show that the size predicted by our model is almost identical to the results obtained by simulation. We also identify closed form solutions that provide tight lower and upper bounds for useful special cases. We show that for many practical applications and deployment environments in Amazon EC2, the size of HVC remains only as a couple entries and substantially less than n. Finally, although the analytical results rely on a specific communication pattern they are useful in evaluating size of HVC in different communication scenarios.