Scalable and Fully Consistent Transactions in the Cloud through Hierarchical Validation - Data Management in Cloud, Grid and P2P Systems - page 33

to those observers. This message contains the write set of t whichisusedto
acquire locks for the relevant items. Furthermore, the validating process is noti-
fied by the message validateRequest , which also contains WVal ( t ), the updated
values, and the mapping RVer ( t ), associating every item i in RS ( t )totheidof
the transaction performing the most recent update on i prior to t 's read. Note
that the initiator may be an observer, and often also the validator.
After the ordering and validation messages are sent, the initiator waits for the
commit decision, and replies to the client accordingly. Finally, locks are released.
4.2 Ordering
Figure 3 describes the rules for ordering transactions. Whenever an observer
receives an informObserver message for transaction t (rule INIT-ORDER ), it
creates a remote subtransaction to apply t 's updates (unless this observer is the
initiator). Remote subtransactions are write-only, request high priority locks to
abort any local transaction (these would eventually fail validation anyway), and
await the commit decision of t before committing. A node for t is also added to
the order graph.
The rule ORDERED is executed at process p when a transaction t satisfies
the requirements to be ordered at p ; i.e., all expected order requests have been
received and there are no preceding transactions in the local ordering graph.
Then, t is appended to the local order at p and a propagateOrder -message is
sent to p 's parent in the validation hierarchy. Since we use FIFO-unicast, the
ordering of propagateOrder -messages from process p a to p b reflects the local
order at p a .
The rule RCV-ORDER is executed whenever a process p receives a propa-
gateOrder message for t from a child p in the validation hierarchy. Unless t
is already known at p , the process p first initiates a remote subtransaction to
acquire the necessary write locks. In any case, an edge from t prev to t is added
to the local order graph of p ,where t prev is the most recent transaction received
from p before t . If the ordering becomes inconsistent, there will be a cycle in
the local order graph and the transaction is aborted. This rule will be triggered
repeatedly for t until all expected propagateOrder messages have arrived. Even-
tually, t will either be aborted or satisfy the conditions for the rule ORDERED
at p ; the proposed ordering is then propagated to p 's parent.
4.3 Validation
The rule for validation is given in Fig. 4. For each transaction t , validation is
performed by the receiver of the validateRequest . Validation of t occurs as soon
as t has been ordered at p v and p v has received the validateRequest message for
t . The validation test is a standard optimistic validation procedure, using the
local update history at p v to verify that for each item i read by t , t saw the most
recent version of i according to p v 's local order.