Timestamps

We have seen that a distributed transaction system requires concurrency control. One mechanism used is to add a time stamp to each transaction. The mechanism is quite simple. A ;SPM_quot;write;SPM_quot; transaction updates an object, and adds its timestamp to the object. If a further ;SPM_quot;read;SPM_quot; or ;SPM_quot;write;SPM_quot; transaction attempts to access the object and has an older timestamp than that of the object (i.e. that of the latest correct successful transaction), this transaction is aborted. This mechanism avoids the need for locks altogether and therefore avoids any deadlock problems. It does so, effectively, by serializing all transactions based on a notion of global time in the distributed system. Of course, we still need to provide failure atomicity (say by two phase commit), but most importantly we need to provide global synchronisation. A global clock is useful for other things too such as distributed deadlock detection (and see later in security). Mills [Ref NTP] suggests that clocks can be synchronized to a high degree of accuracy even compared with the variation in message transit delay between distributed computers. In fact, we do not necessarily require global synchronization of clocks, so much as global ordering of related events. The rules for working out this ordering are simple (due to Lamport[#lamport##1#]). The clock here need only be a counter at a location that is incremented with each event.: Each host keeps monotonically increasing ;SPM_quot;logical;SPM_quot; clock with each event, which it can use to ;SPM_quot;timestamp;SPM_quot; messages so that other hosts can track the order of messages from this host.