Majority Based Protocol for Concurrency Control / Variants of Distributed Lock Manager based Concurrency Control mechanism
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.
Example:
Let us assume that Q is replicated
in 6 sites. Then, we need to lock Q in 4 sites (half+one = 6/2 + 1 = 4). When transaction
T1 sends the lock request message to those 4 sites, the lock-managers of those
sites have to grant the locks based on the usual lock procedure.
How does Majority Based protocol work?
Implementation:
Figure 1 show the implementation of
Majority Based protocol.
In the figure,
- Q, R, and S are the different data items.
- Q is replicated in sites S1, S2, S3 and S6.
- R is replicated in sites S1, S2, S3, and S4.
- S is replicated at sites S1, S2, S4, S5, and S6.
 |
| Figure 1 - Majority Based Protocol Implementation |
Let us assume that Transaction T1
needs data item Q to be locked (either read or write mode).
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 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.
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:
- 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. (To handle this deadlock, we may need to impose an order in which the locks can be requested)
Points
to note:
-Transaction
can execute only after successful acquisition of locks on majority of the
replicas.
-Needs
to send more messages, 2(n/2+1) lock messages and (n/2+1) unlock messages, when
compared to Primary Copy protocol (2n+1 messages).
-Local
lock-managers are responsible for granting or denying the locks on requested
items.
-Not
suitable for applications where read operation is frequent.
-When writing the data item, a transaction
performs writes on all replicas.
-When handling with unreplicated data, both
requests can be handled by requesting the site at which the data item available
Please Follow
Traffic Rules
|
***********