Lazy consistency using loosely synchronized clocks
Atul Adya, Barbara H. Liskov · 1997
This paper describes a new scheme for guaranteeing that transactions in a clientlserver system observe consistent state while they are running.Thescheme ispresented inconjunction with at'toptimistic concurrency control algorithm, but could also be used to prevent read-only transactions from conflicting with read/write transactions in a multi-version system.The scheme is lazy about the consistency it provides forruming transactions and also in the way it generates theconsistency information.Thepaper presents results of simulation experiments showing that the cost of the scheme is negligible.The scheme uses multipart timestamps to inform nodes about information they need to know.Today the utility of such schemes is limited beeause timestamp size is proportional to system size and therefore the schemes don't scale to very large systems.We show how to solve this problem.Our multipart timestamps are based on real rather thm logical clocks; we assume clocks in the system are loosely synchronized.Clocks allow us to keep multipart timestamps small with minimal impact on performance: we remove old information that is likely to be known while retaining recent information.Only performance and not correctness is affected if clocks get out of synch.