diff --git a/core/store/dist/src/main/java/org/onosproject/store/ecmap/EventuallyConsistentMapImpl.java b/core/store/dist/src/main/java/org/onosproject/store/ecmap/EventuallyConsistentMapImpl.java
index 51e5147..3b2129f3 100644
--- a/core/store/dist/src/main/java/org/onosproject/store/ecmap/EventuallyConsistentMapImpl.java
+++ b/core/store/dist/src/main/java/org/onosproject/store/ecmap/EventuallyConsistentMapImpl.java
@@ -258,23 +258,28 @@
     }
 
     private boolean putInternal(K key, V value, Timestamp timestamp) {
-        synchronized (this) {
-            Timestamp removed = removedItems.get(key);
-            if (removed != null && removed.compareTo(timestamp) > 0) {
-                log.debug("ecmap - removed was newer {}", value);
-                return false;
-            }
+        Timestamp removed = removedItems.get(key);
+        if (removed != null && removed.compareTo(timestamp) > 0) {
+            log.debug("ecmap - removed was newer {}", value);
+            return false;
+        }
 
+        boolean success;
+        synchronized (this) {
             Timestamped<V> existing = items.get(key);
             if (existing != null && existing.isNewer(timestamp)) {
                 log.debug("ecmap - existing was newer {}", value);
-                return false;
+                success = false;
             } else {
                 items.put(key, new Timestamped<>(value, timestamp));
-                removedItems.remove(key);
-                return true;
+                success = true;
             }
         }
+
+        if (success && removed != null) {
+            removedItems.remove(key, removed);
+        }
+        return success;
     }
 
     @Override
diff --git a/core/store/dist/src/main/java/org/onosproject/store/impl/Timestamped.java b/core/store/dist/src/main/java/org/onosproject/store/impl/Timestamped.java
index 76a2a14..5b158a0 100644
--- a/core/store/dist/src/main/java/org/onosproject/store/impl/Timestamped.java
+++ b/core/store/dist/src/main/java/org/onosproject/store/impl/Timestamped.java
@@ -77,6 +77,7 @@
      * @param other timestamp to compare against
      * @return true if this instance is newer
      */
+    //TODO put this in Timestamp
     public boolean isNewer(Timestamp other) {
         return this.timestamp.compareTo(checkNotNull(other)) > 0;
     }