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.