The Gateway to Computer Science Excellence
+32 votes

Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock?

  1. 2-phase locking
  2. Time-stamp ordering
    1. I only
    2. II only
    3. Both I and II
    4. Neither I nor II
in Databases by Veteran (105k points)
edited by | 7.8k views

6 Answers

+42 votes
Best answer
In basic two phase locking there is a chance for deadlock

Conservative 2pl is deadlock free

I go with B.
by Boss (11k points)
edited by
In the question it's just mentioned 2pl locking. They haven't mentioned which version on 2pl. Of course basic 2pl has deadlock problem. It could also be conservative or strict. So how to decide?
Two phase locking ensures only conflict serializability, whereas time stamp ensure both.
Basic 2PL==>(ensure serializability) + (but deadlock and starvation possible).

Strict 2PL ==>(ensure serializability) +(ensure recoverability) + (but deadlock and starvation possible).

Conservative 2PL ==>(ensure serializability)+ (no deadlock) +(but starvation possible).

time stamp ordering ==>(ensure serializability)+ (no deadlock) +(avoid starvation by using wait-die and wound -wait scheme).
Rigorous 2PL ==> (ensure serializability) + (no cascading rollback)+ (but deadlock and starvation possible)

strict 2PL and rigorous  2PL both produce strict schedule so by the definition  both will be recoverable . where as conservative 2PL may produce cascading (means not cascadeless) schedule .

must read given link

one more point : deadlock has been taken care by locking strategy but cascading is care by unlocking strategy.

+12 votes
Answer is B.

2PL ensures conflict serializability but is not deadlock free.

Timestamp ordering ensures conflict serializability because if any action causes violation in serializability order that was being followed from beginning of schedule, then the transaction is rolled back and again started with new timestamp.

It also ensures freedom from deadlock because there are no locks.. which means no mutual exclusion.
by Active (1.3k points)
+8 votes

Timestamp Based Ordering Protocol is :

by Loyal (7.9k points)
+5 votes

Two phase locking ensures conflict serializable schedules, but does not ensure freedom from deadlock.

One the other hand, Timestamp ordering protocol ensures freedom from deadlock but does not ensure conflict serializable schedules.

ensure = every schedule is conflict serializable. Hence the answer is D


Additional info: Tree based protocol ensures both, freedom from deadlocks and conflict serializable schedule.

by Active (3.6k points)

The timestamp-ordering protocol guarantees serializability since

all the arcs in the precedence graph are of the form one node to other thus there will be no cycle in the graph.

In TO protocol if any conflict pair does not follow the order then it is rollback , because we consider conflict action so schedule must conflict serializable.

so option B correct


Timestamp ordering protocol 

  • Conflict serializable
  • Deadlock free
  • but maynot Starvation free
+2 votes

2 Phase Locking (2PL) is a concurrency control method that guarantees serializability. The protocol utilizes locks, applied by a transaction to data, which may block (interpreted as signals to stop) other transactions from accessing the same data during the transaction’s life. 2PL may be lead to deadlocks that result from the mutual blocking of two or more transactions. See the following situation, neither T3 nor T4 can make progress.

Timestamp-based concurrency control algorithm is a non-lock concurrency control method. In Timestamp based method, deadlock cannot occur as no transaction ever waits.

by Boss (10.2k points)
0 votes
B is answer
by Junior (817 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,370 answers
105,272 users