diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DatabaseManager.java b/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DatabaseManager.java
index 37e75cf..af3f6ac 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DatabaseManager.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DatabaseManager.java
@@ -179,6 +179,11 @@
         }
 
         client.waitForLeader();
+
+        // Try and list the tables to verify database manager is
+        // in a state where it can serve requests.
+        tryTableListing();
+
         log.info("Started.");
     }
 
@@ -214,6 +219,24 @@
         }
     }
 
+    private void tryTableListing() {
+        int retries = 0;
+        do {
+            try {
+                listTables();
+                return;
+            } catch (DatabaseException e) {
+                if (retries == 10) {
+                    log.error("Failed to listTables after multiple attempts. Giving up.", e);
+                    throw e;
+                } else {
+                    log.debug("Failed to listTables. Will retry...", e);
+                    retries++;
+                }
+            }
+        } while (true);
+    }
+
     @Override
     public boolean createTable(String name) {
         return client.createTable(name);
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLock.java b/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLock.java
index 4998179..f84baaf 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLock.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLock.java
@@ -12,6 +12,7 @@
 
 import org.joda.time.DateTime;
 import org.onlab.onos.cluster.ClusterService;
+import org.onlab.onos.store.service.DatabaseException;
 import org.onlab.onos.store.service.DatabaseService;
 import org.onlab.onos.store.service.Lock;
 import org.slf4j.Logger;
@@ -23,8 +24,6 @@
 
     private final Logger log = getLogger(getClass());
 
-    private static final long MAX_WAIT_TIME_MS = 100000000L;
-
     private final DistributedLockManager lockManager;
     private final DatabaseService databaseService;
     private final String path;
@@ -53,13 +52,17 @@
     }
 
     @Override
-    public void lock(int leaseDurationMillis) {
+    public void lock(int leaseDurationMillis) throws InterruptedException {
         if (isLocked() && lockExpirationTime.isAfter(DateTime.now().plusMillis(leaseDurationMillis))) {
-            // Nothing to do.
-            // Current expiration time is beyond what is requested.
             return;
         } else {
-            tryLock(MAX_WAIT_TIME_MS, leaseDurationMillis);
+            CompletableFuture<DateTime> future =
+                    lockManager.lockIfAvailable(this, leaseDurationMillis);
+            try {
+                lockExpirationTime = future.get();
+            } catch (ExecutionException e) {
+                throw new DatabaseException(e);
+            }
         }
     }
 
@@ -79,22 +82,17 @@
     @Override
     public boolean tryLock(
             long waitTimeMillis,
-            int leaseDurationMillis) {
+            int leaseDurationMillis) throws InterruptedException {
         if (tryLock(leaseDurationMillis)) {
             return true;
         }
-
         CompletableFuture<DateTime> future =
                 lockManager.lockIfAvailable(this, waitTimeMillis, leaseDurationMillis);
         try {
             lockExpirationTime = future.get(waitTimeMillis, TimeUnit.MILLISECONDS);
             return true;
-        } catch (ExecutionException | InterruptedException e) {
-            log.error("Encountered an exception trying to acquire lock for " + path, e);
-            // TODO: ExecutionException could indicate something
-            // wrong with the backing database.
-            // Throw an exception?
-            return false;
+        } catch (ExecutionException e) {
+            throw new DatabaseException(e);
         } catch (TimeoutException e) {
             log.debug("Timed out waiting to acquire lock for {}", path);
             return false;
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLockManager.java b/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLockManager.java
index ea0f7d5..3ec7876 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLockManager.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/service/impl/DistributedLockManager.java
@@ -64,23 +64,22 @@
     @Activate
     public void activate() {
         try {
-            Set<String> tableNames = databaseAdminService.listTables();
-            if (!tableNames.contains(ONOS_LOCK_TABLE_NAME)) {
+            Set<String> tables = databaseAdminService.listTables();
+
+            if (!tables.contains(ONOS_LOCK_TABLE_NAME)) {
                 if (databaseAdminService.createTable(ONOS_LOCK_TABLE_NAME, DEAD_LOCK_TIMEOUT_MS)) {
                     log.info("Created {} table.", ONOS_LOCK_TABLE_NAME);
                 }
             }
         } catch (DatabaseException e) {
             log.error("DistributedLockManager#activate failed.", e);
-            throw e;
         }
 
-        clusterCommunicator.addSubscriber(
-                DatabaseStateMachine.DATABASE_UPDATE_EVENTS,
-                new LockEventMessageListener());
+         clusterCommunicator.addSubscriber(
+                 DatabaseStateMachine.DATABASE_UPDATE_EVENTS,
+                 new LockEventMessageListener());
 
-        log.info("Started.");
-
+         log.info("Started");
     }
 
     @Deactivate
@@ -119,7 +118,31 @@
             long waitTimeMillis,
             int leaseDurationMillis) {
         CompletableFuture<DateTime> future = new CompletableFuture<>();
-        locksToAcquire.put(lock.path(), new LockRequest(lock, waitTimeMillis, leaseDurationMillis, future));
+        LockRequest request = new LockRequest(
+                lock,
+                leaseDurationMillis,
+                DateTime.now().plusMillis(leaseDurationMillis),
+                future);
+        locksToAcquire.put(lock.path(), request);
+        return future;
+    }
+
+    /**
+     * Attempts to acquire the lock as soon as it becomes available.
+     * @param lock lock to acquire.
+     * @param leaseDurationMillis the duration for which to acquire the lock initially.
+     * @return Future lease expiration date.
+     */
+    protected CompletableFuture<DateTime> lockIfAvailable(
+            Lock lock,
+            int leaseDurationMillis) {
+        CompletableFuture<DateTime> future = new CompletableFuture<>();
+        LockRequest request = new LockRequest(
+                lock,
+                leaseDurationMillis,
+                DateTime.now().plusYears(100),
+                future);
+        locksToAcquire.put(lock.path(), request);
         return future;
     }
 
@@ -182,11 +205,14 @@
         private final int leaseDurationMillis;
         private final CompletableFuture<DateTime> future;
 
-        public LockRequest(Lock lock, long waitTimeMillis,
-                int leaseDurationMillis, CompletableFuture<DateTime> future) {
+        public LockRequest(
+                Lock lock,
+                int leaseDurationMillis,
+                DateTime requestExpirationTime,
+                CompletableFuture<DateTime> future) {
 
             this.lock = lock;
-            this.requestExpirationTime = DateTime.now().plusMillis((int) waitTimeMillis);
+            this.requestExpirationTime = requestExpirationTime;
             this.leaseDurationMillis = leaseDurationMillis;
             this.future = future;
         }