Murat Demirbas: Hybrid Clocks for High Auditability

 Work on theory of distributed systems abstract away from thewall-clock/physical-clock time and use the notion of logical clocks for
ordering events in asynchronous distributed systems. Practice of
distributed systems, on the other hand, employ loosely synchronized clocks,
mostly using NTP. Unfortunately, there are fundamental limits to clock
synchronization and perfect synchronization is unachievable. Recently, we
introduced a third option, hybrid clocks. Hybrid clocks combine the best of
logical and physical clocks; hybrid clocks are immune to their
disadvantages while providing their benefits. Hybrid clocks are loosely
synchronized using NTP, yet they also provide provable comparison
conditions as in LC or VC within time synchronization uncertainty periods.

Our hybrid clocks come in two flavors: hybrid logical clocks (HLC) and
hybrid vector clocks (HVC). HLC finds applications in multiversion
distributed database systems and enable efficient querying of consistent
snapshots for read transactions, while ensuring commits of write
transactions do not get delayed despite the uncertainties in NTP clock
synchronization. HVC finds applications in debugging for concurrency race
conditions and in lightweight causal delivery of messages, and, for almost
all practical applications and deployment environments, the size of HVC
remains only as a couple entries and substantially less than n.

In addition to covering our recent work on hybrid clocks, I will also talk
about what I believe are promising directions for distributed systems
research on cloud computing systems.