Question 5 of 6: Transaction Processing Techniques

Question 5: Transaction Processing Techniques

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

(a) A serially-equivalent interleaving of T and U.

Given. T: x = read(i); write(j,44);; U: write(i,55); write(j,66); (the assignment to x in U is a typo in the printed source, see the check note above, and does not affect the analysis). Initial values i = 10, j = 20.

Find. An interleaving of T's and U's operations, different from either transaction simply running start-to-finish before the other, that is still serially equivalent to one of the two possible serial orders T;U or U;T.

Approach. Two conflicting-operation pairs exist: T's read(i) against U's write(i,55), and T's write(j,44) against U's write(j,66). A schedule is serially equivalent exactly when, for every conflicting pair, the relative order they execute in is consistent with the SAME serial order for both pairs at once — simulated below.

1. Choose the interleaved execution order. Interleave the four operations as: T:read(i), U:write(i,55), T:write(j,44), U:write(j,66) — genuinely alternating between T and U rather than running either one to completion first.
2. Check the (T.read(i), U.write(i,55)) conflict. T's read executes before U's write, so T observes the pre-U value $i=10$ — identical to what T observes in the serial order T;U. This conflict is consistent with T preceding U.
3. Check the (T.write(j,44), U.write(j,66)) conflict. T's write executes before U's write, so U's write is the last one to touch j and its value survives — final $j=66$, identical to serial order T;U. This conflict is also consistent with T preceding U.
4. Conclude equivalence. Both conflicting pairs are consistent with the same serial order (T before U), so the interleaved schedule is conflict-equivalent to T;U. $$\boxed{\text{Interleaving: T:read(i)}\to\text{U:write(i,55)}\to\text{T:write(j,44)}\to\text{U:write(j,66)}\ \equiv\ \text{serial } T;U}$$ Final state: $i=55$, $j=66$; T's read observed the original $i=10$ — exactly matching what a genuinely serial execution of T followed by U would have produced.

(b) Deadlock: definition, prevention, avoidance, detection, recovery. A deadlock is a state in which a set of processes are each waiting for a resource held by another process in the same set, so that none of them can ever proceed — formally, a cycle exists in the wait-for graph. Deadlock requires all four Coffman conditions simultaneously: mutual exclusion (a resource can be held by only one process at a time), hold-and-wait (a process holding a resource may request another), no preemption (a resource cannot be forcibly taken from its holder), and circular wait (a cycle of processes each waiting on the next). Prevention removes one of these conditions structurally — the most common technique is imposing a global total ordering on resource acquisition (every process must request resources in the same fixed order), which makes circular wait impossible: e.g. two bank-transfer transactions that must each lock accounts A and B are both required to lock the lower account number first, so neither can end up holding A and waiting for B while the other holds B and waits for A. Avoidance allows the conditions to hold but refuses any resource request that would move the system into an unsafe state, e.g. the Banker's algorithm, which grants a request only if a safe sequence still exists in which every process could still finish given its declared maximum future need. Detection lets deadlocks occur and periodically searches the wait-for graph (or a distributed edge-chasing/probe algorithm across nodes, since no single node sees the whole graph in a distributed system) for cycles. Recovery once a deadlock is detected typically means aborting or rolling back one or more of the deadlocked transactions/processes (chosen e.g. by lowest priority or least work already done) so its resources are released, or preempting a resource from one victim and giving it to another, then restarting the victim. A concrete scenario: the classic dining philosophers, where each philosopher (process) holds their left fork (resource) and waits for their right fork, held by their neighbour — a perfect circular wait; and a database example of two concurrent transactions each locking a different row and then requesting the other's row in reverse order, which a lock-ordering rule (prevention) or a periodic wait-for-graph scan (detection, with one transaction aborted to recover) both resolve.

(c) Two-phase commit protocol. Two-phase commit (2PC) coordinates an atomic outcome (all commit, or all abort) for a transaction spanning multiple participants, driven by one coordinator.

Coordinator:
  write START_2PC to local log
  send VOTE_REQUEST to all participants
  wait for VOTE_COMMIT or VOTE_ABORT from every participant (or timeout)
  if all participants voted VOTE_COMMIT:
      write GLOBAL_COMMIT to log
      send GLOBAL_COMMIT to all participants
  else:
      write GLOBAL_ABORT to log
      send GLOBAL_ABORT to all participants
  wait for ACK from every participant
  write COMPLETE to log

Participant:
  wait for VOTE_REQUEST
  if local work can be committed:
      write READY to log
      send VOTE_COMMIT to coordinator
      wait for GLOBAL_COMMIT or GLOBAL_ABORT (or timeout -> ask other
        participants / block until coordinator recovers)
  else:
      write ABORT to log
      send VOTE_ABORT to coordinator
      abort locally
  on receiving GLOBAL_COMMIT: commit locally; send ACK
  on receiving GLOBAL_ABORT: abort locally; send ACK

Phase 1 (voting/prepare): the coordinator asks every participant whether it can commit its part of the transaction; each participant makes its own local decision, durably logs it, and votes COMMIT or ABORT. Phase 2 (commit/decision): once the coordinator has every vote, it decides — GLOBAL_COMMIT only if every vote was COMMIT, GLOBAL_ABORT if any participant voted ABORT (or failed to respond) — logs that decision durably, and broadcasts it; every participant then carries out that decision and acknowledges. The protocol guarantees atomicity across all participants, but a participant that has voted COMMIT and is then waiting for the coordinator's decision is blocked if the coordinator crashes at that point — it can neither commit nor abort safely on its own, which is 2PC's well-known availability weakness (addressed by protocols such as three-phase commit at the cost of extra message rounds).

(d) ACID properties. Atomicity — a transaction's effects are all-or-nothing; e.g. a funds transfer that debits account A and credits account B must never be left half-done (debited but not credited) even if the system crashes between the two writes. Consistency — a transaction takes the database from one valid state to another, preserving all declared invariants (constraints, triggers); e.g. a transfer must never leave the sum of A's and B's balances different from before it ran. Isolation — concurrently executing transactions must not observe each other's intermediate, uncommitted state, i.e. the combined effect must be equivalent to some serial execution (exactly the property demonstrated in part (a)); e.g. two simultaneous transfers out of the same account must not both read the same starting balance and overdraw it. Durability — once a transaction commits, its effects survive any subsequent crash (guaranteed by writing to stable/logged storage before acknowledging the commit, as the 2PC log writes in part (c) illustrate); e.g. a committed transfer must still be reflected in the balances after a server reboot.