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

1. Execute all operations at the process receiving t (denoted t 's initiator).
2. Ordering: A set of processes denoted observers are asked to order t against all
conflicting transactions. The observers for t are given by RS ( t )and WS ( t ).
3. Validation: Once t is ordered against all conflicting transactions, it is ready
for validation. The validating process p is determined by the observers. t is
granted commit if and only if for each member i of RS ( t ), t has read the
most recent version of i according to the local order of p .
4. If t is committed, updates are applied according to the order seen by the
validator. Otherwise, an abort-message is sent to participating processes.

The purpose of FLACS is to reduce validation delay since coordination among
the observers usually requires fewer messages than an atomic broadcast.

3.1 Observers

An observer's task is to serialize updates on its observed items. Formally, an
observer function obs : I

+ ( P ) maps each item i to its observer(s) obs ( i ).
The idea is to choose as observers processes physically near the most frequent
users, and assign items commonly accessed by conflicting transactions to the
same observer(s). The observers for a transaction t is the union of the observers
for all items in WS ( t ).

→P

Example 1. Consider a hotel reservation service. Since most reservations are
local, rooms in France should map to observers physically located in Paris, while
rooms in Germany are observed by processes in Berlin. As explained below, this
allows transactions accessing rooms only in France to commit locally in Paris.

3.2 Ordering

The FLACS validation procedure dictates that a transaction t is granted commit
if and only if t has read the most recent version of each i ∈ RS ( t ). Since there is
no common time among processes, we need to define “most recent.” For protocols
where transactions are included in a total order before validation, the definition
of most recent is simple: it is the most recent according to the total order.
FLACS does not include transactions in a total order before validation. In-
stead, FLACS uses an incremental ordering and validates a transaction t as soon
as it is ordered against all conflicting transactions. Each process p maintains a
local, strict partial order

≺ p on the (update) transactions seen so far. Intuitively,
≺ p must order any pair of transactions t, t known by p to be in conflict. How-
ever, the local orders at different processes might be inconsistent. Our idea is to
combine these local orders using a tree structure among processes, in which the
root of a subtree is responsible for combining the local orders of its descendants,
or discovering inconsistencies and resolving them by aborting transactions.
A transaction t can be validated if all observers of items in WS ( t )havetreated
t , and if the local orders of these observers are consistent up to t ; i.e., they can
be combined into one strict partial order.