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

RULE: VAL IDATION
when hasLocalOrder(t) and hasReceivedValidationRequest(t) do
if isValid ( RS ( t ) , RVe r ( t ) ,WS ( t )) then broadCast commit( t , WS ( t ), WVal ( t ), Wseq ( t ))
else broadCast abort( t )
func isValid(RS ( t ) ,RVer ( t ) ,WS ( t ) )
foreach i in RS ( t ) do
version =getVersion( i , RVe r ( i ))
if version < getLatestVersion(i, DATABASE) then return false
return true

Fig. 4. Validation

Scenario A: New York as
master validator

Scenario B: Rooms are
observed in their local city

New York LA Paris London New

York

New
York

London 42 74 19 -

Paris 42 74 - 19

Los
Angeles

Paris

Los
Angeles

London

LA 42 - 74 74

Paris

London

Fig. 5. Validation hierarchy with observer placement, and average network delay (ms)

chosen according to the geographical distance. 1 We inject transactions with a
load generator per process, which generates transaction requests at random times
with an adjustable average rate, measured in transactions per second (TPS) .All
processes have the same average. Once a lock is acquired, we assume a delay
of 2 ms per local operation. We do not model protocol overhead since network
latency is the dominating factor. In these experiments, no failures are injected.
Each item represents one hotel room at some date. We assume a “hotspot”
setting (e.g., a sale period) with only 10 items at each process. We have different
transaction types, and each transaction type will access either one room in one
city or two rooms (total) in two cities. Each load generator randomly selects a
transaction type according to the distribution given in Table 1. The rooms ac-
cessed are chosen randomly, and Book London represents a read and consecutive
write of one room in London. Correspondingly, Book London+Paris is the read
and consecutive write of one room in London and then one in Paris. We per-
formed four experiments, varying the overall target throughput between 20 and
60 transactions per second. We measured the abort rate and transaction latency,
i.e., the time between a request is submitted and it is successfully returned.

5.2 Results

The abort rate and average transaction latency for Scenarios A and B are shown
in Fig. 6. Decentralized validation allows FLACS to commit a significantly higher

1 The delays New York-Paris and New York-London are the same, assuming trans-
atlantic backbone links from each of these cities. The delay between Paris and Lon-
don reflect that network equipment and local lines increase delivery times.