Friday, April 4, 2014

Majority Based Protocol - Distributed Lock Manager Concurrency Control

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.


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?


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.
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.


  • Replicated data handled in decentralized manner. Hence, no single point-of-failure problem.


  • 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

Featured Content

Multiple choice questions in Natural Language Processing Home

MCQ in Natural Language Processing, Quiz questions with answers in NLP, Top interview questions in NLP with answers Multiple Choice Que...

All time most popular contents

data recovery