72 72 votes Which of the following concurrency control protocols ensure both conflict serializability and freedom from deadlock? $2$-phase locking Time-stamp ordering I only II only Both I and II Neither I nor II Databases gatecse-2010 databases transaction-and-concurrency normal + – go_editor 33.6k views answer comment Share Follow Print See all 7 Comments 7 7 Comments reply Show 4 previous comments P0535_Yedidyah_Sagar commented Jan 19 i edited by P0535_Yedidyah_Sagar May 17 reply Follow flag $ \begin{array}{|l|c|c|c|c|c|c|} \hline Protocol & Serializable? & Deadlock\ Possible? & Starvation\ Freedom? & Cascading\ Freedom? & Recoverability? & Strict? \\ \hline Basic\ 2PL & CSR & Yes & No & No & No & No \\ \hline Strict\ 2PL & CSR & Yes & No & Yes & Yes & Yes \\ \hline Rigorous\ 2PL & CSR & Yes & No & Yes & Yes & Yes \\ \hline Conservative\ (Static)\ 2PL & CSR & No & No & No & No & No \\ \hline Graph\text{-}based\ (Tree)\ Protocol & CSR & No & No & No & No & No \\ \hline Timestamp\ Ordering\ Protocol & CSR & No & No & No & No & No \\ \hline Thomas\ Write\ Rule & VSR\ (not\ CSR) & No & No & No & No & No \\ \hline Validation\text{-}Based\ (Optimistic\ CC) & CSR & No & No & No & No & No \\ \hline \end{array} $ Interpretation for column 1 (Serializable?) : $If\ a\ DBMS\ uses\ protocol\ P,\ what\ kind\ of\ schedules\ can\ it\ produce?$ Interpretation for columns 3-6 : $Does\ the\ protocol\ guarantee\ that\ property\ for\ all\ schedules\ it\ produces?$ $Theory :$ Strict $=$ No dirty reads and no dirty writes Cascadeless $=$ No dirty reads $Recoverable\ Schedule:$ If one transaction reads a value written by another transaction, then the writing transaction must commit before the reading transaction commits. $$ read\ by\ T_2\ from\ T_1 \Rightarrow commit\ of\ T_1\ before\ commit\ of\ T_2 $$ $Cascadeless\ (cascading-free)\ schedule:$ A transaction is allowed to read a value only after the transaction that wrote that value has committed. This means dirty reads are not allowed. $$ read\ by\ T_2\ from\ T_1 \Rightarrow commit\ of\ T_1\ before\ the\ read\ of\ T_2 $$ $Strict\ schedule:$ A transaction is not allowed to read or write a value until the transaction that last wrote that value has committed. This means neither dirty reads nor dirty writes are allowed. $$ write\ by\ T_1\ on\ X \Rightarrow commit\ of\ T_1\ before\ any\ read\ or\ write\ on\ X\ by\ others $$ $Implication:$ $$ Strict \Rightarrow Cascadeless \Rightarrow Recoverable $$ In a strict schedule, no transaction can read uncommitted data, so it is cascadeless. In a cascadeless schedule, a transaction can read only committed data, so it cannot commit before the transaction it read from. Therefore, every strict schedule is cascadeless, and every cascadeless schedule is recoverable. Optimistic CC $=$ Optimistic Concurrency Control 5 5 replyShare Strange commented Aug 12 reply Follow flag 2PL: Basic 2PL gives Conflict Serializability (CS) but allows deadlocks. Its Conservative 2PL variation gives CS + Deadlock Freedom, while Rigorous/Strict 2PL gives CS + Recoverability/No Cascading Aborts.TSP: Basic TSP gives CS + Deadlock Freedom. Adding Thomas Write Rule allows non-CS schedules that are View Serializable (VS) + Deadlock Free. 1 1 replyShare Jayvijay Chauhan commented Sep 22 reply Follow flag @jaswanth431 correct using AI Corrections NeededGraph-Based Protocol (Missing Entry for Starvation): Issue: The Starvation possible? cell is left blank.Correction: It should be Yes (starvation can occur if a transaction is repeatedly denied access due to other active transactions holding locks higher up in the graph).Rigorous 2PL (Generated Schedules): Issue: It lists "Strict schedules".Correction: While all rigorous schedules are strict, it specifically produces Rigorous schedules. Difference: Strict 2PL holds all exclusive (write) locks until commit. Rigorous 2PL holds both shared (read) and exclusive (write) locks until commit.Thomas Write Rule (Serializability Type - Clarification): Clarification: Under Serializable Schedules?, it states Yes. While correct, note that Thomas Write Rule generates View Serializable schedules that are not Conflict Serializable (due to ignoring outdated writes). Every other protocol listed generates Conflict Serializable schedules.Corrected Summary TableProtocolSerializable?Deadlock possible?Starvation possible?Generated SchedulesBasic 2PLYes (Conflict)YesYesMay not be recoverableStrict 2PLYes (Conflict)YesYesStrict & CascadelessRigorous 2PLYes (Conflict)YesYesRigorous & CascadelessConservative 2PLYes (Conflict)NoYesMay not be recoverableGraph-Based ProtocolYes (Conflict)NoYes (Was blank)May not be recoverableTimestamp OrderingYes (Conflict)NoYesMay not be recoverableThomas Write RuleYes (View)NoYesView Serializable (Not Conflict) 0 0 replyShare Please log in or register to add a comment.
Best answer 77 77 votes In basic two phase locking there is a chance for deadlock Conservative $\text{2pl}$ is deadlock free I go with B. Sankaranarayanan P.N answered Nov 16, 2014 • edited Jun 17, 2021 by Lakshman Bhaiya Sankaranarayanan P.N comment Share Follow See all 13 Comments 13 13 Comments reply Show 10 previous comments rhl commented May 31, 2023 reply Follow flag @vaibhavkedia968 starvation is avoided by ensuring that transactions are restarted with the same timestamp instead of a new timestamp But if the transaction starts with old Timestamp then it will lead to starvation. I think the transaction will start with a new timestamp. 0 0 replyShare Prashant_Dubey commented Jan 27, 2024 i edited by Prashant_Dubey Jan 27, 2024 reply Follow flag @rhl IN wound -wait condition case, lets say Tj is holding the lock on A , and Ti is req for the lock on A, now say TS(Ti)<TS(Tj) then Ti will wound/aborts Tj . And if it starts with the new time then it will gets always aborted by the older Transaction. According to you then this ques. will be wrong Databases: GATE CSE 2017 Set 1 | Question: 42 (gateoverflow.in) 0 0 replyShare rhl commented Dec 23, 2025 i edited by rhl Dec 23, 2025 reply Follow flag @Prashant_Dubey wound-wait scheme is used in lock based protocols for deadlock prevention. Since timestamp based protocols don't use locks, they don't have deadlocks, hence no scheme needed for the same. What i was trying to say that iif we restart a transaction with older timestamp, then it would be aborted again since its time has already passed. Starting it with newer timestamp would be correct i think. 0 0 replyShare Please log in or register to add a comment.
23 23 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. Rajendra Dangwal answered Oct 13, 2016 Rajendra Dangwal comment Share Follow 0 reply Please log in or register to add a comment.
11 11 votes Timestamp Based Ordering Protocol is : Conflict serializable i.e. it is conflict equivalent to some serial schedule. It is deadlock free because timestamp ordering protocol allows rollback and restart it after detecting a mismatched situation. http://www.edugrabs.com/timestamp-ordering-protocols/ set2018 answered Aug 1, 2017 set2018 comment Share Follow 0 reply Please log in or register to add a comment.
6 6 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 Reference: http://codex.cs.yale.edu/avi/db-book/db4/slide-dir/ch16-2.pdf Additional info: Tree based protocol ensures both, freedom from deadlocks and conflict serializable schedule. ryan sequeira answered Jan 18, 2016 ryan sequeira comment Share Follow See all 2 Comments 2 2 Comments reply abc11 commented Jul 12, 2016 reply Follow flag 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 4 4 replyShare srestha commented Sep 28, 2019 reply Follow flag Timestamp ordering protocol Conflict serializable Deadlock free but maynot Starvation free 0 0 replyShare Please log in or register to add a comment.
4 4 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. Paras Nath answered Apr 16, 2018 Paras Nath comment Share Follow 0 reply Please log in or register to add a comment.
2 2 votes BEST ANSWER2PL ensures conflict serializability but there is a chance for deadlockTimestamp Based Ordering Protocol is :Conflict serializable i.e. it is conflict equivalent to some serial schedule.It is deadlock free because timestamp ordering protocol allows rollback and restart it after detecting a mismatched situation. akshay_123 answered Jul 5, 2025 akshay_123 comment Share Follow See 1 comment 1 1 comment reply Kshitij_Rabadey commented Jan 8 reply Follow flag thanks 1 1 replyShare Please log in or register to add a comment.
