V SEM AI & ML Distributed Systems MODULE-5

Chapter-5 Distributed Transactions

5.1. Introduction
➢ A transaction is a series of object operations that must be done in an ACID-
compliant manner.
1. Atomicity: The transaction is completed entirely or not at all.
2. Consistency: It is a term that refers to the transition from one consistent
state to another.
3. Isolation : It is carried out separately from other transactions.
4. Durability : Once completed, it is long lasting.
➢ Transactions - Commands :
1. Begin: initiate a new transaction.
2. Commit: End a transaction and the changes made during the
transaction are saved. Also, it allows other transactions to see the
modifications you've made.
3. Abort: End a transaction and all changes made during the transaction
will be undone.
➢ Various roles are allocated to running a transaction successfully
1. Client: The transactions are issued by the clients.
2. Coordinator: The execution of the entire transaction is controlled by it
(handles Begin, commit & abort).
3. Server: Every component that accesses or modifies a resource is subject
to transaction control. The coordinator must be known by the
transactional server. The transactional server registers its participation
in a transaction with the coordinator.
5.2. Flat and nested distributed transactions
➢ A client transaction becomes distributed if it invokes operations in several
different servers.
➢ There are two different ways that distributed transactions can be
structured: as flat transactions and as nested transactions.
➢ A flat or nested transaction that accesses objects handled by different
servers is referred to as a distributed transaction.
➢ When a distributed transaction reaches its end, in order to maintain the
atomicity property of the transaction, it is mandatory that all of the servers
involved in the transaction either commit the transaction or abort it.
➢ To do this, one of the servers takes on the job of coordinator, which entails
ensuring that the same outcome is achieved across all servers.
➢ The method by which the coordinator accomplishes this is determined by
the protocol selected. The most widely used protocol is the 'two-phase
commit protocol.' This protocol enables the servers to communicate with
one another in order to come to a joint decision on whether to commit or
abort the complete transaction.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ Flat & Nested Distributed Transactions: If a client transaction calls

actions on multiple servers, it is said to be distributed. Distributed
transactions can be structured in two different ways:
1. Flat transactions
2. Nested transactions
➢ Flat transactions: A flat transaction has a single initiating point(Begin)
and a single end point(Commit or abort).
➢ They are usually very simple and are generally used for short activities
rather than larger ones.
➢ A client makes requests to multiple servers in a flat transaction.
➢ Transaction T, for example, is a flat transaction that performs operations
on objects in servers X, Y, and Z.
➢ Before moving on to the next request, a flat client transaction completes
the previous one. As a result, each transaction visits the server object in
order.
➢ A transaction can only wait for one object at a time when servers utilize
locking.

Fig 5.1: Flat Transaction

➢ Limitations of a flat Transaction :
1. All work is lost in the event of a crash.
2. Only one DBMS may be used at a time.
3. No partial rollback is possible.
➢ NESTED TRANSACTIONS : A transaction that includes other transactions
within its initiating point and a end point are known as nested
transactions. So the nesting of the transactions is done in a transaction.
➢ The nested transactions here are called sub-transactions.
➢ The top-level transaction in a nested transaction can open sub-
transactions, and each sub-transaction can open more sub-transactions
down to any depth of nesting.
➢ A client's transaction T opens up two sub-transactions, T1 and T2, which
access objects on servers X and Y, as shown in the diagram below.
T1.1, T1.2, T2.1, and T2.2, which access the objects on the servers M,N,
and P, are opened by the sub-transactions T1 and T2.

Fig 5.2: Nested Transactions

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ Concurrent Execution of the Sub-transactions is done which are at the

same level - in the nested transaction [Link], in the above
diagram, T1 and T2 invoke objects on different servers and hence they can
run in parallel and are therefore concurrent. T1.1, T1.2, T2.1, and T2.2
are four sub-transactions. These sub-transactions can also run in
parallel.
➢ Consider a distributed transaction (T) in which a customer transfers:
Rs.105 from account A to account C and Subsequently, Rs.205 from
account B to account D.
➢ It can be viewed of as:
Transaction T:
Start
Transfer Rs 105 from A to C:
Deduct Rs 105 from A (withdraw from A) & Add Rs 105 to C (deposit to C)
Transfer Rs 205 from B to D:
Deduct Rs 205 from B (withdraw from B & Add Rs 205 to D (deposit to D)
End
➢ Assuming: Account A is on server X, Account B is on server Y, and
Accounts C and D are on server Z.
➢ The transaction T involves four requests - 2 for deposits and 2 for
withdrawals. Now they can be treated as sub transactions (T1, T2, T3, T4)
of the transaction T. As shown in the figure below, transaction T is
designed as a set of four nested transactions: T1, T2, T3 and T4.
➢ Advantage: The performance is higher than a single transaction in which
four operations are invoked one after the other in sequence.

Fig 5.3: Nested Banking Transaction

➢ So, the Transaction T may be divided into sub-transactions as :
//Start the Transaction
T = open transaction
//T1
Opensubtransaction
[Link](105);
//T2
Opensubtransaction
[Link](205);
//T3
opensubtransaction
[Link](105);
//T4

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

Opensubtransaction
[Link](205)
//End Transaction
Close Transaction
5.2.1. The coordinator of a distributed transaction
➢ When the Distributed Transaction commits, the servers that are involved
in the transaction execution, for proper coordination, must be able to
communicate with one another .
➢ When a client initiates a transaction, an "openTransaction" request is sent
to any coordinator server. The contacted coordinator carries out the
"openTransaction" and returns the transaction identifier to the client.
➢ Distributed transaction identifiers must be unique within the distributed
system.
➢ A simple way is to generate a TID contains two parts - the 'server identifier''
(example : IP address) of the server that created it and a number unique to
the server.
➢ The coordinator who initiated the transaction becomes the distributed
transaction's coordinator and has the responsibility of either aborting it
or committing it.
➢ Every server that manages an object accessed by a transaction is a
participant in the transaction & provides an object we call the participant.
➢ The participants are responsible for working together with the coordinator
to complete the commit process.
➢ The coordinator every time, records the new participant in the participants
list.
➢ Each participant knows the coordinator & the coordinator knows all the
participants.
➢ This enables them to collect the information that will be needed at the time
of commit and hence work in coordination.

Fig 5.4: A Distributed Banking Transaction

➢ Figure 5.4 shows a client whose (flat) banking transaction involves

accounts A, B, C and D at servers BranchX, BranchY and BranchZ.
➢ The client’s transaction, T, transfers $4 from account A to account C and
then transfers $3 from account B to account D.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ The transaction described on the left is expanded to show that

openTransaction and closeTransaction are directed to the coordinator,
which would be situated in one of the servers involved in the transaction.
➢ Each server is shown with a participant, which joins the transaction by
invoking the join method in the coordinator.
➢ When the client invokes one of the methods in the transaction, for example
[Link](T, 3), the object receiving the invocation (B at BranchY, in this
case) informs its participant object that the object belongs to the
transaction T.
➢ If it has not already informed the coordinator, the participant object uses
the join operation to do so.
➢ By the time the client calls closeTransaction, the coordinator has
references to all of the participants.
➢ Note that it is possible for a participant to call abortTransaction in the
coordinator if for some reason it is unable to continue with the transaction.
5.3. Atomic commit protocols
➢ The atomicity property of transactions requires that when a distributed
transaction comes to an end, either all of its operations are carried out or
none of them.
➢ In the case of a distributed transaction, the client has requested operations
at more than one server.
➢ A transaction comes to an end when the client requests that it be
committed or aborted.
➢ A simple way to complete the transaction in an atomic manner is for the
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 have carried it out.
➢ This simple one-phase atomic commit protocol is inadequate, though,
because it does not allow a server to make a unilateral decision to abort a
transaction when the client requests a commit.
➢ Reasons that prevent a server from being able to commit its part of a
transaction generally relate to issues of concurrency control.
➢ The coordinator may not know if a server has crashed and been replaced
during the progress of a distributed transaction – such a server will need
to abort the transaction.
➢ The two-phase commit protocol is designed to allow any participant to abort
its part of a transaction.
➢ Due to the requirement for atomicity, if one part of a transaction is aborted,
then the whole transaction must be aborted.
➢ In the first phase of the protocol, each participant votes for the transaction
to be committed or aborted.
➢ Once a participant has voted to commit a transaction, it is not allowed to
abort it.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ Therefore, before a participant votes to commit a transaction, it must

ensure that it will eventually be able to carry out its part of the commit
protocol, even if it fails and is replaced in the interim.
➢ A participant in a transaction is said to be in a prepared state for a
transaction if it will eventually be able to commit it.
➢ To make sure of this, each participant saves in permanent storage all of
the objects that it has altered in the transaction, together with its status –
prepared.
➢ In the second phase of the protocol, every participant in the transaction
carries out the joint decision.
➢ If any one participant votes to abort, then the decision must be to abort
the transaction.
➢ 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.
➢ This is fairly simple if no errors occur, but the protocol must work correctly
even when some of the servers fail, messages are lost or servers are
temporarily unable to communicate with one another.
➢ Failure model for the commit protocols: Commit protocols are designed
to work in an asynchronous system in which servers may crash and
messages may be lost.
➢ It is assumed that an underlying request-reply protocol removes corrupt
and duplicated messages.
➢ There are no Byzantine faults servers either crash or obey the messages
they are sent.
➢ The two-phase commit protocol is an example of a protocol for reaching a
consensus.
➢ This is because crash failures of processes are masked by replacing a
crashed process with a new process whose state is set from information
saved in permanent storage and information held by other processes.
5.3.1. The Two-Phase Commit Protocol
➢ During the progress of a transaction, there is no communication between
the coordinator and the participants apart from the participants informing
the coordinator when they join the transaction.
➢ A client’s request to commit (or abort) a transaction is directed to the
coordinator.
➢ If the client requests abortTransaction, or if the transaction is aborted by
one of the participants, the coordinator informs all participants
immediately.
➢ It is when the client asks the coordinator to commit the transaction that
the two-phase commit protocol comes into use.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ In the first phase of the two-phase commit protocol the coordinator asks
all the participants if they are prepared to commit; in the second, it tells
them to commit (or abort) the transaction.
➢ If a participant can commit its part of a transaction, it will agree as soon
as it has recorded the changes it has made (to the objects) and its status
in permanent storage and is therefore prepared to commit.
➢ The coordinator in a distributed transaction communicates with the
participants to carry out the two-phase commit protocol by means of the
operations.

Fig 5.5 Operations for two-phase commit protocol

➢ The methods canCommit, doCommit and doAbort are methods in the
interface of the participant.
➢ The methods haveCommitted and getDecision are in the coordinator
interface.
➢ The two-phase commit protocol consists of a voting phase and a
completion phase.

Fig 5.6 The two-phase commit protocol

➢ By the end of step 2, the coordinator and all the participants that voted
Yes are prepared to commit. By the end of step 3, the transaction is
effectively completed.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ At step 3a the coordinator and the participants are committed, so the

coordinator can report a decision to commit to the client.
➢ At 3b the coordinator reports a decision to abort to the client.
➢ At step 4 participants confirm that they have committed so that the
coordinator knows when the information it has recorded about the
transaction is no longer needed.
➢ This apparently straightforward protocol could fail due to one or more of
the servers crashing or due to a breakdown in communication between the
servers.
➢ To deal with the possibility of crashing, each server saves information
relating to the two-phase commit protocol in permanent storage.
➢ This information can be retrieved by a new process that is started to
replace a crashed server.
➢ The exchange of information between the coordinator and participants can
fail when one of the servers crashes, or when messages are lost.
➢ Timeouts are used to avoid processes blocking forever. When a timeout
occurs at a process, it must take an appropriate action.
➢ To allow for this the protocol includes a timeout action for each step at
which a process may block.
➢ Timeout actions in the two-phase commit protocol: There are various
stages in the protocol at which the coordinator or a participant cannot
progress its part of the protocol until it receives another request or reply
from one of the others.
➢ Consider first the situation where 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 the transaction (shown in below fig).

Fig 5.7. Communication in Two-phase commit protocol

➢ Such a participant is uncertain of the outcome and cannot proceed any
further until it gets the outcome of the vote from the coordinator.
➢ The participant cannot decide unilaterally what to do next, and meanwhile
the objects used by its transaction cannot be released for use by other
transactions.
➢ The participant can make a getDecision request to the coordinator to
determine the outcome of the transaction. When it gets the reply, it
continues the protocol at step 4 (in figure 5.6).
➢ 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.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ However, even with a cooperative protocol, if all the participants are in the
uncertain state, they will be unable to get a decision until the coordinator
or a participant with the necessary knowledge is available.
➢ Another point at which a participant may be delayed is when it has carried
out all its client requests in the transaction but has not yet received a
canCommit? call from the coordinator.
➢ As the client sends the closeTransaction to the coordinator, a participant
can only detect such a situation if it notices that it has not had a request
in a particular transaction for a long time – for example, by the time a
timeout period on a lock expires.
➢ As no decision has been made at this stage, the participant can decide to
abort unilaterally.
➢ The coordinator may be delayed when it is waiting for votes from the
participants.
➢ As it has not yet decided the fate of the transaction it may decide to abort
the transaction after some period of time.
➢ It must then announce doAbort to the participants who have already sent
their votes.
➢ Performance of the two-phase commit protocol: In the worst case, there
may be arbitrarily many server and communication failures during the
two-phase commit protocol.
➢ However, the protocol is designed to tolerate a succession of failures (server
crashes or lost messages) and is guaranteed to complete eventually,
although it is not possible to specify a time limit within which it will be
completed.
➢ The two-phase commit protocol can cause considerable delays to
participants in the uncertain state.
➢ These delays occur when the coordinator has failed and cannot reply to
getDecision requests from participants.
➢ Even if a cooperative protocol allows participants to make getDecision
requests to other participants, delays will occur if all the active participants
are uncertain.
5.3.2. Two-phase commit protocol for nested transactions
➢ The outermost transaction in a set of nested transactions is called the top-
level transaction. Transactions other than the top-level transaction are
called subtransactions.
➢ In Fig 5.2, T is the top-level transaction and T1, T2, T11, T12, T21 and T22
are subtransactions. T1 and T2 are child transactions of T, which is
referred to as their parent.
➢ Similarly, T11 and T12 are child transactions of T1, and T21 and T22 are
child transactions of T2. Each subtransaction starts after its parent and
finishes before it.
➢ When a subtransaction completes, it makes an independent decision
either to commit provisionally or to abort.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ A provisional commit is different from being prepared to commit: nothing

is backed up in permanent storage.
➢ If the server crashes subsequently, its replacement will not be able to
commit.
➢ After all subtransactions have completed, the provisionally committed
ones participate in a two-phase commit protocol, in which servers of
provisionally committed subtransactions express their intention to commit
and those with an aborted ancestor will abort.
➢ A coordinator for a subtransaction will provide an operation to open a
subtransaction, together with an operation enabling that coordinator to
enquire whether its parent has yet committed or aborted (as shown in
below figure).

Fig 5.8: Operations in coordinator for nested transactions

➢ A client starts a set of nested transactions by opening a top-level
transaction with an openTransaction operation, which returns a
transaction identifier for the top-level transaction.
➢ The client starts a subtransaction by invoking the openSubTransaction
operation, whose argument specifies its parent transaction.
➢ The new subtransaction automatically joins the parent transaction, and a
transaction identifier for a subtransaction is returned.
➢ An identifier for a subtransaction must be an extension of its parent’s TID,
constructed in such a way that the identifier of the parent or top-level
transaction of a subtransaction can be determined from its own
transaction identifier.
➢ The client makes a set of nested transactions come to completion by
invoking closeTransaction or abortTransaction on the coordinator of the
top-level transaction.
➢ Meanwhile, each of the nested transactions carries out its operations.
When they are finished, the server managing a subtransaction records
information as to whether the subtransaction committed provisionally or
aborted.
➢ A top-level transaction can commit even if one of its child subtransactions
has aborted.
➢ In such cases, the parent transaction will be programmed to take different
actions according to whether a subtransaction has committed or aborted.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

Fig 5.9 Transaction T decides whether to commit (based on fig 5.2)

➢ Dependency on Parent Transactions: Even if a subtransaction
provisionally commits (e.g., T12), its final outcome depends on whether its
parent transaction (T1) and ultimately the top-level transaction (T)
commit.
• If the parent aborts, all its provisionally committed subtransactions must
also abort.
➢ Effect of Parent Abortion: T21 and T22 both provisionally committed, but
since their parent T2 aborted, both must abort as well, regardless of their
individual success.
➢ Top-Level Transaction Commit
• Suppose T decides to commit even though T2 aborted.
• In this case, T1’s results can still be made permanent, but T2 and all its
subtransactions are discarded.
➢ Selective Commit Within a Parent
• If T1 decides to commit despite T11 aborting, then only T12’s
provisional results are made permanent, while T11 effects are discarded.
• This shows that some subtransactions under a parent can commit
while others abort, depending on the parent’s final decision.
➢ When a top-level transaction completes, its coordinator carries out a two-
phase commit protocol.
➢ The only reason for a participant subtransaction being unable to complete
is if it has crashed since it completed its provisional commit.
➢ Recall that when each subtransaction was created, it joined its parent
transaction.
➢ Therefore, the coordinator of each parent transaction has a list of its child
subtransactions.
➢ When a nested transaction provisionally commits, it reports its status and
the status of its descendants to its parent.
➢ When a nested transaction aborts, it just reports abort to its parent without
giving any information about its descendants.
➢ Eventually, the top-level transaction receives a list of all the
subtransactions in the tree, together with the status of each.
➢ Descendants of aborted subtransactions are omitted from this list.
➢ If participants vote to commit, then they must prepare their transactions
by saving the state of the objects in permanent storage.
➢ This state is recorded as belonging to the top-level transaction of which it
will form a part.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ The two-phase commit protocol may be performed in either a hierarchic

manner or a flat manner.
➢ The second phase of the two-phase commit protocol is that coordinator
collects the votes and then informs the participants as to the outcome.
➢ When it is complete, coordinator and participants will have committed or
aborted their transactions.
➢ Hierarchic two-phase commit protocol: In this approach, the two-phase
commit protocol becomes a multi-level nested protocol.
➢ The coordinator of the top-level transaction communicates with the
coordinators of the subtransactions for which it is the immediate parent.
➢ It sends canCommit? messages to each of the latter, which in turn pass
them on to the coordinators of their child transactions (and so on down
the tree).
➢ Each participant collects the replies from its descendants before replying
to its parent.
➢ In our example, T sends canCommit? messages to the coordinator of T1
and then T1 sends canCommit? messages to T12 asking about descendants
of T1.
➢ The protocol does not include the coordinators of transactions such as T2,
which has aborted.

Fig 5.10 canCommit? for hierarchic two-phase commit protocol

➢ Above fig shows the arguments required for canCommit?. The first
argument is the TID of the toplevel transaction, for use when preparing the
data.
➢ The second argument is the TID of the participant making the canCommit?
call.
➢ The participant receiving the call looks in its transaction list for any
provisionally committed transaction or subtransaction matching the TID
in the second argument.
➢ If a participant finds any subtransactions that match the second
argument, it prepares the objects and replies with a Yes vote.
➢ If it fails to find any, then it must have crashed since it performed the
subtransaction and it replies with a No vote.
➢ Flat two-phase commit protocol: In this approach, the coordinator of the
top-level transaction sends canCommit? messages to the coordinators of
all of the subtransactions in the provisional commit list.
➢ During the commit protocol, the participants refer to the transaction by its
top-level TID.
➢ Each participant looks in its transaction list for any transaction or
subtransaction matching that TID.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ Unfortunately, this does not provide sufficient information to enable

correct actions by participants such as the coordinator at server N that
have a mix of provisionally committed and aborted subtransactions.
➢ If N’s coordinator is just asked to commit T it will end up by committing
both T12 and T21, because, according to its local information, both have
provisionally committed.
➢ This is wrong in the case of T21, because its parent, T2, has aborted.
➢ To allow for such cases, the canCommit? Operation for the flat commit
protocol has a second argument that provides a list of aborted
subtransactions (as shown in below fig).

Fig 5.11 canCommit? for flat two-phase commit protocol

➢ When a participant receives a canCommit? request, it does the following:
1. If the participant has any provisionally committed transactions that are
descendants of the top-level transaction, trans, it:
➔ checks that they do not have aborted ancestors in the abortList, then
prepares to commit (by recording the transaction and its objects in
permanent storage);
➔ aborts those with aborted ancestors;
➔ sends a Yes vote to the coordinator.
2. If the participant does not have a provisionally committed descendent of
the toplevel transaction, it must have failed since it performed the
subtransaction and it sends a No vote to the coordinator.
➢ A comparison of the two approaches: The hierarchic protocol has the
advantage that at each stage, the participant only need look for
subtransactions of its immediate parent, whereas the flat protocol needs
to have the abort list in order to eliminate transactions whose parents have
aborted.

5.4. Concurrency control in distributed transactions

➢ Each server manages a set of objects and is responsible for ensuring that
they remain consistent when accessed by concurrent transactions.
➢ Therefore, each server is responsible for applying concurrency control to
its own objects.
➢ The members of a collection of servers of distributed transactions are
jointly responsible for ensuring that they are performed in a serially
equivalent manner.
5.4.1. Locking
➢ In a distributed transaction, the locks on an object are held locally (in the
same server).
➢ The local lock manager can decide whether to grant a lock or make the
requesting transaction wait.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ However, it cannot release any locks until it knows that the transaction
has been committed or aborted at all the servers involved in the
transaction.
➢ When locking is used for concurrency control, the objects remain locked
and are unavailable for other transactions during the atomic commit
protocol, although an aborted transaction releases its locks after phase 1
of the protocol.
➢ As lock managers in different servers set their locks independently of one
another, it is possible that different servers may impose different orderings
on transactions.
➢ Consider the following interleaving of transactions T and U at servers X
and Y:

➢ The transaction T locks object A at server X, and then transaction U locks

object B at server Y. After that, T tries to access B at server Y and waits for
U’s lock.
➢ Similarly, transaction U tries to access A at server X and has to wait for T’s
lock.
➢ Therefore, we have T before U in one server and U before T in the other.
➢ These different orderings can lead to cyclic dependencies between
transactions, giving rise to a distributed deadlock situation.
➢ When a deadlock is detected, a transaction is aborted to resolve the
deadlock.
➢ In this case, the coordinator will be informed and will abort the transaction
at the participants involved in the transaction.
5.4.2. Timestamp ordering concurrency control
➢ In a single server transaction, the coordinator issues a unique timestamp
to each transaction when it starts.
➢ In distributed transactions, we require that each coordinator issue globally
unique timestamps.
➢ A globally unique transaction timestamp is issued to the client by the first
coordinator accessed by a transaction.
➢ The transaction timestamp is passed to the coordinator at each server
whose objects perform an operation in the transaction.
➢ The servers of distributed transactions are jointly responsible for ensuring
that they are performed in a serially equivalent manner.
➢ To achieve the same ordering at all the servers, the coordinators must
agree as to the ordering of their timestamps.
➢ A timestamp consists of a <local timestamp, server-id> pair.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ The agreed ordering of pairs of timestamps is based on a comparison in

which the server-id part is less significant.
➢ The same ordering of transactions can be achieved at all the servers even
if their local clocks are not synchronized.
➢ The ordering of transactions generally corresponds to the order in which
they are started in real time.
➢ Timestamps can be kept roughly synchronized by the use of synchronized
local physical clocks.
➢ When timestamp ordering is used for concurrency control, conflicts are
resolved as each operation is performed using the rules.
➢ If the resolution of a conflict requires a transaction to be aborted, the
coordinator will be informed and it will abort the transaction at all the
participants.
➢ Therefore any transaction that reaches the client request to commit should
always be able to commit, and participants in the two-phase commit
protocol will normally agree to commit.
➢ The only situation in which a participant will not agree to commit is if it
has crashed during the transaction.

5.4.3. Optimistic concurrency control

➢ In optimistic concurrency control, each transaction is validated before it is
allowed to commit.
➢ Transaction numbers are assigned at the start of validation and
transactions are serialized according to the order of the transaction
numbers.
➢ A distributed transaction is validated by a collection of independent
servers, each of which validates transactions that access its own objects.
➢ This validation takes place during the first phase of the two-phase commit
protocol.
➢ Consider the following interleaving of transactions T and U, which access
objects A and B at servers X and Y, respectively:

➢ The transactions access the objects in the order T before U at server X and
in the order U before T at server Y.
➢ Now suppose that T and U start validation at about the same time, but
server X validates T first and server Y validates U first.
➢ A simplification of the validation protocol that makes a rule that only one
transaction may perform validation and update phases at a time.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML
V SEM AI & ML Distributed Systems MODULE-5

➢ Therefore each server will be unable to validate the other transaction until
the first one has completed.
➢ In a distributed transaction, the two-phase commit protocol may take
some time to complete, and other transactions will be prevented from
entering validation until a decision on the current transaction has been
obtained.
➢ In distributed optimistic transactions, each server applies a parallel
validation protocol.
➢ This is an extension of either backward or forward validation to allow
multiple transactions to be in the validation phase at the same time.
➢ If parallel validation is used, transactions will not suffer from commitment
deadlock.
➢ However, if servers simply perform independent validations, it is possible
that different servers in a distributed transaction may serialize the same
set of transactions in different orders.
➢ The servers of distributed transactions must prevent this happening. One
approach is that after a local validation by each server, a global validation
is carried out.
➢ Another approach is that all of the servers of a particular transaction use
the same globally unique transaction number at the start of the validation.
➢ The coordinator of the two-phase commit protocol is responsible for
generating the globally unique transaction number and passes it to the
participants in the canCommit? messages.
➢ As different servers may coordinate different transactions, the servers
must (as in the distributed timestamp ordering protocol) have an agreed
order for the transaction numbers they generate.
➢ MVGV (multi-version generalized validation) is a form of parallel validation
that ensures that transaction numbers reflect serial order, but it requires
that in some cases, other transactions are unable to read their effects
immediately after they have committed.
➢ It also allows the transaction number to be changed so as to permit some
transactions to validate that otherwise would have failed.
➢ At the end of the read phase, the coordinator proposes a value for the global
transaction number and each participant attempts to validate its local
transactions using that number.
➢ However, if the proposed global transaction number is too small, some
participants may not be able to validate their transactions, and they will
have to negotiate with the coordinator for an increased number.
➢ If no suitable number can be found, then those participants will have to
abort their transactions.
➢ Eventually, if all of the participants can validate their transactions, the
coordinator will have received proposals for transaction numbers from
each of them.
➢ If common numbers can be found then the transaction will be committed.

Compiled by: Kavyashree G J

Assistant Professor Dept. of AI&ML