Questions

Section A: Multiple Choice Questions

Q1. Lock Compatibility and Conversions

In a system with multiple granularity locking, Transaction T1 holds an SIX lock on file F1. Transaction T2 wants to read record R5 in file F1. What sequence of locks does T2 need?

(A) IS on Database → IS on F1 → S on R5
(B) IS on Database → IX on F1 → S on R5
(C) S on Database → S on F1 → S on R5
(D) T2 cannot proceed as SIX conflicts with any access

Q2. Timestamp Ordering with Thomas' Write Rule

Given TS(T1) = 8, TS(T2) = 12, TS(T3) = 15. Data item Y has R-timestamp = 10, W-timestamp = 14. Operations: T1: Write(Y), T3: Read(Y), T2: Write(Y)

What happens under Thomas' Write Rule?

(A) T1 writes ignored, T3 reads successfully, T2 aborts
(B) T1 aborts, T3 reads successfully, T2 writes ignored
(C) T1 writes ignored, T3 aborts, T2 writes ignored
(D) All operations succeed with timestamps updated

Q3. Tree Protocol Validity

A database has hierarchical structure: Root → A → {B,C} → {D,E,F,G}. Transaction sequence: Lock(C) → Lock(F) → Unlock(C) → Lock(A) → Lock(B)

Is this sequence valid under Tree Protocol?

(A) Valid - follows parent-child rule
(B) Invalid - cannot lock A after unlocking C
(C) Invalid - must lock Root first
(D) Valid but inefficient

Q4. Wait-Die vs Wound-Wait Analysis

System has 5 transactions with timestamps: T1(5), T2(10), T3(15), T4(20), T5(25). Current state: T2 holds X-lock on item P, T4 holds S-lock on item Q. Requests: T1 wants P, T3 wants Q, T5 wants P.

Under Wait-Die scheme, which transactions will wait?

(A) T1 waits, T3 waits, T5 dies
(B) T1 waits, T3 dies, T5 dies
(C) T1 dies, T3 waits, T5 dies
(D) T1 waits, T3 waits, T5 waits

Q5. Optimistic Protocol Validation

Two transactions overlap: T6(Start=100, Validation=180, Finish=200) and T7(Start=150, Validation=220, Finish=250). T6 read set: {A,B,C}, write set: {A} T7 read set: {B,D}, write set: {D,E}

Will validation succeed?

(A) Both pass validation
(B) T6 passes, T7 fails
(C) T6 fails, T7 passes
(D) Both fail validation

Section B: Numerical and Analytical Questions

Q6. Deadlock Probability Analysis

A system processes 1000 transactions/second. Each transaction:

  • Duration: Exponentially distributed, mean = 50ms

  • Lock requests: Uniformly distributed between 2-6 locks per transaction

  • Data items: 500 total items in system

Given that deadlock probability ≈ (active_transactions²) × 0.0002:

Tasks:

  1. Calculate expected number of active transactions at any time (2 marks)

  2. Estimate deadlocks per second (2 marks)

  3. If deadlock detection runs every 200ms with cost 5ms × (active_transactions), calculate detection overhead percentage (2 marks)

  4. Find optimal detection interval to minimize total cost (detection + rollback cost = 100ms per deadlock) (2 marks)

Q7. Complex Timestamp Ordering Simulation

Database has items {P, Q, R} with initial values P=50, Q=75, R=100. Four transactions with operations:

T1 (TS=10): Read(P), Write(Q, Q+10), Read(R), Write(P, P-5)
T2 (TS=15): Write(R, R×2), Read(P), Write(R, R+25)  
T3 (TS=20): Read(Q), Write(P, P+15), Read(R)
T4 (TS=25): Write(Q, Q-10), Read(P), Write(R, R/2)

Schedule order: T1:Read(P), T2:Write(R), T1:Write(Q), T3:Read(Q), T2:Read(P), T4:Write(Q), T1:Read(R), T3:Write(P), T4:Read(P), T2:Write(R), T1:Write(P), T3:Read(R), T4:Write(R)

Tasks:

  1. Trace through each operation, showing allowed/abort decisions (4 marks)

  2. Update R-timestamp and W-timestamp after each allowed operation (3 marks)

  3. List final values of P, Q, R and which transactions committed (2 marks)

  4. Compare with Thomas' Write Rule - how many additional operations would succeed? (1 mark)

Q8. Multi-Granularity Lock Performance

Banking system hierarchy:

Database (1M accounts)
├── Region1 (300K accounts) ├── Region2 (400K accounts) ├── Region3 (300K accounts)
  ├── Branch1 (50K)           ├── Branch3 (100K)           ├── Branch5 (150K)
  ├── Branch2 (250K)          ├── Branch4 (300K)           ├── Branch6 (150K)

Transaction types (per hour):

  • Individual account access: 50,000 (1 account each)

  • Branch reports: 100 (entire branch each)

  • Regional analysis: 20 (entire region each)

  • System backup: 1 (entire database)

Tasks:

  1. Design optimal lock protocol using intention locks (2 marks)

  2. Calculate total lock operations per hour for each transaction type (3 marks)

  3. Estimate lock table memory requirements (assume 64 bytes per lock entry) (2 marks)

  4. Compare with simple exclusive locking on all accessed accounts (1 mark)

Section C: Conceptual and Design Questions

Q9. Protocol Comparison and Optimization

E-commerce system handles:

  • 80% Read transactions (product browsing)

  • 15% Update transactions (inventory updates)

  • 5% Complex transactions (order processing, multiple tables)

Average transaction characteristics:

  • Read: 2ms duration, accesses 3 items

  • Update: 8ms duration, accesses 5 items

  • Complex: 50ms duration, accesses 15 items

  • System load: 2000 transactions/second

Part A (6 marks): Compare three protocols for this workload:

  1. Strict 2PL with deadlock detection (every 100ms)

  2. Timestamp ordering with 20% rollback rate

  3. Optimistic protocol with 12% validation failure rate

Calculate expected response time for each transaction type under each protocol.

Part B (6 marks): Design a hybrid protocol that:

  • Uses different strategies for different transaction types

  • Minimizes overall system latency

  • Handles priority transactions (VIP customers)

Justify your design with calculations and trade-off analysis.

Q10. Advanced Deadlock Resolution

Consider a distributed database system with 4 sites. Transaction costs:

Transaction  Execution_Time  Items_Locked  Remaining_Work  Network_Hops
T1          120ms          8             30ms           2
T2          45ms           3             200ms          4  
T3          200ms          12            15ms           1
T4          80ms           5             100ms          3
T5          300ms          15            50ms           2

Current wait-for relationships form a cycle: T1→T2→T3→T4→T1, with T5 waiting for T3.

Tasks:

  1. Define a comprehensive cost function for victim selection considering: execution time, remaining work, number of items locked, and network communication cost (3 marks)

  2. Calculate cost for each transaction using your function (2 marks)

  3. Analyze the cascading effects if each transaction is chosen as victim (3 marks)

  4. Propose an algorithm that minimizes total system disruption, not just individual transaction cost (2 marks)

Section D: Simulation and Implementation

Q11. Lock Manager Implementation Challenge

Design a lock manager for a high-throughput OLTP system with these requirements:

System Specifications:

  • 10,000 concurrent transactions

  • 1M data items

  • 100,000 lock requests/second

  • Lock table memory limit: 512MB

  • Average transaction duration: 25ms

Part A - Data Structures (4 marks):

  1. Design efficient data structures for:

    • Lock table organization

    • Wait-for graph maintenance

    • Transaction tracking

  2. Analyze space complexity

Part B - Algorithms (4 marks):

  1. Implement lock request algorithm (pseudocode)

  2. Design deadlock detection with O(V+E) complexity

  3. Optimize for the given workload characteristics

Part C - Performance Analysis (4 marks):

  1. Calculate expected lock table size

  2. Estimate deadlock detection frequency needed

  3. Analyze bottlenecks and propose solutions

  4. Compare with alternative approaches (lock-free, timestamp-based)

Q12. Protocol Simulation Under Failure Conditions

Simulate a system where:

  • 30% of transactions abort due to user cancellation

  • 15% abort due to system failures

  • Network partitions occur every 500ms lasting 50ms

  • Recovery time after failure: 200ms

Scenario:

Initial state: 20 active transactions, various lock states
t=0: Network partition begins
t=30ms: 5 new transactions start
t=50ms: Network heals
t=75ms: System failure occurs
t=275ms: System recovers
t=400ms: Heavy load spike (50 new transactions)

Tasks:

  1. Model the system behavior under each event (3 marks)

  2. Calculate expected number of transactions that must restart (2 marks)

  3. Analyze lock table state evolution (2 marks)

  4. Propose resilience improvements (3 marks)

Section E: Research-Level Problems

Q13. Novel Lock Mode Design

Design a new lock mode called "Conditional Exclusive" (CX) for scientific databases where:

  • Transactions often need exclusive access only if certain conditions are met

  • Multiple CX locks can coexist if their conditions are mutually exclusive

  • CX lock can upgrade to X lock when condition is satisfied

Requirements:

  1. Define formal semantics and compatibility rules (5 marks)

  2. Prove that your protocol maintains serializability (4 marks)

  3. Analyze performance improvement over traditional X locks (3 marks)

  4. Handle edge cases and provide implementation strategy (3 marks)

Q14. AI-Optimized Deadlock Prevention

Design an ML-based system that predicts and prevents deadlocks by:

  • Learning transaction patterns from historical data

  • Predicting likely conflicts before they occur

  • Dynamically adjusting lock acquisition order

Given historical data:

  • 1 million transaction traces

  • Deadlock patterns show temporal clustering

  • Certain transaction combinations have 80% deadlock probability

Tasks:

  1. Design the prediction model architecture (4 marks)

  2. Define training data features and target variables (3 marks)

  3. Integrate predictions with lock manager decisions (4 marks)

  4. Analyze the trade-offs between prediction accuracy and system overhead (4 marks)

Updated on
Page 9: Deadlock Handling
Solutions