05 02 2025 E TS

Page 1

Databases 2 - exam - February 5, 2025 - Dur. 2h S. Comai, P. Fraternali, D. Martinenghi A. Concurrency control (11 points) Consider a distributed system with three nodes (A, B, C) with the following wait-for conditions: NODE A: EB → t4; t4 → t7; t7 → t5; t5 → EC NODE B: EC → t1; t1 → t3; t3 → t2; t3 → t4; t4 → EA NODE C: EA → t5; t5 → t6; t6 → t8; t6 → t1; t1 → EB Apply the Obermarck algorithm and determine if a deadlock is detected, under the two following conventions: (1) A node X transmits to a downstream node Y the arc tj → ti if j > i. (4 points) (2) A node X transmits to a downstream node Y the arc tj → ti if j < i. (4 points) (3) Consider schedules comprising abort requests and explain why long duration write locks (i.e., strict 2PL locks for write operations) are required. (3 points) Solution. Exercise solutions, point 1 • Node A: EB → t4; t4 → t7; t7 → t5; t5 → EC; -- does not transmit • Node B: EC → t1; t1 → t3; t3 → t2; t3 → t4; t4 → EA; -- does not transmit • Node C: EA → t5; t5 → t6; t6 → t8; t6 → t1; t1 → EB; -- can transmit Exercise solutions, point 1 • Node C: • EA → t5; t5 → t6; t6 → t8; t6 → t1; t1 → EB; • sends EA → t5; → t1 → EB; to Node B • Node B EA → t5 EC → t1; t1 → t3; t3 → t2; t3 → t4; t4 → EA; EB • Sends EA → t5 → t4 → EA to Node A • Node A: EB → t4; t4 → t7; t7 → t5; t5 → EC; Exercise solutions, point 2 • Node A: EB → t4; t4 → t7; t7 → t5; t5 → EC; -- can transmit • Node B: EC → t1; t1 → t3; t3 → t2; t3 → t4; t4 → EA; -- can transmit • Node C: EA → t5; t5 → t6; t6 → t8; t6 → t1; t1 → EB; -- cannot transmit Exercise solutions, point 2 Node C: EA → t5; t5 → t6; t6 → t8; t6 → t1; t1 → EB; -- cannot transmit • Node C receives: EB → t4→ t5 → EC EB → t4 • Node A receives EC → t1 → t4 → EA Node A: EB → t4; t4 → t7; t7 → t5; t5 → EC; -- can transmit…