diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMapService.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMapService.java
index 1b5cb12..89c8da6 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMapService.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/resources/impl/AtomixConsistentTreeMapService.java
@@ -20,6 +20,7 @@
 import java.util.Map;
 import java.util.NavigableMap;
 import java.util.TreeMap;
+import java.util.concurrent.ConcurrentSkipListMap;
 
 import com.google.common.collect.Maps;
 import io.atomix.protocols.raft.service.Commit;
@@ -75,17 +76,17 @@
             .register(MapEntryValue.class)
             .register(MapEntryValue.Type.class)
             .register(new HashMap().keySet().getClass())
-            .register(TreeMap.class)
+            .register(ConcurrentSkipListMap.class)
             .build());
 
     @Override
-    protected TreeMap<String, MapEntryValue> createMap() {
-        return Maps.newTreeMap();
+    protected NavigableMap<String, MapEntryValue> createMap() {
+        return new ConcurrentSkipListMap<>();
     }
 
     @Override
-    protected TreeMap<String, MapEntryValue> entries() {
-        return (TreeMap<String, MapEntryValue>) super.entries();
+    protected NavigableMap<String, MapEntryValue> entries() {
+        return (NavigableMap<String, MapEntryValue>) super.entries();
     }
 
     @Override