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.:
-
If two events are co-located, then the local clock will determine their
ordering.
-
If an event e1 causes a message to arrive at a separate host, which ;SPM_quot;causes;SPM_quot;
another event e2, then e2 happens ;SPM_quot;after;SPM_quot; e1.
-
If e1 ;SPM_quot;causes;SPM_quot; e2 and e2 ;SPM_quot;causes;SPM_quot; e3, then e3 happens ;SPM_quot;after;SPM_quot; e1.
-
If e1 ;SPM_quot;causes;SPM_quot; e2, and e1 ;SPM_quot;causes;SPM_quot; e3, then e2 and e3 have no special
relation and are effectively ;SPM_quot;simultaneous;SPM_quot;.
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.