Summary

Hybrid vector clocks implements vector clocks in a space-efficient manner by employing loosely clock synchronization, e.g., from NTP while supporting traditional comparison as in vector clocks. The key benefits is that HVC does not need to maintain all entries at all time while vector clocks cannot reduce size in general. The size of HVC depends on communication pattern. If processes are talkaive, the size of HVC can be up to n where n is the number of processes. If processes do not talk at all, the size of HVC is a constant one. A natural question is what is the size of HVC given a communication pattern? We address this question by analyzing random unicast message transmission pattern. We provide analytical models that the predicted sizes of HVC match with our simulation results. The main connection to the real-world parameters is that we derive a condition where the size of HVC blow up at exponential rate, and we can plug in system's parameter directly to see if the expected hvc size of the system in the long run.

Observations

This work demonstrates the phenomenon of processes in such a way that worse-case and best-case analysis only provide a trivial result. The communication pattern is then necessary to obtain meaningful result in between worst-case and best-case. We then analyze a natural random process, which is a unicast random transimission model. Interestingly, this problem turns out to have interesting solutions. We obtain the precise solution to analytical model by exploring combinatorial structure of HVC to make the original model tractable.

Download source code here


  • Simulation is written in C++
  • Numerical Solution is obtained by MATLAB using ddr23 packages

Presentation is available here as well as local copy of the paper

images