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
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.