Uploaded byVincent Chu
Timestamp based protocol
The document discusses timestamp-based protocols for ensuring serializability in concurrent transactions. Each transaction is assigned a unique timestamp. Transactions are executed in timestamp order to prevent conflicts between read and write operations. For each data item, the protocol maintains a write-timestamp of the most recent write and a read-timestamp of the most recent read. Transactions with later timestamps cannot read or write values overwritten by earlier transactions. While this guarantees serializability, it can lead to cascading rollbacks if transactions abort.
In this document
Powered by AI
Introduction to timestamp-based protocols focused on concurrent transaction management.
Each transaction is assigned a timestamp to determine the serializability order of operations.
Two key timestamps are maintained for each data item: W-timestamp and R-timestamp for write/read operations.
Rules for read operations in timestamp-based protocols, including rollback conditions based on timestamps.
Conditions under which write operations are accepted or rejected based on timestamp comparisons.
Timestamp ordering guarantees serializability and prevents deadlock, though it may not be recoverable.
A problem with the timestamp protocol where aborting transactions can lead to cascading rollbacks.
Proposes structuring transactions so that writes occur at the end and restarting aborted transactions.
Timestamp based protocol
- 1.
- 2. Timestamp-Based ProtocolsEach transactionis issued a timestamp when it enters the system. If an old transaction Ti has time-stamp TS(Ti), a new transaction Tj is assigned time-stamp TS(Tj) such that TS(Ti) <TS(Tj). The protocol manages concurrent execution such that the time-stamps determine the serializability order.2010/5/22
- 3. Timestamp-Based ProtocolsIn orderto assure such behavior, the protocol maintains for each data Q two timestamp values:W-timestamp(Q) is the largest time-stamp of any transaction that executed write(Q) successfully.R-timestamp(Q) is the largest time-stamp of any transaction that executed read(Q) successfully.2010/5/23
- 4. Timestamp-Based ProtocolsThe timestampordering protocol ensures that any conflicting read and write operations are executed in timestamp order.Suppose a transaction Ti issues a read(Q) 1. If TS(Ti) W-timestamp(Q), then Ti needs to read a value of Q that was already overwritten. Hence, the read operation is rejected, and Ti is rolled back. 2. If TS(Ti)W-timestamp(Q), then the read operation is executed, and R-timestamp(Q) is set to the maximum of R- timestamp(Q) and TS(Ti).2010/5/24
- 5. Timestamp-Based ProtocolsSuppose thattransaction Ti issues write(Q).If TS(Ti) < R-timestamp(Q), then the value of Q that Ti is producing was needed previously, and the system assumed that that value would never be produced. Hence, the write operation is rejected, and Ti is rolled back.If TS(Ti) < W-timestamp(Q), then Ti is attempting to write an obsolete value of Q. Hence, this write operation is rejected, and Ti is rolled back.Otherwise, the write operation is executed, and W-timestamp(Q) is set to TS(Ti).2010/5/25
- 6. Timestamp-Based ProtocolsThe timestamp-orderingprotocol guarantees serializability since all the arcs in the precedence graph are of the form:Thus, there will be no cycles in the precedence graphTimestamp protocol ensures freedom from deadlock as no transaction ever waits. But the schedule may not be cascade-free, and may not even be recoverable.transactionwith largertimestamptransactionwith smallertimestamp2010/5/26
- 7. Timestamp-Based ProtocolsProblem withtimestamp-ordering protocol:Suppose Ti aborts, but Tj has read a data item written by TiThen Tjmust abort; if Tjhad been allowed to commit earlier, the schedule is not recoverable.Further, any transaction that has read a data item written by Tj must abortThis can lead to cascading rollback --- that is, a chain of rollbacks 2010/5/27
- 8. Timestamp-Based ProtocolsSolution:A transactionis structured such that its writes are all performed at the end of its processingAll writes of a transaction form an atomic action; no transaction may execute while a transaction is being written.A transaction that aborts is restarted with a new timestamp.2010/5/28