diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
new file mode 100644
index 0000000..ba5a8bf
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentTreeMap.java
@@ -0,0 +1,279 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.store.primitives;
+
+import com.google.common.base.Throwables;
+import org.onosproject.store.service.ConsistentMapException;
+import org.onosproject.store.service.AsyncConsistentTreeMap;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Synchronous;
+import org.onosproject.store.service.ConsistentTreeMap;
+import org.onosproject.store.service.Versioned;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.NavigableSet;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.ExecutionException;
+import java.util.concurrent.TimeUnit;
+import java.util.concurrent.TimeoutException;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+/**
+ * Implementation of the {@link ConsistentTreeMap} interface.
+ */
+public class DefaultConsistentTreeMap<K, V> extends Synchronous<AsyncConsistentTreeMap<K, V>>
+        implements ConsistentTreeMap<K, V> {
+    private static final int MAX_DELAY_BETWEEN_RETRY_MILLIS = 50;
+    private final AsyncConsistentTreeMap<K, V> treeMap;
+    private final long operationTimeoutMillis;
+    private Map<K, V> javaMap;
+
+    public DefaultConsistentTreeMap(AsyncConsistentTreeMap<K, V> treeMap, long operationTimeoutMillis) {
+        super(treeMap);
+        this.treeMap = treeMap;
+        this.operationTimeoutMillis = operationTimeoutMillis;
+    }
+
+    private <T> T complete(CompletableFuture<T> future) {
+        try {
+            return future.get(operationTimeoutMillis, TimeUnit.MILLISECONDS);
+        } catch (InterruptedException e) {
+            Thread.currentThread().interrupt();
+            throw new ConsistentMapException.Interrupted();
+        } catch (ExecutionException e) {
+            throw new ConsistentMapException.Timeout();
+        } catch (TimeoutException e) {
+            Throwables.propagateIfPossible(e.getCause());
+            throw new ConsistentMapException(e.getCause());
+        }
+    }
+
+    @Override
+    public K firstKey() {
+        return complete(treeMap.firstKey());
+    }
+
+    @Override
+    public K lastKey() {
+        return complete(treeMap.lastKey());
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> ceilingEntry(K key) {
+        return complete(treeMap.ceilingEntry(key));
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> floorEntry(K key) {
+        return complete(treeMap.floorEntry(key));
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> higherEntry(K key) {
+        return complete(treeMap.higherEntry(key));
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> lowerEntry(K key) {
+        return complete(treeMap.lowerEntry(key));
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> firstEntry() {
+        return complete(treeMap.firstEntry());
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> lastEntry() {
+        return complete(treeMap.lastEntry());
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> pollFirstEntry() {
+        return complete(treeMap.pollFirstEntry());
+    }
+
+    @Override
+    public Map.Entry<K, Versioned<V>> pollLastEntry() {
+        return complete(treeMap.pollLastEntry());
+    }
+
+    @Override
+    public K lowerKey(K key) {
+        return complete(treeMap.lowerKey(key));
+    }
+
+    @Override
+    public K floorKey(K key) {
+        return complete(treeMap.floorKey(key));
+    }
+
+    @Override
+    public K ceilingKey(K key) {
+        return complete(treeMap.ceilingKey(key));
+    }
+
+    @Override
+    public K higherKey(K key) {
+        return complete(treeMap.higherKey(key));
+    }
+
+
+    @Override
+    /**
+     * {@inheritDoc}
+     * <p>This may be a long operation with greater risk of timeout.</p>
+     */
+    public NavigableSet<K> navigableKeySet() {
+        return complete(treeMap.navigableKeySet());
+    }
+
+    @Override
+    public int size() {
+        return complete(treeMap.size());
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return complete(treeMap.isEmpty());
+    }
+
+    @Override
+    public boolean containsKey(K key) {
+        return complete(treeMap.containsKey(key));
+    }
+
+    @Override
+    public boolean containsValue(V value) {
+        return complete(treeMap.containsValue(value));
+    }
+
+    @Override
+    public Versioned<V> get(K key) {
+        return complete(treeMap.get(key));
+    }
+
+    @Override
+    public Versioned<V> computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction) {
+        return complete(treeMap.computeIfAbsent(key, mappingFunction));
+    }
+
+    @Override
+    public Versioned<V> compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return complete(treeMap.compute(key, remappingFunction));
+    }
+
+    @Override
+    public Versioned<V> computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return complete(treeMap.computeIfPresent(key, remappingFunction));
+    }
+
+    @Override
+    public Versioned<V> computeIf(K key, Predicate<? super V> condition,
+                                  BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return complete(treeMap.computeIf(key, condition, remappingFunction));
+    }
+
+    @Override
+    public Versioned<V> put(K key, V value) {
+        return complete(treeMap.put(key, value));
+    }
+
+    @Override
+    public Versioned<V> putAndGet(K key, V value) {
+        return complete(treeMap.putAndGet(key, value));
+    }
+
+    @Override
+    public Versioned<V> remove(K key) {
+        return complete(treeMap.remove(key));
+    }
+
+    @Override
+    public void clear() {
+        complete(treeMap.clear());
+    }
+
+    @Override
+    public Set<K> keySet() {
+        return complete(treeMap.keySet());
+    }
+
+    @Override
+    public Collection<Versioned<V>> values() {
+        return complete(treeMap.values());
+    }
+
+    @Override
+    public Set<Map.Entry<K, Versioned<V>>> entrySet() {
+        return complete(treeMap.entrySet());
+    }
+
+    @Override
+    public Versioned<V> putIfAbsent(K key, V value) {
+        return complete(treeMap.putIfAbsent(key, value));
+    }
+
+    @Override
+    public boolean remove(K key, V value) {
+        return complete(treeMap.remove(key, value));
+    }
+
+    @Override
+    public boolean remove(K key, long version) {
+        return complete(treeMap.remove(key, version));
+    }
+
+    @Override
+    public Versioned<V> replace(K key, V value) {
+        return complete(treeMap.replace(key, value));
+    }
+
+    @Override
+    public boolean replace(K key, V oldValue, V newValue) {
+        return complete(treeMap.replace(key, oldValue, newValue));
+    }
+
+    @Override
+    public boolean replace(K key, long oldVersion, V newValue) {
+        return complete(treeMap.replace(key, oldVersion, newValue));
+    }
+
+    @Override
+    public void addListener(MapEventListener<K, V> listener) {
+        complete(treeMap.addListener(listener));
+    }
+
+    @Override
+    public void removeListener(MapEventListener<K, V> listener) {
+        complete(treeMap.removeListener(listener));
+    }
+
+    @Override
+    public Map<K, V> asJavaMap() {
+        synchronized (this) {
+            if (javaMap == null) {
+                javaMap = new ConsistentMapBackedJavaMap<>(this);
+            }
+        }
+        return javaMap;
+    }
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java
new file mode 100644
index 0000000..d5cc522
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentTreeMap.java
@@ -0,0 +1,152 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.store.service;
+
+import org.onosproject.store.primitives.DefaultConsistentTreeMap;
+
+import java.util.Map;
+import java.util.NavigableSet;
+import java.util.concurrent.CompletableFuture;
+
+/**
+ * API for a distributed tree map implementation.
+ */
+public interface AsyncConsistentTreeMap<K, V> extends AsyncConsistentMap<K, V> {
+
+    /**
+     * Return the lowest key in the map.
+     *
+     * @return the key or null if none exist
+     */
+    CompletableFuture<K> firstKey();
+
+    /**
+     * Return the highest key in the map.
+     *
+     * @return the key or null if none exist
+     */
+    CompletableFuture<K> lastKey();
+
+    /**
+     * Returns the entry associated with the least key greater than or equal to the key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> ceilingEntry(K key);
+
+    /**
+     * Returns the entry associated with the greatest key less than or equal to key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> floorEntry(K key);
+
+    /**
+     * Returns the entry associated with the lest key greater than key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> higherEntry(K key);
+
+    /**
+     * Returns the entry associated with the largest key less than key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> lowerEntry(K key);
+
+    /**
+     * Return the entry associated with the lowest key in the map.
+     *
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> firstEntry();
+
+    /**
+     * Return the entry assocaited with the highest key in the map.
+     *
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> lastEntry();
+
+    /**
+     * Return and remove the entry associated with the lowest key.
+     *
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> pollFirstEntry();
+
+    /**
+     * Return and remove the entry associated with the highest key.
+     *
+     * @return the entry or null
+     */
+    CompletableFuture<Map.Entry<K, Versioned<V>>> pollLastEntry();
+
+    /**
+     * Return the entry associated with the greatest key less than key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+    CompletableFuture<K> lowerKey(K key);
+
+    /**
+     * Return the entry associated with the highest key less than or equal to key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+    CompletableFuture<K> floorKey(K key);
+
+    /**
+     * Return the lowest key greater than or equal to key.
+     *
+     * @param key the key
+     * @return the key or null
+     */
+    CompletableFuture<K> ceilingKey(K key);
+
+    /**
+     * Return the lowest key greater than key.
+     *
+     * @param key the key
+     * @return the key or null
+     */
+    CompletableFuture<K> higherKey(K key);
+
+    /**
+     * Returns a navigable set of the keys in this map.
+     *
+     * @return a navigable key set
+     */
+    CompletableFuture<NavigableSet<K>> navigableKeySet();
+
+    default ConsistentTreeMap<K, V> asTreeMap() {
+        return asTreeMap(DistributedPrimitive.DEFAULT_OPERTATION_TIMEOUT_MILLIS);
+    }
+
+    default ConsistentTreeMap<K, V> asTreeMap(long timeoutMillis) {
+        return new DefaultConsistentTreeMap<>(this, timeoutMillis);
+    }
+
+
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java
new file mode 100644
index 0000000..0b83606
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentTreeMap.java
@@ -0,0 +1,140 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.store.service;
+
+import java.util.Map;
+import java.util.NavigableSet;
+
+/**
+ * Tree map interface counterpart to {@link AsyncConsistentTreeMap}.
+ */
+ public interface ConsistentTreeMap<K, V> extends ConsistentMap<K, V> {
+
+    /**
+     * Returns the lowest key in the map.
+     *
+     * @return the key or null if none exist
+     */
+     K firstKey();
+
+    /**
+     * Returns the highest key in the map.
+     *
+     * @return the key or null if none exist
+     */
+     K lastKey();
+
+    /**
+     * Returns the entry associated with the least key greater than or equal to the key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> ceilingEntry(K key);
+
+    /**
+     * Returns the entry associated with the greatest key less than or equal to key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> floorEntry(K key);
+
+    /**
+     * Returns the entry associated with the lest key greater than key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> higherEntry(K key);
+
+    /**
+     * Returns the entry associated with the largest key less than key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> lowerEntry(K key);
+
+    /**
+     * Returns the entry associated with the lowest key in the map.
+     *
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> firstEntry();
+
+    /**
+     * Returns the entry associated with the highest key in the map.
+     *
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> lastEntry();
+
+    /**
+     * Returns and removes the entry associated with the lowest key.
+     *
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> pollFirstEntry();
+
+    /**
+     * Returns and removes the entry associated with the highest key.
+     *
+     * @return the entry or null
+     */
+     Map.Entry<K, Versioned<V>> pollLastEntry();
+
+    /**
+     * Returns the entry associated with the greatest key less than key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+     K lowerKey(K key);
+
+    /**
+     * Returns the entry associated with the highest key less than or equal to key.
+     *
+     * @param key the key
+     * @return the entry or null
+     */
+     K floorKey(K key);
+
+    /**
+     * Returns the lowest key greater than or equal to key.
+     *
+     * @param key the key
+     * @return the key or null
+     */
+     K ceilingKey(K key);
+
+    /**
+     * Returns the lowest key greater than key.
+     *
+     * @param key the key
+     * @return the key or null
+     */
+     K higherKey(K key);
+
+    /**
+     * Returns a navigable set of the keys in this map.
+     *
+     * @return a navigable key set
+     */
+     NavigableSet<K> navigableKeySet();
+
+}