diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/CachingAsyncConsistentMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/CachingAsyncConsistentMap.java
new file mode 100644
index 0000000..aaa01e4
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/CachingAsyncConsistentMap.java
@@ -0,0 +1,141 @@
+/*
+ * 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.impl;
+
+import java.util.concurrent.CompletableFuture;
+import java.util.function.BiFunction;
+import java.util.function.Predicate;
+
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.Versioned;
+
+import com.google.common.cache.CacheBuilder;
+import com.google.common.cache.CacheLoader;
+import com.google.common.cache.LoadingCache;
+
+/**
+ * {@code AsyncConsistentMap} that caches entries on read.
+ * <p>
+ * The cache entries are automatically invalidated when updates are detected either locally or
+ * remotely.
+ * <p> This implementation only attempts to serve cached entries for {@link AsyncConsistentMap#get get}
+ * calls. All other calls skip the cache and directly go the backing map.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class CachingAsyncConsistentMap<K, V> extends DelegatingAsyncConsistentMap<K, V> {
+
+    private final LoadingCache<K, CompletableFuture<Versioned<V>>> cache =
+            CacheBuilder.newBuilder()
+                        .maximumSize(10000) // TODO: make configurable
+                        .build(new CacheLoader<K, CompletableFuture<Versioned<V>>>() {
+                            @Override
+                            public CompletableFuture<Versioned<V>> load(K key)
+                                    throws Exception {
+                                return CachingAsyncConsistentMap.super.get(key);
+                            }
+                        });
+
+    public CachingAsyncConsistentMap(AsyncConsistentMap<K, V> backingMap) {
+        super(backingMap);
+        super.addListener(event -> cache.invalidate(event.key()));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> get(K key) {
+        return cache.getUnchecked(key);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> computeIf(K key,
+            Predicate<? super V> condition,
+            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return super.computeIf(key, condition, remappingFunction)
+                    .whenComplete((r, e) -> cache.invalidate(key));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> put(K key, V value) {
+        return super.put(key, value)
+                    .whenComplete((r, e) -> cache.invalidate(key));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putAndGet(K key, V value) {
+        return super.put(key, value)
+                    .whenComplete((r, e) -> cache.invalidate(key));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> remove(K key) {
+        return super.remove(key)
+                    .whenComplete((r, e) -> cache.invalidate(key));
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return super.clear()
+                    .whenComplete((r, e) -> cache.invalidateAll());
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        return super.remove(key, value)
+                    .whenComplete((r, e) -> {
+                        if (r) {
+                            cache.invalidate(key);
+                        }
+                    });
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, long version) {
+        return super.remove(key, version)
+                .whenComplete((r, e) -> {
+                    if (r) {
+                        cache.invalidate(key);
+                    }
+                });
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> replace(K key, V value) {
+        return super.replace(key, value)
+                    .whenComplete((r, e) -> cache.invalidate(key));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, V oldValue, V newValue) {
+        return super.replace(key, oldValue, newValue)
+                .whenComplete((r, e) -> {
+                    if (r) {
+                        cache.invalidate(key);
+                    }
+                });
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, long oldVersion, V newValue) {
+        return super.replace(key, oldVersion, newValue)
+                .whenComplete((r, e) -> {
+                    if (r) {
+                        cache.invalidate(key);
+                    }
+                });
+    }
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DelegatingAsyncConsistentMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DelegatingAsyncConsistentMap.java
new file mode 100644
index 0000000..76d7488
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DelegatingAsyncConsistentMap.java
@@ -0,0 +1,183 @@
+/*
+ * 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.impl;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import java.util.Collection;
+import java.util.Map.Entry;
+import java.util.Objects;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.function.BiFunction;
+import java.util.function.Predicate;
+
+import org.onosproject.core.ApplicationId;
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Versioned;
+
+import com.google.common.base.MoreObjects;
+
+/**
+ * {@code AsyncConsistentMap} that merely delegates control to
+ * another AsyncConsistentMap.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class DelegatingAsyncConsistentMap<K, V> implements AsyncConsistentMap<K, V> {
+
+    private final AsyncConsistentMap<K, V> delegateMap;
+
+    DelegatingAsyncConsistentMap(AsyncConsistentMap<K, V> delegateMap) {
+        this.delegateMap = checkNotNull(delegateMap, "delegate map cannot be null");
+    }
+
+    @Override
+    public String name() {
+        return delegateMap.name();
+    }
+
+    @Override
+    public ApplicationId applicationId() {
+        return delegateMap.applicationId();
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        return delegateMap.size();
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsKey(K key) {
+        return delegateMap.containsKey(key);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsValue(V value) {
+        return delegateMap.containsValue(value);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> get(K key) {
+        return delegateMap.get(key);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> computeIf(K key,
+            Predicate<? super V> condition,
+            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return delegateMap.computeIf(key, condition, remappingFunction);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> put(K key, V value) {
+        return delegateMap.put(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putAndGet(K key, V value) {
+        return delegateMap.putAndGet(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> remove(K key) {
+        return delegateMap.remove(key);
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return delegateMap.clear();
+    }
+
+    @Override
+    public CompletableFuture<Set<K>> keySet() {
+        return delegateMap.keySet();
+    }
+
+    @Override
+    public CompletableFuture<Collection<Versioned<V>>> values() {
+        return delegateMap.values();
+    }
+
+    @Override
+    public CompletableFuture<Set<Entry<K, Versioned<V>>>> entrySet() {
+        return delegateMap.entrySet();
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putIfAbsent(K key, V value) {
+        return delegateMap.putIfAbsent(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        return delegateMap.remove(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, long version) {
+        return delegateMap.remove(key, version);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> replace(K key, V value) {
+        return delegateMap.replace(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, V oldValue, V newValue) {
+        return delegateMap.replace(key, oldValue, newValue);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, long oldVersion, V newValue) {
+        return delegateMap.replace(key, oldVersion, newValue);
+    }
+
+    @Override
+    public CompletableFuture<Void> addListener(MapEventListener<K, V> listener) {
+        return delegateMap.addListener(listener);
+    }
+
+    @Override
+    public CompletableFuture<Void> removeListener(MapEventListener<K, V> listener) {
+        return delegateMap.removeListener(listener);
+    }
+
+    @Override
+    public String toString() {
+        return MoreObjects.toStringHelper(getClass())
+                          .add("delegateMap", delegateMap)
+                          .toString();
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(delegateMap);
+    }
+
+    @Override
+    public boolean equals(Object other) {
+        if (other instanceof DelegatingAsyncConsistentMap) {
+            DelegatingAsyncConsistentMap<K, V> that = (DelegatingAsyncConsistentMap) other;
+            return this.delegateMap.equals(that.delegateMap);
+        }
+        return false;
+    }
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/Hasher.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/Hasher.java
new file mode 100644
index 0000000..96de934
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/Hasher.java
@@ -0,0 +1,32 @@
+/*
+ * 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.impl;
+
+import org.onosproject.cluster.PartitionId;
+
+/**
+ * Interface for mapping from an object to {@link PartitionId}.
+ *
+ * @param <K> object type.
+ */
+public interface Hasher<K> {
+    /**
+     * Returns the {@link PartitionId} to which the specified object maps.
+     * @param object object
+     * @return partition identifier
+     */
+    PartitionId hash(K object);
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/MeteredAsyncConsistentMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/MeteredAsyncConsistentMap.java
new file mode 100644
index 0000000..540d0ad
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/MeteredAsyncConsistentMap.java
@@ -0,0 +1,262 @@
+/*
+ * 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.impl;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+import java.util.function.Predicate;
+
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.MapEvent;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Versioned;
+
+import com.google.common.base.Throwables;
+import com.google.common.collect.Maps;
+
+/**
+ * {@link AsyncConsistentMap} that meters all its operations.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class MeteredAsyncConsistentMap<K, V>  extends DelegatingAsyncConsistentMap<K, V> {
+
+    private static final String PRIMITIVE_NAME = "consistentMap";
+    private static final String SIZE = "size";
+    private static final String IS_EMPTY = "isEmpty";
+    private static final String CONTAINS_KEY = "containsKey";
+    private static final String CONTAINS_VALUE = "containsValue";
+    private static final String GET = "get";
+    private static final String COMPUTE_IF = "computeIf";
+    private static final String PUT = "put";
+    private static final String PUT_AND_GET = "putAndGet";
+    private static final String PUT_IF_ABSENT = "putIfAbsent";
+    private static final String REMOVE = "remove";
+    private static final String CLEAR = "clear";
+    private static final String KEY_SET = "keySet";
+    private static final String VALUES = "values";
+    private static final String ENTRY_SET = "entrySet";
+    private static final String REPLACE = "replace";
+    private static final String COMPUTE_IF_ABSENT = "computeIfAbsent";
+    private static final String ADD_LISTENER = "addListener";
+    private static final String REMOVE_LISTENER = "removeListener";
+    private static final String NOTIFY_LISTENER = "notifyListener";
+
+    private final Map<MapEventListener<K, V>, InternalMeteredMapEventListener> listeners =
+            Maps.newIdentityHashMap();
+    private final MeteringAgent monitor;
+
+    public MeteredAsyncConsistentMap(AsyncConsistentMap<K, V> backingMap) {
+        super(backingMap);
+        this.monitor = new MeteringAgent(PRIMITIVE_NAME, backingMap.name(), true);
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        final MeteringAgent.Context timer = monitor.startTimer(SIZE);
+        return super.size()
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> isEmpty() {
+        final MeteringAgent.Context timer = monitor.startTimer(IS_EMPTY);
+        return super.isEmpty()
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsKey(K key) {
+        final MeteringAgent.Context timer = monitor.startTimer(CONTAINS_KEY);
+        return super.containsKey(key)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsValue(V value) {
+        final MeteringAgent.Context timer = monitor.startTimer(CONTAINS_VALUE);
+        return super.containsValue(value)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> get(K key) {
+        final MeteringAgent.Context timer = monitor.startTimer(GET);
+        return super.get(key)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> computeIfAbsent(K key,
+                                                           Function<? super K, ? extends V> mappingFunction) {
+        final MeteringAgent.Context timer = monitor.startTimer(COMPUTE_IF_ABSENT);
+        return super.computeIfAbsent(key, mappingFunction)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> computeIf(K key,
+                                                     Predicate<? super V> condition,
+                                                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        final MeteringAgent.Context timer = monitor.startTimer(COMPUTE_IF);
+        return super.computeIf(key, condition, remappingFunction)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> put(K key, V value) {
+        final MeteringAgent.Context timer = monitor.startTimer(PUT);
+        return super.put(key, value)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putAndGet(K key, V value) {
+        final MeteringAgent.Context timer = monitor.startTimer(PUT_AND_GET);
+        return super.putAndGet(key, value)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> remove(K key) {
+        final MeteringAgent.Context timer = monitor.startTimer(REMOVE);
+        return super.remove(key)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        final MeteringAgent.Context timer = monitor.startTimer(CLEAR);
+        return super.clear()
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Set<K>> keySet() {
+        final MeteringAgent.Context timer = monitor.startTimer(KEY_SET);
+        return super.keySet()
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Collection<Versioned<V>>> values() {
+        final MeteringAgent.Context timer = monitor.startTimer(VALUES);
+        return super.values()
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Set<Entry<K, Versioned<V>>>> entrySet() {
+        final MeteringAgent.Context timer = monitor.startTimer(ENTRY_SET);
+        return super.entrySet()
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putIfAbsent(K key, V value) {
+        final MeteringAgent.Context timer = monitor.startTimer(PUT_IF_ABSENT);
+        return super.putIfAbsent(key, value)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        final MeteringAgent.Context timer = monitor.startTimer(REMOVE);
+        return super.remove(key, value)
+                    .whenComplete((r, e) -> timer.stop(e));
+
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, long version) {
+        final MeteringAgent.Context timer = monitor.startTimer(REMOVE);
+        return super.remove(key, version)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> replace(K key, V value) {
+        final MeteringAgent.Context timer = monitor.startTimer(REPLACE);
+        return super.replace(key, value)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, V oldValue, V newValue) {
+        final MeteringAgent.Context timer = monitor.startTimer(REPLACE);
+        return super.replace(key, oldValue, newValue)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, long oldVersion, V newValue) {
+        final MeteringAgent.Context timer = monitor.startTimer(REPLACE);
+        return super.replace(key, oldVersion, newValue)
+                    .whenComplete((r, e) -> timer.stop(e));
+    }
+
+    @Override
+    public CompletableFuture<Void> addListener(MapEventListener<K, V> listener) {
+        final MeteringAgent.Context timer = monitor.startTimer(ADD_LISTENER);
+        synchronized (listeners) {
+            InternalMeteredMapEventListener meteredListener =
+                    listeners.computeIfAbsent(listener, k -> new InternalMeteredMapEventListener(listener));
+            return super.addListener(meteredListener)
+                        .whenComplete((r, e) -> timer.stop(e));
+        }
+    }
+
+    @Override
+    public CompletableFuture<Void> removeListener(MapEventListener<K, V> listener) {
+        final MeteringAgent.Context timer = monitor.startTimer(REMOVE_LISTENER);
+        InternalMeteredMapEventListener meteredListener = listeners.remove(listener);
+        if (meteredListener != null) {
+            return super.removeListener(listener)
+                        .whenComplete((r, e) -> timer.stop(e));
+        } else {
+            timer.stop(null);
+            return CompletableFuture.completedFuture(null);
+        }
+    }
+
+    private class InternalMeteredMapEventListener implements MapEventListener<K, V> {
+
+        private final MapEventListener<K, V> listener;
+
+        InternalMeteredMapEventListener(MapEventListener<K, V> listener) {
+            this.listener = listener;
+        }
+
+        @Override
+        public void event(MapEvent<K, V> event) {
+            final MeteringAgent.Context timer = monitor.startTimer(NOTIFY_LISTENER);
+            try {
+                listener.event(event);
+                timer.stop(null);
+            } catch (Exception e) {
+                timer.stop(e);
+                Throwables.propagate(e);
+            }
+        }
+    }
+}
\ No newline at end of file
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/PartitionedAsyncConsistentMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/PartitionedAsyncConsistentMap.java
new file mode 100644
index 0000000..3090436
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/PartitionedAsyncConsistentMap.java
@@ -0,0 +1,217 @@
+/*
+ * 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.impl;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.TreeMap;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.atomic.AtomicBoolean;
+import java.util.concurrent.atomic.AtomicInteger;
+import java.util.function.BiFunction;
+import java.util.function.Predicate;
+
+import org.onosproject.cluster.PartitionId;
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Versioned;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
+
+/**
+ * {@link AsyncConsistentMap} that has its entries partitioned horizontally across
+ * several {@link AsyncConsistentMap maps}.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class PartitionedAsyncConsistentMap<K, V> implements AsyncConsistentMap<K, V> {
+
+    private final String name;
+    private final TreeMap<PartitionId, AsyncConsistentMap<K, V>> partitions = Maps.newTreeMap();
+    private final Hasher<K> keyHasher;
+
+    public PartitionedAsyncConsistentMap(String name,
+            Map<PartitionId, AsyncConsistentMap<K, V>> partitions,
+            Hasher<K> keyHasher) {
+        this.name = name;
+        this.partitions.putAll(checkNotNull(partitions));
+        this.keyHasher = checkNotNull(keyHasher);
+    }
+
+    @Override
+    public String name() {
+        return name;
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        AtomicInteger totalSize = new AtomicInteger(0);
+        return CompletableFuture.allOf(getMaps()
+                                      .stream()
+                                      .map(map -> map.size().thenAccept(totalSize::addAndGet))
+                                      .toArray(CompletableFuture[]::new))
+                                .thenApply(v -> totalSize.get());
+    }
+
+    @Override
+    public CompletableFuture<Boolean> isEmpty() {
+        return size().thenApply(size -> size == 0);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsKey(K key) {
+        return getMap(key).containsKey(key);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsValue(V value) {
+        AtomicBoolean contains = new AtomicBoolean(false);
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.containsValue(value)
+                                                               .thenAccept(v -> contains.set(contains.get() || v)))
+                                                .toArray(CompletableFuture[]::new))
+                                .thenApply(v -> contains.get());
+    }
+    @Override
+    public CompletableFuture<Versioned<V>> get(K key) {
+        return getMap(key).get(key);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> computeIf(K key,
+            Predicate<? super V> condition,
+            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return getMap(key).computeIf(key, condition, remappingFunction);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> put(K key, V value) {
+        return getMap(key).put(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putAndGet(K key, V value) {
+        return getMap(key).putAndGet(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> remove(K key) {
+        return getMap(key).remove(key);
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.clear())
+                                                .toArray(CompletableFuture[]::new));
+    }
+
+    @Override
+    public CompletableFuture<Set<K>> keySet() {
+        Set<K> allKeys = Sets.newConcurrentHashSet();
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.keySet().thenAccept(allKeys::addAll))
+                                                .toArray(CompletableFuture[]::new))
+                                .thenApply(v -> allKeys);
+    }
+
+    @Override
+    public CompletableFuture<Collection<Versioned<V>>> values() {
+        List<Versioned<V>> allValues = Lists.newCopyOnWriteArrayList();
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.values().thenAccept(allValues::addAll))
+                                                .toArray(CompletableFuture[]::new))
+                                .thenApply(v -> allValues);
+    }
+
+    @Override
+    public CompletableFuture<Set<Entry<K, Versioned<V>>>> entrySet() {
+        Set<Entry<K, Versioned<V>>> allEntries = Sets.newConcurrentHashSet();
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.entrySet().thenAccept(allEntries::addAll))
+                                                .toArray(CompletableFuture[]::new))
+                                .thenApply(v -> allEntries);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putIfAbsent(K key, V value) {
+        return getMap(key).putIfAbsent(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        return getMap(key).remove(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, long version) {
+        return getMap(key).remove(key, version);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> replace(K key, V value) {
+        return getMap(key).replace(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, V oldValue, V newValue) {
+        return getMap(key).replace(key, oldValue, newValue);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, long oldVersion, V newValue) {
+        return getMap(key).replace(key, oldVersion, newValue);
+    }
+
+    @Override
+    public CompletableFuture<Void> addListener(MapEventListener<K, V> listener) {
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.addListener(listener))
+                                                .toArray(CompletableFuture[]::new));
+    }
+
+    @Override
+    public CompletableFuture<Void> removeListener(MapEventListener<K, V> listener) {
+        return CompletableFuture.allOf(getMaps().stream()
+                                                .map(map -> map.removeListener(listener))
+                                                .toArray(CompletableFuture[]::new));
+    }
+
+    /**
+     * Returns the map (partition) to which the specified key maps.
+     * @param key key
+     * @return AsyncConsistentMap to which key maps
+     */
+    private AsyncConsistentMap<K, V> getMap(K key) {
+        return partitions.get(keyHasher.hash(key));
+    }
+
+    /**
+     * Returns all the constituent maps.
+     * @return collection of maps.
+     */
+    private Collection<AsyncConsistentMap<K, V>> getMaps() {
+        return partitions.values();
+    }
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/UnmodifiableAsyncConsistentMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/UnmodifiableAsyncConsistentMap.java
new file mode 100644
index 0000000..30efc36
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/UnmodifiableAsyncConsistentMap.java
@@ -0,0 +1,98 @@
+/*
+ * 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.impl;
+
+import java.util.concurrent.CompletableFuture;
+import java.util.function.BiFunction;
+import java.util.function.Predicate;
+
+import org.onlab.util.Tools;
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.Versioned;
+
+/**
+ * An unmodifiable {@link AsyncConsistentMap}.
+ * <p>
+ * Any attempt to update the map through this instance will cause the
+ * operation to be completed with an {@link UnsupportedOperationException}.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class UnmodifiableAsyncConsistentMap<K, V> extends DelegatingAsyncConsistentMap<K, V> {
+
+    public UnmodifiableAsyncConsistentMap(AsyncConsistentMap<K, V> backingMap) {
+        super(backingMap);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> computeIf(K key,
+            Predicate<? super V> condition,
+            BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> put(K key, V value) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putAndGet(K key, V value) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> remove(K key) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> putIfAbsent(K key, V value) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, long version) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V>> replace(K key, V value) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, V oldValue, V newValue) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K key, long oldVersion, V newValue) {
+        return Tools.exceptionalFuture(new UnsupportedOperationException("map updates are not allowed"));
+    }
+}