diff --git a/asterix-common/src/main/java/edu/uci/ics/asterix/common/transactions/ILockManager.java b/asterix-common/src/main/java/edu/uci/ics/asterix/common/transactions/ILockManager.java
index a752afa..dbe7e82 100644
--- a/asterix-common/src/main/java/edu/uci/ics/asterix/common/transactions/ILockManager.java
+++ b/asterix-common/src/main/java/edu/uci/ics/asterix/common/transactions/ILockManager.java
@@ -66,7 +66,7 @@
      *             TODO
      * @return 
      */
-    public void unlock(DatasetId datasetId, int entityHashValue, ITransactionContext txnContext)
+    public void unlock(DatasetId datasetId, int entityHashValue, byte lockMode, ITransactionContext txnContext)
             throws ACIDException;
 
     /**
diff --git a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataManager.java b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataManager.java
index 46159ba..a1afd89 100644
--- a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataManager.java
+++ b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataManager.java
@@ -128,8 +128,8 @@
     }
 
     @Override
-    public void unlock(MetadataTransactionContext ctx) throws RemoteException, ACIDException {
-        metadataNode.unlock(ctx.getJobId());
+    public void unlock(MetadataTransactionContext ctx, byte lockMode) throws RemoteException, ACIDException {
+        metadataNode.unlock(ctx.getJobId(), lockMode);
     }
 
     @Override
diff --git a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataNode.java b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataNode.java
index a3f736e..577ac50 100644
--- a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataNode.java
+++ b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/MetadataNode.java
@@ -140,9 +140,9 @@
     }
 
     @Override
-    public void unlock(JobId jobId) throws ACIDException, RemoteException {
+    public void unlock(JobId jobId, byte lockMode) throws ACIDException, RemoteException {
         ITransactionContext txnCtx = transactionSubsystem.getTransactionManager().getTransactionContext(jobId, false);
-        transactionSubsystem.getLockManager().unlock(METADATA_DATASET_ID, -1, txnCtx);
+        transactionSubsystem.getLockManager().unlock(METADATA_DATASET_ID, -1, lockMode, txnCtx);
     }
 
     @Override
diff --git a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataManager.java b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataManager.java
index 392c8a1..5fbd06d 100644
--- a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataManager.java
+++ b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataManager.java
@@ -105,7 +105,7 @@
      * @throws ACIDException
      * @throws RemoteException
      */
-    public void unlock(MetadataTransactionContext ctx) throws ACIDException, RemoteException;
+    public void unlock(MetadataTransactionContext ctx, byte lockMode) throws ACIDException, RemoteException;
 
     /**
      * Inserts a new dataverse into the metadata.
diff --git a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataNode.java b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataNode.java
index f27268f..fce3f25 100644
--- a/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataNode.java
+++ b/asterix-metadata/src/main/java/edu/uci/ics/asterix/metadata/api/IMetadataNode.java
@@ -84,7 +84,7 @@
      * @throws ACIDException
      * @throws RemoteException
      */
-    public void unlock(JobId jobId) throws ACIDException, RemoteException;
+    public void unlock(JobId jobId, byte lockMode) throws ACIDException, RemoteException;
 
     /**
      * Inserts a new dataverse into the metadata, acquiring local locks on
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexInstantSearchOperationCallback.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexInstantSearchOperationCallback.java
index dcc4d40..e16e106 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexInstantSearchOperationCallback.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexInstantSearchOperationCallback.java
@@ -64,7 +64,7 @@
     public void complete(ITupleReference tuple) throws HyracksDataException {
         int pkHash = computePrimaryKeyHashValue(tuple, primaryKeyFields);
         try {
-            lockManager.unlock(datasetId, pkHash, txnCtx);
+            lockManager.unlock(datasetId, pkHash, LockMode.S, txnCtx);
         } catch (ACIDException e) {
             throw new HyracksDataException(e);
         }
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexSearchOperationCallback.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexSearchOperationCallback.java
index efe1daa..9957edf 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexSearchOperationCallback.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/opcallbacks/PrimaryIndexSearchOperationCallback.java
@@ -58,7 +58,7 @@
     public void cancel(ITupleReference tuple) throws HyracksDataException {
         int pkHash = computePrimaryKeyHashValue(tuple, primaryKeyFields);
         try {
-            lockManager.unlock(datasetId, pkHash, txnCtx);
+            lockManager.unlock(datasetId, pkHash, LockMode.S, txnCtx);
         } catch (ACIDException e) {
             throw new HyracksDataException(e);
         }
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/ConcurrentLockManager.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/ConcurrentLockManager.java
index f748255..717f6c4 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/ConcurrentLockManager.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/ConcurrentLockManager.java
@@ -198,7 +198,7 @@
         log("instantLock", datasetId.getId(), entityHashValue, lockMode, txnContext);
 
         lock(datasetId, entityHashValue, lockMode, txnContext);
-        unlock(datasetId, entityHashValue, txnContext);
+        unlock(datasetId, entityHashValue, lockMode, txnContext);
     }
 
     @Override
@@ -272,15 +272,15 @@
         log("instantTryLock", datasetId.getId(), entityHashValue, lockMode, txnContext);
         
         if (tryLock(datasetId, entityHashValue, lockMode, txnContext)) {
-            unlock(datasetId, entityHashValue, txnContext);
+            unlock(datasetId, entityHashValue, lockMode, txnContext);
             return true;
         }
         return false;
     }
 
     @Override
-    public void unlock(DatasetId datasetId, int entityHashValue, ITransactionContext txnContext) throws ACIDException {
-        log("unlock", datasetId.getId(), entityHashValue, LockMode.NL, txnContext);
+    public void unlock(DatasetId datasetId, int entityHashValue, byte lockMode, ITransactionContext txnContext) throws ACIDException {
+        log("unlock", datasetId.getId(), entityHashValue, lockMode, txnContext);
 
         ResourceGroup group = table.get(datasetId, entityHashValue);
         group.getLatch();
@@ -297,7 +297,7 @@
             int jobId = txnContext.getJobId().getId();
             long jobSlot = findOrAllocJobSlot(jobId);
 
-            long holder = removeLastHolder(resource, jobSlot);
+            long holder = removeLastHolder(resource, jobSlot, lockMode);
 
             // deallocate request
             reqArenaMgr.deallocate(holder);
@@ -345,7 +345,7 @@
             long resource = reqArenaMgr.getResourceId(holder);
             int dsId = resArenaMgr.getDatasetId(resource);
             int pkHashVal = resArenaMgr.getPkHashVal(resource);
-            unlock(new DatasetId(dsId), pkHashVal, txnContext);
+            unlock(new DatasetId(dsId), pkHashVal, LockMode.NL, txnContext);
             holder = jobArenaMgr.getLastHolder(jobSlot);
         }
         jobArenaMgr.deallocate(jobSlot);
@@ -452,19 +452,19 @@
         }
     }
     
-    private long removeLastHolder(long resource, long jobSlot) {
+    private long removeLastHolder(long resource, long jobSlot, byte lockMode) {
         long holder = resArenaMgr.getLastHolder(resource);
         if (holder < 0) {
             throw new IllegalStateException("no holder for resource " + resource);
         }
         
         // remove from the list of holders for a resource
-        if (reqArenaMgr.getJobSlot(holder) == jobSlot) {
+        if (requestMatches(holder, jobSlot, lockMode)) {
             // if the head of the queue matches, we need to update the resource
             long next = reqArenaMgr.getNextRequest(holder);
             resArenaMgr.setLastHolder(resource, next);
         } else {
-            holder = removeRequestFromQueueForJob(holder, jobSlot);
+            holder = removeRequestFromQueueForJob(holder, jobSlot, lockMode);
         }
         
         synchronized (jobArenaMgr) {
@@ -475,6 +475,12 @@
         return holder;
     }
 
+    private boolean requestMatches(long holder, long jobSlot, byte lockMode) {
+        return jobSlot == reqArenaMgr.getJobSlot(holder) 
+                && (lockMode == LockMode.NL
+                || lockMode == reqArenaMgr.getLockMode(holder));
+    }
+
     private long removeRequestFromJob(long jobSlot, long holder) {
         long prevForJob = reqArenaMgr.getPrevJobRequest(holder);
         long nextForJob = reqArenaMgr.getNextJobRequest(holder);
@@ -592,12 +598,15 @@
     }
     
     /**
-     * remove the first request for a given job from a request queue
+     * remove the first request for a given job and lock mode from a request queue.
+     * If the value of the parameter lockMode is LockMode.NL the first request
+     * for the job is removed - independent of the LockMode.
      * @param head the head of the request queue
      * @param jobSlot the job slot
+     * @param lockMode the lock mode 
      * @return the slot of the first request that matched the given job
      */
-    private long removeRequestFromQueueForJob(long head, long jobSlot) {
+    private long removeRequestFromQueueForJob(long head, long jobSlot, byte lockMode) {
         long holder = head;
         long prev = holder;
         while (prev != -1) {
@@ -605,7 +614,7 @@
             if (holder == -1) {
                 throw new IllegalStateException("no entry for job " + jobSlot + " in queue");
             }
-            if (jobSlot == reqArenaMgr.getJobSlot(holder)) {
+            if (requestMatches(holder, jobSlot, lockMode)) {
                 break;
             }
             prev = holder;
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManager.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManager.java
index c7df2f2..b17a787 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManager.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManager.java
@@ -278,7 +278,7 @@
             did = entityInfoManager.getDatasetId(entityInfo);
             entityHashValue = entityInfoManager.getPKHashVal(entityInfo);
             if (did == datasetId.getId() && entityHashValue != -1) {
-                this.unlock(datasetId, entityHashValue, txnContext);
+                this.unlock(datasetId, entityHashValue, LockMode.NL, txnContext);
             }
 
             entityInfo = prevEntityInfo;
@@ -638,7 +638,7 @@
     }
 
     @Override
-    public void unlock(DatasetId datasetId, int entityHashValue, ITransactionContext txnContext) throws ACIDException {
+    public void unlock(DatasetId datasetId, int entityHashValue, byte lockMode, ITransactionContext txnContext) throws ACIDException {
         internalUnlock(datasetId, entityHashValue, txnContext, false);
     }
 
@@ -2211,7 +2211,7 @@
                     tempDatasetIdObj.setId(logRecord.getDatasetId());
                     tempJobIdObj.setId(logRecord.getJobId());
                     txnCtx = txnSubsystem.getTransactionManager().getTransactionContext(tempJobIdObj, false);
-                    unlock(tempDatasetIdObj, logRecord.getPKHashValue(), txnCtx);
+                    unlock(tempDatasetIdObj, logRecord.getPKHashValue(), LockMode.NL, txnCtx);
                     txnCtx.notifyOptracker(false);
                 } else if (logRecord.getLogType() == LogType.JOB_COMMIT || logRecord.getLogType() == LogType.ABORT) {
                     tempJobIdObj.setId(logRecord.getJobId());
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerDeterministicUnitTest.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerDeterministicUnitTest.java
index ea2d4de..1bcfa22 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerDeterministicUnitTest.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerDeterministicUnitTest.java
@@ -486,7 +486,7 @@
                         request.txnContext);
                 break;
             case RequestType.UNLOCK:
-                lockMgr.unlock(request.datasetIdObj, request.entityHashValue, request.txnContext);
+                lockMgr.unlock(request.datasetIdObj, request.entityHashValue, request.lockMode, request.txnContext);
                 break;
             case RequestType.RELEASE_LOCKS:
                 lockMgr.releaseLocks(request.txnContext);
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerRandomUnitTest.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerRandomUnitTest.java
index 11c48a7..8cdc87b 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerRandomUnitTest.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/locking/LockManagerRandomUnitTest.java
@@ -511,7 +511,7 @@
                         request.txnContext);
                 break;
             case RequestType.UNLOCK:
-                lockMgr.unlock(request.datasetIdObj, request.entityHashValue, request.txnContext);
+                lockMgr.unlock(request.datasetIdObj, request.entityHashValue, request.lockMode, request.txnContext);
                 break;
             case RequestType.RELEASE_LOCKS:
                 lockMgr.releaseLocks(request.txnContext);
diff --git a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/logging/LogPage.java b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/logging/LogPage.java
index 75a74c9..e14a0f8 100644
--- a/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/logging/LogPage.java
+++ b/asterix-transactions/src/main/java/edu/uci/ics/asterix/transaction/management/service/logging/LogPage.java
@@ -29,6 +29,7 @@
 import edu.uci.ics.asterix.common.transactions.JobId;
 import edu.uci.ics.asterix.common.transactions.MutableLong;
 import edu.uci.ics.asterix.transaction.management.service.locking.LockManager;
+import edu.uci.ics.asterix.transaction.management.service.transaction.TransactionManagementConstants.LockManagerConstants.LockMode;
 import edu.uci.ics.asterix.transaction.management.service.transaction.TransactionSubsystem;
 
 public class LogPage implements ILogPage {
@@ -202,7 +203,7 @@
                     dsId.setId(logRecord.getDatasetId());
                     jId.setId(logRecord.getJobId());
                     txnCtx = txnSubsystem.getTransactionManager().getTransactionContext(jId, false);
-                    txnSubsystem.getLockManager().unlock(dsId, logRecord.getPKHashValue(), txnCtx);
+                    txnSubsystem.getLockManager().unlock(dsId, logRecord.getPKHashValue(), LockMode.NL, txnCtx);
                     txnCtx.notifyOptracker(false);
                 } else if (logRecord.getLogType() == LogType.JOB_COMMIT || logRecord.getLogType() == LogType.ABORT) {
                     jId.setId(logRecord.getJobId());