Mod 6

Transaction Processing Concepts
Transaction Processing
• A transaction is an action, or series of actions that are being
performed by a single user or application program, which reads or
updates the contents of the database.
• A transaction is a set of logically related operations.
• For example, you are transferring money from your bank account to
your friend’s account, the set of operations would be like this:
• Simple Transaction Example
1. Read your account balance
2. Deduct the amount from your balance
3. Write the remaining balance to your account
4. Read your friend’s account balance
5. Add the amount to his account balance
6. Write the new updated balance to his account
2
• Let’s take an example of a simple transaction.
Suppose a bank employee transfers Rs 500
from A's account to B's account. This very
simple and small transaction involves several
low-level tasks.
3
4
Transaction states and additional
operations
• A transaction is an atomic unit of work that is either completed in
its entirety or not done at all.
• For recovery purposes the system needs to keep track of when
the transaction starts, terminates, and commits or aborts.
• The recovery manager keeps track of the following operations :
– BEGIN_TRANSACTION
– READ OR WRITE
– COMMIT_TRANSACTION
– ROLLBACK
– END_TRANSACTION
5
Transaction States
IS 533 - Transactions 6
Transaction States
• Active − In this state, the transaction is being
executed. This is the initial state of every
transaction.
• Partially Committed − When a transaction
executes its final operation, it is said to be in a
partially committed state.
• Failed − A transaction is in this state once the
normal execution of the transaction cannot
proceed. A failed transaction can no longer
proceed further.
Transaction States
• Aborted − If any of the checks fails and the
transaction has reached a failed state, then the
recovery manager rolls back all its write
operations on the database to bring the database
back to its original state where it was prior to the
execution of the transaction. Transactions in this
state are called aborted. The database recovery
module can select one of the two operations
after a transaction aborts −
– Re-start the transaction
– Kill the transaction
Transaction States
• Committed − If a transaction executes all its
operations successfully, it is said to be
committed. All its effects are now
permanently established on the database
system.
9
Desirable Properties of transactions
• There are properties that all transactions should

follow and possess. The four basic are in
combination termed as ACID properties.
• ACID properties of transactions :
– Atomicity : a transaction is an atomic unit of processing; it is
either performed entirely or not performed at all.
(It is the responsibility of recovery)
– Consistency : transfer the database from one consistent state

to another consistent state
(It is the responsibility of the applications)
10
Desirable Properties of transactions (continued)
– Isolation : the execution of the transaction should be

isolated from other transactions (Locking)
(It is the responsibility of concurrency)
* Isolation level:
-Level 0 (no dirty read) -Level 1 ( no lost update)
-Level 2 (no dirty+ no lost) -Level 3 (level 2+repeatable reads)
– Durability : committed transactions must persist in the

database ,i.e. those changes must not be lost because of
any failure.
(It is the responsibility of recovery)
11
Schedules
• A schedule is a sequence of read, write, abort
and commit operations from a set of
transactions.
• Each schedule must preserve the order of the
operations in its constituent transactions.
Schedules
• Types of Schedules
– Serial Schedules
– Parallel Schedules
Schedules
– Serial Schedules
In a serial schedule, at any point of time,
only one transaction is active, i.e. there is no
overlapping of transactions.
Schedules
– Non-serial or Parallel/ concurrent Schedules
In parallel schedules, more than one
transactions are active simultaneously, i.e. the
transactions contain operations that overlap at
time.
Characterizing Schedules based on
Recoverability
• Type of schedules :
– Recoverable : If T2 is reading value updated by T1
and commit of T2 is delayed till commit of T1 , the
schedule is called recoverable.
– Irrecoverable Schedule: When T2 is reading the

value updated by T1 and T2 is committed before
commit of T1, the schedule will be irrecoverable.
18
Schedules and Conflicts
• Conflict in Schedules
– In a schedule comprising of multiple transactions,
a conflict occurs when two active transactions
perform non-compatible operations. Two
operations are said to be in conflict, when all of
the following three conditions exists
simultaneously −
• The two operations are parts of different transactions.
• Both the operations access the same data item.
• At least one of the operations is a write_item()
operation, i.e. it tries to modify the data item.
Read and Write Operation Conflict
Rules
Operations of different Conflict Reason
transactions
read read No Because the effect of a pair of read operations
does not depend on the order in which they are
executed
read write Yes Because the effect of a read and a write operation
depends on the order of their execution
write write Yes Because the effect of a pair of write operations
depends on the order of their execution
Conflicting operations may give rise
to the following anomalies:
• Dirty read problem/Read uncommitted

data(WR)
• Unrepeatable Read Problem (RW)
• Lost update problem (WW)

Dirty read problem
Unrepeatable Read Problem
Lost update problem / Write-Write
conflict Problem
Conflict Serializability
• When multiple transactions run concurrently,
then it may give rise to inconsistency of the
database.
• Serializability is a concept that helps to identify
which non-serial schedules are correct and will
maintain the consistency of the database.
• A schedule is called conflict serializable if it can

be transformed into a serial schedule by
swapping non-conflicting operations.
• Conflicting operations pair (R1(A), W2(A)) because
they belong to two different transactions on
same data item A and one of them is write
operation.
• Similarly, (W1(A), W2(A)) and (W1(A), R2(A)) pairs
are also conflicting.
• On the other hand, (R1(A), W2(B)) pair is non-
conflicting because they operate on different
data item.
• Similarly, ((W1(A), W2(B)) pair is non-conflicting.
Transaction Structure
 Flat transaction
 Consists of a sequence of primitive operations embraced
between a begin and end markers.
Begin_transaction Reservation
…
end.
 Nested transaction
 The operations of a transaction may themselves be
transactions.
Begin_transaction Reservation
…
Begin_transaction Airline
 …
end. {Airline}
Begin_transaction Hotel
…
end. {Hotel}
end. {Reservation}
Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 2
Nested Transactions
 Have the same properties as their parents may

themselves have other nested transactions.
 Introduces concurrency control and recovery concepts
to within the transaction.
 Types
 Closed nesting
 Subtransactions begin after their parents and finish
before them.
 Commitment of a subtransaction is conditional upon the
commitment of the parent (commitment through the
root).
 Open nesting
 Subtransactions can execute and commit
independently.
 Compensation may be necessary.

Database Concurrency Control
 1 Purpose of Concurrency Control
 To enforce Isolation (through mutual exclusion) among
conflicting transactions.
 To preserve database consistency through consistency
preserving execution of transactions.
 To resolve read-write and write-write conflicts.
 Example:
 In concurrent execution environment if T1 conflicts with T2
over a data item A, then the existing concurrency control
decides if T1 or T2 should get the A and if the other
transaction is rolled-back or waits.

 If 2 or more transaction are made 2 execute
concurrently then they should result in a consistent
state after the execution of all the transactions same as
prior to their execution i.e they should be serializable
schedule.
 A number of concurrency control techniques are applied

in a concurrent database and one type of technique is
locking the data item to prevent multiple transaction
from accessing the items concurrently.
 Another set of protocol use timestamp.

 Lock Manager:
 Managing locks on data items.
 Lock table:
 Lock manager uses it to store the identity of
transaction locking a data item, the data item, lock
mode and pointer to the next data item locked. One
simple way to implement a lock table is through
linked list.
Transaction ID Data item id lock mode Ptr to next data item

T1 X1 Read Next

 Database requires that all transactions should be
well-formed. A transaction is well-formed if:
 It must lock the data item before it reads or writes to
it.
 It must not lock an already locked data items and it
must not try to unlock a free data item.

 Locking technique: A lock is a variable associated
with each data item that describes the status of the
item with respect to possible operations that can be
applied to it.
 Types of lock: depending upon types of lock the data
manager gives or denies access to other operations
on the same data item
 Binary Locks: will have 2 values locked and unlocked
represented as 0 and 1.
 A transaction sends a request to a datamanager to
access to a dataitem by first locking the data item using
LOCK() operation.
 Transcation tries to access same data item then it is
forced to wait untill the transaction (previous one) that
has locked the dataitem unlock the data item using
unlocked command.
 Few rules must be followed when binary locking
technique is used.
 LOCK() : operation must be issued by transaction
before any update operation like read() or write()
operation are performed on transaction.
 LOCK() :can’t be issued by transaction if already
holds LOCK() on data item
 UNLOCK() : must be issued after all read() and
write() operations are completed in a transaction.
 UNLOCK(): can’t be issued by transaction unless it
already hold the lock on the data item.
Example for binary lock
 T1:LOCK(A)  This example is

 T1:READ(A) A=100 seriazible
 T1:A:=A+200 A=300 schedule.Therefore, in
 T1:WRITE(A) A=300
case of a binary locking
 T1:UNLOCK(A) mechanism atmost one
 T2:LOCK(A) transaction can hold the
 T2:READ(A)
lock on a particular
 T2:A:=A+300 A=600
dataitem .Thus no
 T2:WRITE(A)A=600
transaction can access
the same item
 T2:UNLOCK(A)
concurrently.

Read Write
Read
Y N
Write
N N

Pitfalls of Lock-Based Protocols
 Consider the partial schedule
 Neither T3 nor T4 can make progress — executing lock-S(B)

causes T4 to wait for T3 to release its lock on B, while executing
lock-X(A) causes T3 to wait for T4 to release its lock on A.
 Such a situation is called a deadlock.
 To handle a deadlock one of T3 or T4 must be rolled back
and its locks released.
Locking protocols
Locking Protocol: to ensure the Serializability

1. Two-phase locking (2PL)
2. Non-two-phase locking (skip)

tree protocol locking
directed acyclic graph protocol

Two-Phase Locking Techniques: The algorithm
 Two Phases:
 (a) Locking (Growing)
 (b) Unlocking (Shrinking).
 Locking (Growing) Phase:

 A transaction applies locks (read or write) on desired data items
one at a time.
 Unlocking (Shrinking) Phase:
 A transaction unlocks its locked data items one at a time.
 Requirement:
 For a transaction these two phases must be mutually exclusively,
that is, during locking phase unlocking phase must not start and
during unlocking phase locking phase must not begin.

2 Phase Locking protocol
 A protocol that guarantees serializability.
 A transaction obeying the two-phase locking
protocol (2PL) if
<a> before operating on any object, the transaction first
acquires a
lock on that object (the locking phase)
<b> after releasing a lock, the transaction never acquires
any more
lock (the unlocking phase )
i.e. in any transaction, all locks must precede all unlock.

T1 T2 Result
read_lock (Y); X=50; Y=50
read_item (Y); Nonserializable because it.
unlock (Y); violated two-phase policy.
read_lock (X);
read_item (X);
unlock (X);
Time write_lock (Y);
read_item (Y);
Y:=X+Y;
write_item (Y);
unlock (Y);
write_lock (X);
read_item (X);
X:=X+Y;
write_item (X);
unlock (X);

 <e.g.>
 T1: T2: T3:
 LOCK A LOCK A LOCK B
 LOCK B LOCK C LOCK C
 UNLOCK A UNLOCK C UNLOCK B
 UNLOCK B UNLOCK A LOCK A
 UNLOCK C
 UNLOCK A
 T1 obey 2PL
 T2 obey 2PL
 T3 not obey 2PL

T’1 T’2
read_lock (Y); read_lock (X); T1 and T2 follow two-phase
read_item (Y); read_item (X); policy but they are subject to
write_lock (X); Write_lock (Y); deadlock, which must be
unlock (Y); unlock (X); dealt with.
read_item (X); read_item (Y);
X:=X+Y; Y:=X+Y;
write_item (X); write_item (Y);
unlock (X); unlock (Y);

Two Phase locking protocols types
 Basic 2 PL
 Conservative 2 PL
 Strict 2 PL
 Rigorous 2PL

Timestamp based concurrency control algorithm
 Timestamp
 A monotonically increasing variable (integer)

indicating the age of an operation or a transaction.
A larger timestamp value indicates a more recent
event or operation.
 Timestamp based algorithm uses timestamp to
serialize the execution of concurrent transactions.

Time Stamps
 How timestamps are used ?
<i> Each transaction, T, is assigned a timestamp, t, say t(T)
<ii> Each data item, d, is assigned two timestamps:
(1) Read time, tr(d), the highest transaction timestamp that have read
the item.
(2) Write time, tw(d), the highest transaction timestamp that have
written the item.
<iii> When reading an item, d, by T:
if t(T) > tw(d)
then (1) execute read operation
(2) tr(d) = max {tr(d), t(T)}
else abort.
<iv> When writing an item, d, by T:
if t(T)  tr(d) and t(T)  tw(d)
then (1) execute the write operation.
(2) tw(d) = max {tw(d), t(T)}
else abort
 Basic Timestamp Ordering
 1. Transaction T issues a write_item(X) operation:

 If read_TS(X) > TS(T) or if write_TS(X) > TS(T), then an
younger transaction has already read the data item so abort
and roll-back T and reject the operation.
 If the condition in part (a) does not exist, then execute
write_item(X) of T and set write_TS(X) to TS(T).
 2. Transaction T issues a read_item(X) operation:
 If write_TS(X) > TS(T), then an younger transaction has
already written to the data item so abort and roll-back T and
reject the operation.
 If write_TS(X)  TS(T), then execute read_item(X) of T and set
read_TS(X) to the larger of TS(T) and the current read_TS(X).

 Strict Timestamp Ordering
 1. Transaction T issues a write_item(X) operation:

 If TS(T) > read_TS(X), then delay T until the
transaction T’ that wrote or read X has terminated
(committed or aborted).
 2. Transaction T issues a read_item(X) operation:
 If TS(T) > write_TS(X), then delay T until the
transaction T’ that wrote or read X has terminated
(committed or aborted).

 Thomas’s Write Rule
 If read_TS(X) > TS(T) then abort and roll-back T

and reject the operation.
 If write_TS(X) > TS(T), then just ignore the write
operation and continue execution. This is because
the most recent writes counts in case of two
consecutive writes.
 If the conditions given in 1 and 2 above do not
occur, then execute write_item(X) of T and set
write_TS(X) to TS(T).

Two - Phase Locking Protocol and
Distributed Transactions
Aditya Deepak Joshi - 19BCE0257
Rajarshi Bhattacharyay - 19BCE0296
Aayushi Tiwari - 19BCE0666
Two - Phase Locking Protocol
• A transaction is said to follow the two-phase locking protocol if all locking operations (read_lock,
write_lock) precede the first unlock operation in the transaction.
• Each transaction should have two phases: (a) Locking (Growing) phase, and (b) Unlocking (Shrinking)
Phase.
Locking (Growing) Phase: A transaction applies locks (read or write) on desired data items one at a time.
Can also try to upgrade a lock.
Unlocking (Shrinking) Phase: A transaction unlocks its locked data items one at a time. Can also
downgrade a lock.
• Requirement: For a transaction these two phases must be mutually exclusively, that is, during locking
phase no unlocking or downgrading of locks can occur, and during unlocking phase no new locking or
upgrading operations are allowed.
Basic Two Phase Locking -
• When transaction starts executing, it is in the locking phase, and it can request locks on new items or
upgrade locks. A transaction may be blocked (forced to wait) if a lock request is not granted. This may lead
to several transactions being in a state of deadlock.
Once the transaction unlocks an item (or downgrades a lock), it starts its shrinking phase and can no
longer upgrade locks or request new locks.
The combination of locking rules and 2-phase rule ensures serializable schedules.
Theorem: If every transaction in a schedule follows the 2PL rules, the schedule must be serializable.
(Proof is by contradiction.)
Drawbacks of Two Phase Locking Protocol
• Might not be free from irrecoverability.

• Not free from deadlocks.
• Not free of starvation.
• Not free of cascading rollbacks.
Other Types of Two-Phase Locking -
• Conservative 2PL: A transaction must lock all its items before starting execution. If any item it needs is
not available, it locks no items and tries again later. Conservative 2PL has no deadlocks since no lock
requests are issued once transaction execution starts.
• Strict 2PL: All items that are exclusive locked by a transaction are not released (unlocked) until after the
transaction commits. This is the most commonly used two-phase locking algorithm, and ensures strict
schedules (for recoverability and cascadless rollbacks).
• Rigorous 2PL: All items that are shared locked or exclusive locked by a transaction are not released
(unlocked) until after the transaction commits. Also guarantees strict schedules.
Distributed Transactions
• A distributed transaction is a set of operations on data that is performed across two or more data
repositories (especially databases). It is typically coordinated across separate nodes connected by a network,
but may also span multiple databases on a single server.
• Just like centralized transactions, distributed transactions also support ACID properties :
A - Atomicity C - consistency I - isolation D - Durability
• Why do we need Distributed Transactions? Some of the ACID properties are harder to implement in
centralized transaction system, AND basic single - system Techniques( in centralized system ) are always
not sufficient.
If client runs transaction then each transaction must complete
before proceedding to the next.
If transactions are nested then transactions at the same level
can run in parallel
clients use a single server to act as co-ordinator for all other
transactions. The co-ordinator handles all communication
with other servers.
Servers for a distributed transaction need to coordinate their actions.

A client starts a transaction by sending an openTransaction request to a coordinator. The coordinator returns the
TID to the client. The TID must be unique (serverIP and number unique to that server)
Coordinator is responsible for committing or aborting it. Each other server in a transaction is a participant.
Participants are responsible for cooperating with the coordinator in carrying out the commit protocol, and keep
track of all recoverable objects managed by it.
Each coordinator has a set of references to the participants. Each participant records a reference to the coordinator.
client runs transaction

Distributed One Phase Commit Protocol
• This commit protocol is inadequate because when the client requests a commit, it does not allow a server to
make a unilateral decision to abort a transaction, thus violating the Durability property of ACID. E.g.
deadlock avoidance may force a transaction to abort at a server when locking is used. So any server may
fail or abort and client is not aware.
Distributed Two Phase Commit Protocol
Phase 1 (voting phase):

1. The coordinator sends a canCommit? request to each of the participants in the transaction.
2. When a participant receives a canCommit? request it replies with its vote (Yes or No) to the coordinator. Before
voting Yes, it prepares to commit by saving objects in permanent storage. If the vote is No the participant aborts
immediately.
Phase 2 (completion according to outcome of vote):

3. The coordinator collects the votes (including its own).
(a) If there are no failures and all the votes are Yes the coordinator decides to commit the transaction and sends
a doCommit request to each of the participants.
(b) Otherwise the coordinator decides to abort the transaction and sends doAbort requests to all participants that
voted Yes.
4. Participants that voted Yes are waiting for a doCommit or doAbort request from the coordinator. When a participant
receives one of these messages it acts accordingly and in the case of commit, makes a haveCommitted call as
confirmation to the coordinator.
Operations of Two Phase Commit Protocol
canCommit?(trans)-> Yes / No
Call from coordinator to participant to ask whether it can commit a transaction. Participant replies with its vote.
doCommit(trans)
Call from coordinator to participant to tell participant to commit its part of a transaction.
doAbort(trans)
Call from coordinator to participant to tell participant to abort its part of a transaction.
haveCommitted(trans, participant)
Call from participant to coordinator to confirm that it has committed the transaction.
getDecision(trans) -> Yes / No

Call from participant to coordinator to ask for the decision on a transaction after it has voted Yes but has still
had no reply after some delay. Used to recover from server crash or delayed messages
If participat crashes after voted to commit, it can ask
co-ordinator about results of the vote
Timeouts are used when messages are expected
Introduces new state in transaction prepare to commit

also
• Consider when a participant has voted Yes and is waiting for the coordinator to report on the outcome of
the vote by telling it to commit or abort.
• Such a participant is uncertain and cannot proceed any further. The objects used by its transaction cannot
be released for use by other transactions.
• Participant makes a getDecision request to the coordinator to determine the outcome. If the coordinator has
failed, the participant will not get the decision until the coordinator is replaced resulting in extensive delay
for participant in uncertain state.
• Timeout are used since exchange of information can fail when one of the servers crashes, or when
messages are lost So process will not block forever.
Performance of Two Phase Commit Protocol
• Provided that all servers and communication channels do not fail, with N participants
• N number of canCommit? Messages and replies
• Followed by N doCommit messages
• The cost in messages is proportional to 3N
• The cost in time is three rounds of message.
• The cost of haveCommitted messages are not counted, which can function correctly without them- their
role is to enable server to delete stale coordinator information
Failure of Coordinator
• When a participant has voted Yes and is waiting for the coordinator to report on the outcome of the vote,
such participant is in uncertain stage. If the coordinator has failed, the participant will not be able to get the
decision until the coordinator is replaced, which can result in extensive delays for participants in the
uncertain state.
• One alternative strategy is allow the participants to obtain a decision from other participants instead of
contacting coordinator. However, if all participants are in the uncertain state, they will not get a decision.
Distributed Transaction
Topics in Distributed Transactions
 In previous chapter, we discussed transactions accessed objects at a single server. In the

general case, a transaction will access objects located in different computers. Distributed
transaction accesses objects managed by multiple servers.
 The atomicity property requires that either all of the servers involved in the same
transaction commit the transaction or all of them abort. Agreement among servers are
necessary.
 Transaction recovery is to ensure that all objects are recoverable. The values of the
objects reflect all changes made by committed transactions and none of those made by
aborted ones.
Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn.4
© Pearson Education 2005
Figure 14.1
Distributed transactions
(a) Flat transaction (b) Nested transactions

M
X
T11
X
Client T1 N
T T
Y 12
T
T
T
21
T2
Client
Y
P
Z
T
22
Flat transaction send out requests to different servers and each request is
completed before client goes to the next one. Nested transaction allows sub-
transactions at the same level to execute concurrently.
Figure 14.2
Nested banking transaction
X
Client T A a.withdraw(10)
1
T
T = openTransaction Y
openSubTransaction T B b.withdraw(20)
2
a.withdraw(10);
openSubTransaction
b.withdraw(20); Z
openSubTransaction
c.deposit(10); T
3 C c.deposit(10)
openSubTransaction
d.deposit(20); T D d.deposit(20)
4
closeTransaction
Instructor’s
Instructor’s
GuideGuide
for Coulouris,
for Coulouris,
Dollimore
Dollimore
and Kindberg
and Kindberg
Distributed
Distributed
Systems:
Systems:
Concepts
Concepts
and Design
and Design
Edn.4Edn.4
© Pearson
© Pearson
Education
Education
20052005
Coordinator of a distributed transaction
 Servers for a distributed transaction need to coordinate their

actions.
 A client starts a transaction by sending an openTransaction
request to a coordinator. The coordinator returns the TID to
the client. The TID must be unique (serverIP and number
unique to that server)
 Coordinator is responsible for committing or aborting it.
Each other server in a transaction is a participant.
Participants are responsible for cooperating with the
coordinator in carrying out the commit protocol, and keep
track of all recoverable objects managed by it.
 Each coordinator has a set of references to the participants.
Each participant records a reference to the coordinator.
Figure 14.3
A distributed banking transaction
coordinator
openTransaction join participant

closeTransaction
A a.withdraw(4);
.
join
BranchX
T
participant
b.withdraw(T, 3);
Client B b.withdraw(3);
T = openTransaction
join BranchY
a.withdraw(4);
c.deposit(4); participant
b.withdraw(3);
d.deposit(3); C c.deposit(4);
closeTransaction
D d.deposit(3);
Note: client invoke an operation b.withdraw(),
B will inform participant at BranchY to join coordinator. BranchZ
the coordinator is in one of the servers, e.g. BranchX

Instructor’s
Instructor’s
GuideGuide
for Coulouris,
for Coulouris,
Dollimore
Dollimore
and Kindberg
and Kindberg
Distributed
Distributed
Systems:
Systems:
Concepts
Concepts
and Design
and Design
Edn.4Edn.4
© Pearson
© Pearson
Education
Education
20052005
One-phase atomic commit protocol
 A transaction comes to an end when the client requests that a transaction be

committed or aborted.
 Simple way is: coordinator to communicate the commit or abort request to all
of the participants in the transaction and to keep on repeating the request
until all of them have acknowledged that they had carried it out.
 Inadequate because when the client requests a commit, it does not allow a
server to make a unilateral decision to abort a transaction. E.g. deadlock
avoidance may force a transaction to abort at a server when locking is used.
So any server may fail or abort and client is not aware.
Two-phase commit protocol
 Allow any participant to abort its part of a transaction. Due to atomicity, the
whole transaction must also be aborted.
 In the first phase, each participant votes for the transaction to be committed
or aborted. Once voted to commit, not allowed to abort it. So before votes to
commit, it must ensure that it will eventually be able to carry out its part,
even if it fails and is replaced.
 A participant is said to be in a prepared state if it will eventually be able to
commit it. So each participant needs to save the altered objects in the
permanent storage device together with its status-prepared.
In the second phase, every participant in the transaction carries

out the joint decision. If any one participant votes to abort, the
decision must be to abort. If all the participants vote to commit,
then the decision is to commit the transaction.
The problem is to ensure that all of the participants vote and that
they all reach the same decision. It is an example of consensus.
It is simple if no error occurs. However, it should work when
servers fail, message lost or servers are temporarily unable to
communicate with one another.
If the client requests abort, or if the transaction is aborted by one

of the participants, the coordinator informs the participants
immediately.
It is when the client asks the coordinator to commit the
transaction that two-phase commit protocol comes into use.
In the first phase, the coordinator asks all the participants if they
are prepared to commit; and in the second, it tells them to commit
or abort the transaction.
Figure 14.4
Operations for two-phase commit protocol
canCommit?(trans)-> Yes / No
Call from coordinator to participant to ask whether it can commit a
transaction. Participant replies with its vote.
doCommit(trans)
Call from coordinator to participant to tell participant to commit its part of a
transaction.
doAbort(trans)
Call from coordinator to participant to tell participant to abort its part of a
transaction.
haveCommitted(trans, participant)
Call from participant to coordinator to confirm that it has committed the
transaction.
getDecision(trans) -> Yes / No
Call from participant to coordinator to ask for the decision on a transaction
after it has voted Yes but has still had no reply after some delay. Used to
recover from server crash or delayed messages.
Figure 14.5
The two-phase commit protocol
Phase 1 (voting phase):

1. The coordinator sends a canCommit? request to each of the participants in
the transaction.
2. When a participant receives a canCommit? request it replies with its vote
(Yes or No) to the coordinator. Before voting Yes, it prepares to commit by
saving objects in permanent storage. If the vote is No the participant aborts
immediately.
Phase 2 (completion according to outcome of vote):
3. The coordinator collects the votes (including its own).
(a) If there are no failures and all the votes are Yes the coordinator
decides to commit the transaction and sends a doCommit request
to each of the participants.
(b) Otherwise the coordinator decides to abort the transaction and
sends doAbort requests to all participants that voted Yes.
4. Participants that voted Yes are waiting for a doCommit or doAbort request
from the coordinator. When a participant receives one of these messages it
acts accordingly and in the case of commit, makes a haveCommitted call as
confirmation to the coordinator.
Figure 14.6
Communication in two-phase commit protocol
Coordinator Participant
step status step status

canCommit?
1 prepared to commit
(waiting for votes) Yes 2 prepared to commit
3 committed doCommit (uncertain)
haveCommitted 4 committed
done
two-phase commit protocol
 Consider when a participant has voted Yes and is waiting for the coordinator to report on the
outcome of the vote by telling it to commit or abort.
 Such a participant is uncertain and cannot proceed any further. The objects used by its
transaction cannot be released for use by other transactions.
 Participant makes a getDecision request to the coordinator to determine the outcome. If the
coordinator has failed, the participant will not get the decision until the coordinator is
replaced resulting in extensive delay for participant in uncertain state.
 Timeout are used since exchange of information can fail when one of the servers crashes,
or when messages are lost So process will not block forever.
Performance of two-phase commit protocol
Provided that all servers and communication channels do not fail,

with N participants
N number of canCommit? Messages and replies
Followed by N doCommit messages
The cost in messages is proportional to 3N
The cost in time is three rounds of message.
The cost of haveCommitted messages are not counted, which
can function correctly without them- their role is to enable server
to delete stale coordinator information.
Failure of Coordinator
When a participant has voted Yes and is waiting

for the coordinator to report on the outcome of the
vote, such participant is in uncertain stage. If the
coordinator has failed, the participant will not be
able to get the decision until the coordinator is
replaced, which can result in extensive delays for
participants in the uncertain state.
One alternative strategy is allow the participants
to obtain a decision from other participants
instead of contacting coordinator. However, if all
participants are in the uncertain state, they will not
get a decision. Instructor’s Guide for Coulouris, Dollimore and Kindberg Distributed Systems: Concepts and Design Edn.4

Mod 6

Uploaded by

Copyright:

Available Formats

Mod 6

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Mod 6

Uploaded by

Copyright:

Available Formats

Transaction Processing Concepts

• There are properties that all transactions should

– Consistency : transfer the database from one consistent state

– Isolation : the execution of the transaction should be

– Durability : committed transactions must persist in the

– Irrecoverable Schedule: When T2 is reading the

• Dirty read problem/Read uncommitted

• Unrepeatable Read Problem (RW)

• Lost update problem (WW)

• A schedule is called conflict serializable if it can

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

 Have the same properties as their parents may

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 4

 A number of concurrency control techniques are applied

 Another set of protocol use timestamp.

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Transaction ID Data item id lock mode Ptr to next data item

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 6

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 7

 T1:LOCK(A)  This example is

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 11

 Consider the partial schedule

 Neither T3 nor T4 can make progress — executing lock-S(B)

Locking Protocol: to ensure the Serializability

2. Non-two-phase locking (skip)

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 14

 (a) Locking (Growing)

 (b) Unlocking (Shrinking).

 Locking (Growing) Phase:

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 15

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 16

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 17

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 18

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 19

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 20

 A monotonically increasing variable (integer)

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 22

 1. Transaction T issues a write_item(X) operation:

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 24

 1. Transaction T issues a write_item(X) operation:

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 25

 If read_TS(X) > TS(T) then abort and roll-back T

Copyright © 2007 Ramez Elmasri and Shamkant B. Navathe Slide 18- 26

• Might not be free from irrecoverability.

Servers for a distributed transaction need to coordinate their actions.

client runs transaction

Phase 1 (voting phase):

Phase 2 (completion according to outcome of vote):

getDecision(trans) -> Yes / No

Timeouts are used when messages are expected

Introduces new state in transaction prepare to commit

 In previous chapter, we discussed transactions accessed objects at a single server. In the

(a) Flat transaction (b) Nested transactions

 Servers for a distributed transaction need to coordinate their

openTransaction join participant

the coordinator is in one of the servers, e.g. BranchX

 A transaction comes to an end when the client requests that a transaction be