Is Transactional Locking 2 algorithm serializable?

Question

Consider two threads A and B

• A.readset intersects with B.writeset
• B.readset NOT intersect with A.writeset
• A.writeset NOT intersect with B.writeset

They commit at the same time: A.lock --> A.validation --> B.lock --> B.validation --> (A B installs updates)

Is this not serializable because B may overwrite A's reads before A commits?

Answer 1

It is serializable because the the value written to Transaction A's writeset depends on the cached value of A's readset which was confirmed during validation. The over-writing of A's readset by B does not affect the cached values of A's readset which A's writes are based on. The values written to Transaction A's writeset are exactly the same values that would have been written if transaction A ran to completion before transaction B started, so it's serializable.

EXAMPLE

We have a transactional memory consists of 3 variables X, Y, Z = X1, Y1, Z1

Transaction A reads X and writes Y with a value that depends on X (X + P) Transaction B reads Z and writes X with a value that depends on Z (Z + Q)

SERIALIZED EXECUTION

• Transaction A: locks Y, validates X = X1.
• Transaction A: sets Y = X1 + P and commits.
• Transaction B: locks X, validates Z = Z1.
• Transaction B: sets X = Z1 + Q and commits
• Final result: (X, Y, Z) = (Z1 + Q, X1 + P, Z1)

INTERLEAVED EXECUTION

• Transaction A: locks Y, validates X = X1.
• Transaction B: locks X, validates Z = Z1.
• Transaction B: sets X = Z1 + Q and commits (writes A's readset X before A commits)
• Transaction A: sets Y = X1 + P and commits (uses cached value of X not the latest value)
• Final result: (X, Y, Z) = (Z1 + Q, X1 + P, Z1) (same result as serial execution)