Lazy Consistency Using Loosely Synchronized Clocks

“Lazy Consistency Using Loosely Synchronized Clocks” by Atul Adya and Barbara Liskov. In ACM Symposium on Principles of Distributed Computing (PODC), (Santa Barbara, CA), Aug. 1997, pp. 73-82.

Abstract

This paper describes a new scheme for guaranteeing that transactions in a client/server system observe consistent state while they are running. The scheme is presented in conjunction with an optimistic 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 for running transactions and also in the way it generates the consistency information. The paper 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 because 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 than 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.

BibTeX entry:

@inproceedings{adya97lazy,
   author = {Atul Adya and Barbara Liskov},
   title = {Lazy Consistency Using Loosely Synchronized Clocks},
   booktitle = {ACM Symposium on Principles of Distributed Computing (PODC)},
   pages = {73--82},
   address = {Santa Barbara, CA},
   month = aug,
   year = {1997},
   url = {http://citeseer.ist.psu.edu/adya97lazy.html}
}