CONCURRENCY CONTROL IN

DISTRIBUTED DATABASES

PREPARED BY
SAVITHRI S
What is meant by Concurrency control in distributed
databases?
• Concurrency : A situation in which two or more persons access same record simultaneously is called
concurrency. Various locking protocols are used for handling concurrent transactions in centralized
database systems.

1.Single Lock Manager Approach

2. Distributed Lock Manager Approach

Primary copy protocol

Majority Protocol
Biased Protocol
Quorum Consensus protocol
Single Lock Manager –
Concurrency Control in Distributed Database
• In this approach, the distributed database system which consists of several sites,
maintains a single lock manager at a chosen site .

Step1 - Let us assume that the Transaction T1 is initiated

at Site S5
Step 2 - The initiator site S5’s Transaction manager sends
the lock request to lock data item D to the lock-manager
site S3.
Step 3 - If the requested item is not locked by any other
transactions, the lock-manager site responds with lock
grant message to the initiator site S5.
Step 4 - As the next step, the initiator site S5 can use the
data item D from any of the sites S1, S2, and S6 for
completing the Transaction T1.
Step 5 - After successful completion of the Transaction
T1, the Transaction manager of S5 releases the lock by
sending the unlock request to the lock-manager site S3.
Advantages and Disadvantages
• Advantages:
• Locking can be handled easily.
• Deadlocks can be handled easily.
• Disadvantages:
• The lock-manager site becomes the bottleneck as it is the only site to
handle all the lock requests generated at all the sites in the system.
• Highly vulnerable to single point-of-failure. If the lock-manager site
failed, then we lose the concurrency control.
 Distributed Lock Manager - Concurrency Control in
Distributed Database
• Primary Copy Protocol - Distributed Lock Manager Approach
• Assume that we have the data item Q which is replicated in several sites and we choose one of the replicas of data item Q as
the Primary Copy (only one replica). The site which stores the Primary Copy is designated as the Primary Site. Any lock
requests generated for data item Q at any sites must be routed to the Primary site. Primary site’s lock-manager is responsible
for handling lock requests, though there are other sites with same data item and local lock-managers.

Step 1: Transaction T1 initiated at site S5 and requests lock on data item

Q. Even though the data item available locally at site S5, the lock-
manager of S5 cannot grant the lock. The reason is, in our example, Site
S3 is designated as primary site for Q. Hence, the request must be routed
to the site S3 by the Transaction manager of S5.
Step 2: S5 requests S3 for lock on Q. S5 sends lock request message to
S3.
Step 3: If the lock on Q can be granted, S3 grants lock and send a
message to S5.
On receiving lock grant, S5 executes the Transaction T1 (Executed on
the data item Q available locally. If no local copy, S3 has to execute the
transaction in other sites where Q is available).
Step 4: On successful completion of Transaction, S5 sends unlock
message to the Primary Site S3.
Advantages and Disadvantages of Primary
Copy Protocol
• Advantages:
• Handling of concurrency control on replicated data is like replicated data. Simple
implementation.
• Only 3 messages to handle lock and unlock requests (1 Lock request, 1 Granted,
and 1 Unlock message) for both read and write.
• Disadvantages:
• Possible single point-of-failure. If the Primary Site of a data item, say Q fails,
even though the other sites with the same copy of Q available, the data item Q is
inaccessible.
Majority Based Protocol - Distributed Lock Manager Concurrency Control

•Majority Based Protocol:

•Assume that we have the data item Q which is replicated in several sites and the Majority Based
protocol works as follows;
•A transaction which needs to lock data item Q has to request and lock data item Q in half+one sites in
which Q is replicated (i.e, majority of the sites in which Q is replicated).
•The lock-managers of all the sites in which Q is replicated are responsible for handling lock and
unlock requests locally individually.
•Irrespective of the lock types (read or write, i.e, Shared or Exclusive), we need to lock half+one sites.
How does Majority Based protocol work? Let us assume that Transaction T1 needs data item Q to be
In the figure, locked (either read or write mode).
Q, R, and S are the different data items.
Q is replicated in sites S1, S2, S3 and S6. Step 1: Transaction T1 initiated at site S5 and requests lock
R is replicated in sites S1, S2, S3, and S4. on data item Q. Q is available in S1, S2, S3 and the site
S is replicated at sites S1, S2, S4, S5, and S6. S6. According to the protocol, T1 has to lock Q in half+one
sites, i.e, in our example, we need to lock any 3 out of 4
sites. Assume that we have chosen sites S1, S2, and S3.
Step 2: S5 requests S1, S2 and S3 for lock on Q. The lock
request is represented in purple color.
Step 3: If the lock on Q can be granted, S1, S2, and S3
grant lock and send a message to S5.
On receiving lock grant, S5 executes the Transaction T1
(Executed on the data item Q which is taken from any one
of the locked sites). The lock grant is represented in green
color.
Step 4: On successful completion of Transaction, S5 sends
unlock message to all the sites S1, S2, and S3.
The unlock message is represented in blue color.
Note: If the transaction T1 writes the data item Q, then the
changes must be forward to all the sites where Q is
replicated. If the transaction read the data item Q, then no
problem.
Advantages and Disadvantages of Majority Based
Protocol
• Advantages:
Replicated data handled in decentralized manner. Hence, no single point-of-failure
problem.
• Disadvantages:
• Implementation is complex. We need to send (n/2 + 1) lock request messages, (n/2
+ 1) lock grant messages, and (n/2 + 1) unlock messages, irrespective of lock
requested (read or write).
• Both read and write involves same level of complexity.
• Deadlock would occur
Biased Protocol - Distributed Lock Manager
Concurrency Control
Protocol:
If a data item Q is replicated over n sites, then a read lock (Shared lock)
request message must be sent to any one of the sites in which Q is
replicated and, a write lock (Exclusive lock) request message must be sent
to all the sites in which Q is replicated. The lock-managers of all the sites in
which Q is replicated are responsible for handling lock and unlock requests
locally individually.
Step 1: Transaction T1 initiated at site S5 and requests lock on data item Q.
Q is available in S1, S2, S3 and the site S6. According to the protocol, T1 has
to lock Q in any one site in which Q is replicated, i.e, in our example, we
need to lock any 1 out of 4 sites where Q is replicated. Assume that we
have chosen the site S3.
Step 2: S5 requests S3 for shared lock on Q. The lock request is
represented in purple color.
Step 3: If the lock on Q can be granted, S3 can grant lock and send a
message to S5.
On receiving lock grant, S5 executes the Transaction T1 (Reading can be
done in the locked site, in our case, it is S3).
Step 4: On successful completion of Transaction, S5 sends unlock message
to the site S3.
Step 1: Transaction T1 initiated at site S5 and requests lock
on data item Q. According to the protocol, T1 has to lock Q
in all the sites in which Q is replicated, i.e, in our example,
we need to lock all the 4 sites where Q is replicated.
Step 2: S5 requests S1, S2, S3, and S6 for exclusive lock on
Q. The lock request is represented in purple color.
Step 3: If the lock on Q can be granted at every site, all the
sites will respond with grant lock message to S5. (If any
one or more sites cannot grant, T1 cannot be continued)
On receiving lock grant, S5 executes the Transaction T1
(When writing the data item, transaction performs writes
on all replicas).
Step 4: On successful completion of Transaction, S5 sends
unlock message to all sites S1, S2, S3, and S6.
Advantages and Disadvantages of Biased
Protocol
• Advantages:
Read operation can be handled faster compared to Majority based
protocol.If read operations are performed frequently in an application,
biased approach can be suggested.
• Disadvantages:
• Additional overhead on Write operation.
• Implementation is complex. We need to send (n/2 + 1) lock request
messages, (n/2 + 1) lock grant messages, and (n/2 + 1) unlock messages for
write operation.
• Deadlock would occur as discussed in the Majority Based protocol.