According the paper [1] (Section 4), timestamp ordering (T/O) is a technique whereby a serialization order is selected a priori and transaction execution is forced to obey this order. In the following, it reads

Each transaction is assigned a unique timestamp by its TM (transaction manager). The TM attaches the timestamp to all dm-reads and dm-writes issued on behalf of the transaction, and DMs (data manager) are required to process conflicting operations in timestamp order.

However, this paper did not explain

Question: How to generate the globally unique timestamps for transactions in distributed database systems (assuming no centralized coordination)? What are the commonly used techniques (with references) in this area?

Specifically, is the <local clock, site-id> pair sufficient and appropriate as a timestamp mechanism? If not, why?

[1] Concurrency Control in Distributed Database Systems by Philip A. Bernstein and Nathan Goodman. Computing Surveys, Vol.13, No., 2, June 1981.

  • $\begingroup$ My gut feeling tells me that in order for (local clock, site id) to be useful, the clocks would have to be precisely synchronized, otherwise an event timestamped $(C_1, N_1)$ could be observed by site $N_2$ at a local time $C_2 < C_1$, so causation would not imply precession. But databases aren't my field. $\endgroup$ – Gilles 'SO- stop being evil' May 17 '15 at 13:53
  • $\begingroup$ @Gilles It seems that although (local clock, site id) provides globally unique timestamps, it needs other mechanisms (what I want to know) to make sure that all the sites commit all the transactions in the same total order defined by the timestamps. Thanks for your opinion. $\endgroup$ – hengxin May 17 '15 at 14:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.