Once I thought 2PL ensures serializability while S2PL ensures strict serializability. However, I was wrong, as 2PL is already strong enough for strict serializability, with assumptions: clients do not abort transactions (which is hard), or the system commit dependent transactions.

The definition of 2PL is simple and clear. A transaction in 2PL is not able to grab locks once it starts to release locks. Consequently, the transaction’s life time can be divide into an expanding phase where the transaction keeps grabbing new locks, and a shrinking phase where the transaction keeps releasing locks. Intuitively, between these two phases, there will be a period of time where the transaction is holding all its locks and conducting its operations.

Let’s use \(H(T)\) to represent the time period of transaction $$T$ holding all its locks (we do not need to distinguish the start/end event of this period).

Consider two conflicting transactions \(T_1\) and \(T_2\). 2PL ensures that \(H(T_1)\) and \(H(T_2)\) has no overlap; because otherwise, during the overlapped time, \(T_1\) and \(T_2\) both hold the locks of their shared keys, breaking the semantic of locks.

Say \(H(T_1)\) is before \(H(T_2)\) in real time. Then, \(T_2\) must grab the locks of shared keys after \(T_1\) releasing them, i.e., \(T_2\) is serialized after \(T_1\), denoted by \(T_1 <_S T_2\). The direct proposition here is that 2PL ensures serializability: if there is a cycle in the dependency graph \(T_1 <_S .... <_S T_1\), it means that \(T_1\) grab locks after \(T_1\) release them, violating 2PL’s definition.

2PL also ensures strict serializability, which can be proved by contradiction. Suppose \(T_x\) finishes before \(T_y\) starts, but the serial order is \(T_y <_S ....<_S T_x\). This means \(T_x\) grabs some locks after \(T_y\) releasing them, contradicting with the assumption.

Therefore, 2PL is already enough for Strict Serializability.

TODO: S2PL