diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java b/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
index b0a25f2..2e986c4 100644
--- a/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DistributedPrimitiveCreator.java
@@ -20,6 +20,7 @@
 import org.onosproject.store.service.AsyncAtomicCounter;
 import org.onosproject.store.service.AsyncAtomicValue;
 import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncConsistentMultimap;
 import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AsyncDistributedSet;
 import org.onosproject.store.service.AsyncDocumentTree;
@@ -51,7 +52,20 @@
      * @param <V> value type
      * @return distributedTreeMap
      */
-    <V> AsyncConsistentTreeMap<V> newAsyncConsistentTreeMap(String name, Serializer serializer);
+    <V> AsyncConsistentTreeMap<V> newAsyncConsistentTreeMap(
+            String name, Serializer serializer);
+
+    /**
+     * Creates a new set backed {@code AsyncConsistentMultimap}.
+     *
+     * @param name multimap name
+     * @param serializer serializer to use for serializing/deserializing
+     * @param <K> key type
+     * @param <V> value type
+     * @return set backed distributedMultimap
+     */
+    <K, V> AsyncConsistentMultimap<K, V> newAsyncConsistentSetMultimap(
+            String name, Serializer serializer);
 
     /**
      * Creates a new {@code AsyncAtomicCounter}.
diff --git a/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentMultimap.java b/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentMultimap.java
index a0f3b84..da121c9 100644
--- a/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentMultimap.java
+++ b/core/api/src/main/java/org/onosproject/store/service/AsyncConsistentMultimap.java
@@ -17,6 +17,7 @@
 package org.onosproject.store.service;
 
 import com.google.common.collect.Multiset;
+import org.onosproject.store.primitives.DefaultConsistentMultimap;
 
 import java.util.Collection;
 import java.util.Map;
@@ -229,4 +230,32 @@
      * values, the returned map may be empty.
      */
     CompletableFuture<Map<K, Collection<V>>> asMap();
+
+    /**
+     * Returns a {@code ConsistentMultimap} instance that wraps this map. All
+     * calls will have the same behavior as this map but will be blocking
+     * instead of asynchronous. If a call does not complete within the
+     * default timeout an exception will be produced.
+     *
+     * @return a {@code ConsistentMultimap} which wraps this map, providing
+     * synchronous access to this map
+     */
+    default ConsistentMultimap<K, V> asMultimap() {
+        return asMultimap(DEFAULT_OPERTATION_TIMEOUT_MILLIS);
+    }
+
+    /**
+     * Returns a {@code ConsistentMultimap} instance that wraps this map. All
+     * calls will have the same behavior as this map but will be blocking
+     * instead of asynchronous. If a call does not complete within the
+     * specified timeout an exception will be produced.
+     *
+     * @param timeoutMillis the number of millis to block while waiting for a
+     *                      call to return
+     * @return a {@code ConsistentMultimap} which wraps this map, providing
+     * synchronous access to this map
+     */
+    default ConsistentMultimap<K, V> asMultimap(long timeoutMillis) {
+        return new DefaultConsistentMultimap(this, timeoutMillis);
+    }
 }
diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimapBuilder.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimapBuilder.java
new file mode 100644
index 0000000..1881d795
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimapBuilder.java
@@ -0,0 +1,62 @@
+/*
+ * 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.DistributedPrimitiveBuilder;
+
+/**
+ * A builder class for {@code AsyncConsistentMultimap}.
+ */
+public abstract class ConsistentMultimapBuilder<K, V>
+        extends DistributedPrimitiveBuilder<ConsistentMultimapBuilder<K, V>,
+        ConsistentMultimap<K, V>> {
+
+    private boolean purgeOnUninstall = false;
+
+    public ConsistentMultimapBuilder() {
+        super(DistributedPrimitive.Type.CONSISTENT_MULTIMAP);
+    }
+
+    /**
+     * Clears multimap contents when the owning application is uninstalled.
+     *
+     * @return this builder
+     */
+    public ConsistentMultimapBuilder<K, V> withPurgeOnUninstall() {
+        purgeOnUninstall = true;
+        return this;
+    }
+
+    /**
+     * Returns if multimap entries need to be cleared when owning application
+     * is uninstalled.
+     *
+     * @return true if items are to be cleared on uninstall
+     */
+    public boolean purgeOnUninstall() {
+        return purgeOnUninstall;
+    }
+
+    /**
+     * Builds the distributed multimap based on the configuration options
+     * supplied to this builder.
+     *
+     * @return new distributed multimap
+     * @throws java.lang.RuntimeException if a mandatory parameter is missing
+     */
+    public abstract AsyncConsistentMultimap<K, V> buildMultimap();
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/StorageService.java b/core/api/src/main/java/org/onosproject/store/service/StorageService.java
index 21fdfda..d532be2 100644
--- a/core/api/src/main/java/org/onosproject/store/service/StorageService.java
+++ b/core/api/src/main/java/org/onosproject/store/service/StorageService.java
@@ -60,6 +60,15 @@
     <V> ConsistentTreeMapBuilder<V> consistentTreeMapBuilder();
 
     /**
+     * Creates a new {@code AsyncConsistentSetMultimapBuilder}.
+     *
+     * @param <K> key type
+     * @param <V> value type
+     * @return builder for a set based async consistent multimap
+     */
+    <K, V> ConsistentMultimapBuilder<K, V> consistentMultimapBuilder();
+
+    /**
      * Creates a new DistributedSetBuilder.
      *
      * @param <E> set element type
@@ -136,6 +145,30 @@
      */
     <V> AsyncDocumentTree<V> getDocumentTree(String name, Serializer serializer);
 
+     /** Returns a set backed instance of {@code AsyncConsistentMultimap} with
+     * the specified name.
+     *
+     * @param name the multimap name
+     * @param serializer serializer
+     * @param <K> key type
+     * @param <V> value type
+     * @return set backed {@code AsyncConsistentMultimap} instance
+     */
+    <K, V> AsyncConsistentMultimap<K, V> getAsyncSetMultimap(String name,
+                                                             Serializer serializer);
+
+    /**
+     * Returns an instance of {@code AsyncConsistentTreeMap} with the specified
+     * name.
+     *
+     * @param name the treemap name
+     * @param serializer serializer
+     * @param <V> value type
+     * @return set backed {@code AsyncConsistentTreeMap} instance
+     */
+    <V> AsyncConsistentTreeMap<V> getAsyncTreeMap(String name,
+                                                  Serializer serializer);
+
     /**
      * Returns an instance of {@code Topic} with specified name.
      *
diff --git a/core/api/src/test/java/org/onosproject/store/service/StorageServiceAdapter.java b/core/api/src/test/java/org/onosproject/store/service/StorageServiceAdapter.java
index 29dd72d..c44d3c7 100644
--- a/core/api/src/test/java/org/onosproject/store/service/StorageServiceAdapter.java
+++ b/core/api/src/test/java/org/onosproject/store/service/StorageServiceAdapter.java
@@ -65,11 +65,23 @@
     }
 
     @Override
+    public <K, V> AsyncConsistentMultimap<K, V> getAsyncSetMultimap(
+            String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
     public <T> Topic<T> getTopic(String name, Serializer serializer) {
         return null;
     }
 
     @Override
+    public <V> AsyncConsistentTreeMap<V> getAsyncTreeMap(
+            String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
     public <V> ConsistentTreeMapBuilder<V> consistentTreeMapBuilder() {
         return null;
     }
@@ -78,4 +90,8 @@
     public <V> AsyncDocumentTree<V> getDocumentTree(String name, Serializer serializer) {
         return null;
     }
+    @Override
+    public <K, V> ConsistentMultimapBuilder<K, V> consistentMultimapBuilder() {
+        return null;
+    }
 }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentMultimapBuilder.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentMultimapBuilder.java
new file mode 100644
index 0000000..976862b
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentMultimapBuilder.java
@@ -0,0 +1,47 @@
+/*
+ * 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.store.primitives.DistributedPrimitiveCreator;
+import org.onosproject.store.service.AsyncConsistentMultimap;
+import org.onosproject.store.service.ConsistentMultimap;
+import org.onosproject.store.service.ConsistentMultimapBuilder;
+
+/**
+ * Default {@link AsyncConsistentMultimap} builder.
+ */
+public class DefaultConsistentMultimapBuilder<K, V>
+        extends ConsistentMultimapBuilder<K, V> {
+
+    private final DistributedPrimitiveCreator primitiveCreator;
+
+    public DefaultConsistentMultimapBuilder(
+            DistributedPrimitiveCreator primitiveCreator) {
+        this.primitiveCreator = primitiveCreator;
+    }
+
+    @Override
+    public AsyncConsistentMultimap<K, V> buildMultimap() {
+        return primitiveCreator.newAsyncConsistentSetMultimap(
+                name(), serializer());
+    }
+
+    @Override
+    public ConsistentMultimap<K, V> build() {
+        return buildMultimap().asMultimap();
+    }
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentTreeMapBuilder.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentTreeMapBuilder.java
index 2aa906a..65a364e 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentTreeMapBuilder.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DefaultConsistentTreeMapBuilder.java
@@ -35,7 +35,8 @@
 
     @Override
     public AsyncConsistentTreeMap<V> buildTreeMap() {
-        return primitiveCreator.newAsyncConsistentTreeMap(name(), serializer());
+        return primitiveCreator.newAsyncConsistentTreeMap(name(),
+                                                          serializer());
     }
 
     @Override
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DelegatingAsyncConsistentMultimap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DelegatingAsyncConsistentMultimap.java
new file mode 100644
index 0000000..a425c32
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DelegatingAsyncConsistentMultimap.java
@@ -0,0 +1,184 @@
+/*
+ * Copyright 2016-present 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 com.google.common.base.MoreObjects;
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Multiset;
+import org.onosproject.store.service.AsyncConsistentMultimap;
+import org.onosproject.store.service.Versioned;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Objects;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.function.Consumer;
+
+/**
+ * {@code AsyncConsistentMultimap} that merely delegates control to
+ * another AsyncConsistentMultimap.
+ *
+ * @param <K> key type
+ * @param <V> value type
+ */
+public class DelegatingAsyncConsistentMultimap<K, V>
+        implements AsyncConsistentMultimap<K, V> {
+
+    private final AsyncConsistentMultimap<K, V> delegateMap;
+
+    public DelegatingAsyncConsistentMultimap(
+            AsyncConsistentMultimap<K, V> delegateMap) {
+        this.delegateMap = Preconditions.checkNotNull(delegateMap);
+    }
+
+    @Override
+    public String name() {
+        return delegateMap.name();
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        return delegateMap.size();
+    }
+
+    @Override
+    public CompletableFuture<Boolean> isEmpty() {
+        return delegateMap.isEmpty();
+    }
+
+    @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<Boolean> containsEntry(K key, V value) {
+        return delegateMap.containsEntry(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> put(K key, V value) {
+        return delegateMap.put(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        return delegateMap.remove(key, value);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> removeAll(
+            K key, Collection<? extends V> values) {
+        return delegateMap.removeAll(key, values);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>>
+        removeAll(K key) {
+        return delegateMap.removeAll(key);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> putAll(
+            K key, Collection<? extends V> values) {
+        return delegateMap.putAll(key, values);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>>
+        replaceValues(K key, Collection<V> values) {
+        return delegateMap.replaceValues(key, values);
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return delegateMap.clear();
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>> get(K key) {
+        return delegateMap.get(key);
+    }
+
+    @Override
+    public CompletableFuture<Set<K>> keySet() {
+        return delegateMap.keySet();
+    }
+
+    @Override
+    public CompletableFuture<Multiset<K>> keys() {
+        return delegateMap.keys();
+    }
+
+    @Override
+    public CompletableFuture<Multiset<V>> values() {
+        return delegateMap.values();
+    }
+
+    @Override
+    public CompletableFuture<Collection<Map.Entry<K, V>>> entries() {
+        return delegateMap.entries();
+    }
+
+    @Override
+    public CompletableFuture<Map<K, Collection<V>>> asMap() {
+        return delegateMap.asMap();
+    }
+
+    @Override
+    public void addStatusChangeListener(Consumer<Status> listener) {
+        delegateMap.addStatusChangeListener(listener);
+    }
+
+    @Override
+    public void removeStatusChangeListener(Consumer<Status> listener) {
+        delegateMap.removeStatusChangeListener(listener);
+    }
+
+    @Override
+    public Collection<Consumer<Status>> statusChangeListeners() {
+        return delegateMap.statusChangeListeners();
+    }
+
+    @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 DelegatingAsyncConsistentMultimap) {
+            DelegatingAsyncConsistentMultimap<K, V> that =
+                    (DelegatingAsyncConsistentMultimap) other;
+            return this.delegateMap.equals(that.delegateMap);
+        }
+        return false;
+    }
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DistributedPrimitives.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DistributedPrimitives.java
index 83af62d..520b9a6 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DistributedPrimitives.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DistributedPrimitives.java
@@ -18,6 +18,7 @@
 import java.util.function.Function;
 
 import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncConsistentMultimap;
 import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AsyncDistributedSet;
 
@@ -121,4 +122,39 @@
                                                        valueEncoder,
                                                        valueDecoder);
     }
+
+    /**
+     * Creates an instance of {@code AsyncConsistentMultimap} that transforms
+     * operations inputs and applies them to corresponding operation in a
+     * differently typed map and returns the output after reverse transforming
+     * it.
+     *
+     * @param multimap backing multimap
+     * @param keyEncoder transformer for key type of returned map to key type
+     *                   of input map
+     * @param keyDecoder transformer for key type of input map to key type of
+     *                   returned map
+     * @param valueEncoder transformer for value type of returned map to value
+     *                     type of input map
+     * @param valueDecoder transformer for value type of input map to value
+     *                     type of returned map
+     * @param <K1> returned map key type
+     * @param <K2> input map key type
+     * @param <V1> returned map value type
+     * @param <V2> input map key type
+     * @return new map
+     */
+    public static <K1, V1, K2, V2> AsyncConsistentMultimap<K1, V1>
+    newTranscodingMultimap(AsyncConsistentMultimap<K2, V2> multimap,
+                           Function<K1, K2> keyEncoder,
+                           Function<K2, K1> keyDecoder,
+                           Function<V1, V2> valueEncoder,
+                           Function<V2, V1> valueDecoder) {
+        return new TranscodingAsyncConsistentMultimap<>(multimap,
+                                                        keyEncoder,
+                                                        keyDecoder,
+                                                        valueDecoder,
+                                                        valueEncoder);
+    }
+
 }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
index b36906c..78447a8 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
@@ -27,6 +27,7 @@
 import org.onosproject.store.service.AsyncAtomicCounter;
 import org.onosproject.store.service.AsyncAtomicValue;
 import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncConsistentMultimap;
 import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AsyncDistributedSet;
 import org.onosproject.store.service.AsyncDocumentTree;
@@ -76,6 +77,13 @@
     }
 
     @Override
+    public <K, V> AsyncConsistentMultimap<K, V> newAsyncConsistentSetMultimap(
+            String name, Serializer serializer) {
+        return getCreator(name).newAsyncConsistentSetMultimap(name,
+                                                              serializer);
+    }
+
+    @Override
     public <E> AsyncDistributedSet<E> newAsyncDistributedSet(String name, Serializer serializer) {
         return DistributedPrimitives.newSetFromMap(newAsyncConsistentMap(name, serializer));
     }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StorageManager.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StorageManager.java
index 4d9c1a6..e2820a2 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StorageManager.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StorageManager.java
@@ -44,10 +44,13 @@
 import org.onosproject.store.service.AsyncAtomicValue;
 import org.onosproject.store.service.AsyncConsistentMap;
 import org.onosproject.store.service.AsyncDocumentTree;
+import org.onosproject.store.service.AsyncConsistentMultimap;
+import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AtomicCounterBuilder;
 import org.onosproject.store.service.AtomicValueBuilder;
 import org.onosproject.store.service.ConsistentMap;
 import org.onosproject.store.service.ConsistentMapBuilder;
+import org.onosproject.store.service.ConsistentMultimapBuilder;
 import org.onosproject.store.service.ConsistentTreeMapBuilder;
 import org.onosproject.store.service.DistributedSetBuilder;
 import org.onosproject.store.service.DocumentTreeBuilder;
@@ -146,6 +149,13 @@
     }
 
     @Override
+    public <K, V> ConsistentMultimapBuilder<K, V> consistentMultimapBuilder() {
+        checkPermission(STORAGE_WRITE);
+        return new DefaultConsistentMultimapBuilder<K, V>(
+                federatedPrimitiveCreator);
+    }
+
+    @Override
     public <E> DistributedSetBuilder<E> setBuilder() {
         checkPermission(STORAGE_WRITE);
         return new DefaultDistributedSetBuilder<>(() -> this.<E, Boolean>consistentMapBuilder());
@@ -194,6 +204,22 @@
     }
 
     @Override
+    public <K, V> AsyncConsistentMultimap<K, V> getAsyncSetMultimap(
+            String name, Serializer serializer) {
+        checkPermission(STORAGE_WRITE);
+        return federatedPrimitiveCreator.newAsyncConsistentSetMultimap(name,
+                                                                serializer);
+    }
+
+    @Override
+    public <V> AsyncConsistentTreeMap<V> getAsyncTreeMap(
+            String name, Serializer serializer) {
+        checkPermission(STORAGE_WRITE);
+        return federatedPrimitiveCreator.newAsyncConsistentTreeMap(name,
+                                                                   serializer);
+    }
+
+    @Override
     public List<MapInfo> getMapInfo() {
         return listMapInfo(federatedPrimitiveCreator);
     }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java
index b123ee0..b320a95 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/StoragePartitionClient.java
@@ -39,6 +39,7 @@
 import org.onlab.util.HexString;
 import org.onosproject.store.primitives.DistributedPrimitiveCreator;
 import org.onosproject.store.primitives.resources.impl.AtomixConsistentMap;
+import org.onosproject.store.primitives.resources.impl.AtomixConsistentSetMultimap;
 import org.onosproject.store.primitives.resources.impl.AtomixConsistentTreeMap;
 import org.onosproject.store.primitives.resources.impl.AtomixCounter;
 import org.onosproject.store.primitives.resources.impl.AtomixDocumentTree;
@@ -48,6 +49,7 @@
 import org.onosproject.store.service.AsyncAtomicCounter;
 import org.onosproject.store.service.AsyncAtomicValue;
 import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncConsistentMultimap;
 import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AsyncDistributedSet;
 import org.onosproject.store.service.AsyncDocumentTree;
@@ -154,7 +156,7 @@
             atomixConsistentTreeMap.statusChangeListeners()
                     .forEach(listener -> listener.accept(mapper.apply(state)));
         };
-            resourceClient.client().onStateChange(statusListener);
+        resourceClient.client().onStateChange(statusListener);
         AsyncConsistentTreeMap<byte[]> rawMap =
                 new DelegatingAsyncConsistentTreeMap<byte[]>(atomixConsistentTreeMap) {
                     @Override
@@ -171,6 +173,38 @@
     }
 
     @Override
+    public <K, V> AsyncConsistentMultimap<K, V> newAsyncConsistentSetMultimap(
+            String name, Serializer serializer) {
+        AtomixConsistentSetMultimap atomixConsistentSetMultimap =
+                client.getResource(name, AtomixConsistentSetMultimap.class)
+                        .join();
+        Consumer<State> statusListener = state -> {
+            atomixConsistentSetMultimap.statusChangeListeners()
+                    .forEach(listener -> listener.accept(mapper.apply(state)));
+        };
+        resourceClient.client().onStateChange(statusListener);
+        AsyncConsistentMultimap<String, byte[]> rawMap =
+                new DelegatingAsyncConsistentMultimap<String, byte[]>(
+                        atomixConsistentSetMultimap) {
+                    @Override
+                    public String name() {
+                        return super.name();
+                    }
+                };
+        AsyncConsistentMultimap<K, V> trancodedMap =
+                DistributedPrimitives.<K, V, String, byte[]>newTranscodingMultimap(
+                        rawMap,
+                        key -> HexString.toHexString(serializer.encode(key)),
+                        string -> serializer.decode(
+                                HexString.fromHexString(string)),
+                        value -> value == null ? null :
+                                serializer.encode(value),
+                        bytes -> serializer.decode(bytes));
+        return trancodedMap;
+
+    }
+
+    @Override
     public <E> AsyncDistributedSet<E> newAsyncDistributedSet(String name, Serializer serializer) {
         return DistributedPrimitives.newSetFromMap(this.<E, Boolean>newAsyncConsistentMap(name, serializer));
     }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/TranscodingAsyncConsistentMultimap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/TranscodingAsyncConsistentMultimap.java
new file mode 100644
index 0000000..e31653e
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/TranscodingAsyncConsistentMultimap.java
@@ -0,0 +1,293 @@
+/*
+ * 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 com.google.common.collect.ImmutableMultiset;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Multiset;
+import org.onlab.util.Tools;
+import org.onosproject.store.service.AsyncConsistentMultimap;
+import org.onosproject.store.service.Versioned;
+
+import java.util.Collection;
+import java.util.EnumSet;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.function.BiConsumer;
+import java.util.function.BinaryOperator;
+import java.util.function.Consumer;
+import java.util.function.Function;
+import java.util.function.Supplier;
+import java.util.stream.Collector;
+import java.util.stream.Collectors;
+
+/**
+ * An {@link AsyncConsistentMultimap} that maps its operation to operations to
+ * a differently typed {@link AsyncConsistentMultimap} by transcoding operation
+ * inputs and outputs while maintaining version numbers.
+ *
+ * @param <K2> key type of other map
+ * @param <V2> value type of other map
+ * @param <K1> key type of this map
+ * @param <V1> value type of this map
+ */
+public class TranscodingAsyncConsistentMultimap<K1, V1, K2, V2>
+        implements AsyncConsistentMultimap<K1, V1> {
+
+    private final AsyncConsistentMultimap<K2, V2> backingMap;
+    private final Function<K1, K2> keyEncoder;
+    private final Function<K2, K1> keyDecoder;
+    private final Function<V2, V1> valueDecoder;
+    private final Function<V1, V2> valueEncoder;
+    private final Function<? extends Versioned<V2>,
+            ? extends Versioned<V1>> versionedValueTransform;
+    private final Function<Versioned<Collection<? extends V2>>,
+            Versioned<Collection<? extends V1>>> versionedValueCollectionDecode;
+    private final Function<Collection<? extends V1>, Collection<V2>>
+            valueCollectionEncode;
+
+     public TranscodingAsyncConsistentMultimap(
+            AsyncConsistentMultimap<K2, V2> backingMap,
+            Function<K1, K2> keyEncoder,
+            Function<K2, K1> keyDecoder,
+            Function<V2, V1> valueDecoder,
+            Function<V1, V2> valueEncoder) {
+        this.backingMap = backingMap;
+        this.keyEncoder = k -> k == null ? null : keyEncoder.apply(k);
+        this.keyDecoder = k -> k == null ? null : keyDecoder.apply(k);
+        this.valueDecoder = v -> v == null ? null : valueDecoder.apply(v);
+        this.valueEncoder = v -> v == null ? null : valueEncoder.apply(v);
+        this.versionedValueTransform = v -> v == null ? null :
+                v.map(valueDecoder);
+        this.versionedValueCollectionDecode = v -> v == null ? null :
+                new Versioned<>(
+                        v.value()
+                                .stream()
+                                .map(valueDecoder)
+                                .collect(Collectors.toSet()),
+                        v.version(),
+                        v.creationTime());
+         this.valueCollectionEncode = v -> v == null ? null :
+                 v.stream().map(valueEncoder).collect(Collectors.toSet());
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        return backingMap.size();
+    }
+
+    @Override
+    public CompletableFuture<Boolean> isEmpty() {
+        return backingMap.isEmpty();
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsKey(K1 key) {
+        try {
+            return backingMap.containsKey(keyEncoder.apply(key));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsValue(V1 value) {
+        try {
+            return backingMap.containsValue(valueEncoder.apply(value));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsEntry(K1 key, V1 value) {
+        try {
+            return backingMap.containsEntry(keyEncoder.apply(key),
+                                            valueEncoder.apply(value));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Boolean> put(K1 key, V1 value) {
+        try {
+            return backingMap.put(keyEncoder.apply(key),
+                                  valueEncoder.apply(value));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K1 key, V1 value) {
+        try {
+            return backingMap.remove(keyEncoder.apply(key), valueEncoder
+                    .apply(value));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Boolean> removeAll(
+            K1 key, Collection<? extends V1> values) {
+        try {
+            return backingMap.removeAll(
+                    keyEncoder.apply(key),
+                    values.stream().map(valueEncoder).collect(
+                            Collectors.toSet()));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V1>>>
+    removeAll(K1 key) {
+        try {
+            return backingMap.removeAll(keyEncoder.apply(key))
+                    .thenApply(versionedValueCollectionDecode);
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Boolean>
+    putAll(K1 key, Collection<? extends V1> values) {
+        try {
+            return backingMap.putAll(keyEncoder.apply(key),
+                                     valueCollectionEncode.apply(values));
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V1>>>
+    replaceValues(K1 key, Collection<V1> values) {
+        try {
+            return backingMap.replaceValues(keyEncoder.apply(key),
+                                     valueCollectionEncode.apply(values))
+                    .thenApply(versionedValueCollectionDecode);
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return backingMap.clear();
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V1>>> get(K1 key) {
+        try {
+            return backingMap.get(keyEncoder.apply(key))
+                    .thenApply(versionedValueCollectionDecode);
+        } catch (Exception e) {
+            return Tools.exceptionalFuture(e);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Set<K1>> keySet() {
+        return backingMap.keySet().thenApply(s -> s.stream()
+                .map(keyDecoder)
+                .collect(Collectors.toSet()));
+    }
+
+    @Override
+    public CompletableFuture<Multiset<K1>> keys() {
+        return backingMap.keys().thenApply(s -> s.stream().map(keyDecoder)
+                .collect(new MultisetCollector<>()));
+    }
+
+    @Override
+    public CompletableFuture<Multiset<V1>> values() {
+        return backingMap.values().thenApply(s -> s.stream().map(valueDecoder)
+                .collect(new MultisetCollector<>()));
+    }
+
+    @Override
+    public CompletableFuture<Collection<Map.Entry<K1, V1>>> entries() {
+        return backingMap.entries().thenApply(s -> s.stream()
+        .map(e -> Maps.immutableEntry(keyDecoder.apply(e.getKey()),
+                                      valueDecoder.apply(e.getValue())))
+                .collect(Collectors.toSet()));
+    }
+
+    @Override
+    public CompletableFuture<Map<K1, Collection<V1>>> asMap() {
+        throw new UnsupportedOperationException("Unsupported operation.");
+    }
+
+    @Override
+    public String name() {
+        return backingMap.name();
+    }
+
+    @Override
+    public void addStatusChangeListener(Consumer<Status> listener) {
+        backingMap.addStatusChangeListener(listener);
+    }
+
+    @Override
+    public void removeStatusChangeListener(Consumer<Status> listener) {
+        backingMap.removeStatusChangeListener(listener);
+    }
+
+    @Override
+    public Collection<Consumer<Status>> statusChangeListeners() {
+        return backingMap.statusChangeListeners();
+    }
+
+    private class MultisetCollector<T> implements Collector<T,
+            ImmutableMultiset.Builder<T>,
+            Multiset<T>> {
+
+        @Override
+        public Supplier<ImmutableMultiset.Builder<T>> supplier() {
+            return ImmutableMultiset::builder;
+        }
+
+        @Override
+        public BiConsumer<ImmutableMultiset.Builder<T>, T> accumulator() {
+            return ((builder, t) -> builder.add(t));
+        }
+
+        @Override
+        public BinaryOperator<ImmutableMultiset.Builder<T>> combiner() {
+            return (a, b) -> {
+                a.addAll(b.build());
+                return a;
+            };
+        }
+
+        @Override
+        public Function<ImmutableMultiset.Builder<T>, Multiset<T>> finisher() {
+            return ImmutableMultiset.Builder::build;
+        }
+
+        @Override
+        public Set<Characteristics> characteristics() {
+            return EnumSet.of(Characteristics.UNORDERED);
+        }
+    }
+}
diff --git a/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/StorageServiceAdapter.java b/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/StorageServiceAdapter.java
index 4f60b06..b77faac 100644
--- a/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/StorageServiceAdapter.java
+++ b/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/StorageServiceAdapter.java
@@ -16,9 +16,12 @@
 package org.onosproject.pcelabelstore.util;
 
 import org.onosproject.store.service.AsyncDocumentTree;
+import org.onosproject.store.service.AsyncConsistentMultimap;
+import org.onosproject.store.service.AsyncConsistentTreeMap;
 import org.onosproject.store.service.AtomicCounterBuilder;
 import org.onosproject.store.service.AtomicValueBuilder;
 import org.onosproject.store.service.ConsistentMapBuilder;
+import org.onosproject.store.service.ConsistentMultimapBuilder;
 import org.onosproject.store.service.ConsistentTreeMapBuilder;
 import org.onosproject.store.service.DistributedSetBuilder;
 import org.onosproject.store.service.DocumentTreeBuilder;
@@ -80,6 +83,16 @@
     }
 
     @Override
+    public <K, V> AsyncConsistentMultimap<K, V> getAsyncSetMultimap(String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
+    public <V> AsyncConsistentTreeMap<V> getAsyncTreeMap(String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
     public <T> Topic<T> getTopic(String name, Serializer serializer) {
         // TODO Auto-generated method stub
         return null;
@@ -95,4 +108,7 @@
     public <V> AsyncDocumentTree<V> getDocumentTree(String name, Serializer serializer) {
         return null;
     }
+    public <K, V> ConsistentMultimapBuilder<K, V> consistentMultimapBuilder() {
+        return null;
+    }
 }
diff --git a/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/TestStorageService.java b/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/TestStorageService.java
index a7fbf1d..4f35be2 100644
--- a/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/TestStorageService.java
+++ b/protocols/pcep/ctl/src/test/java/org/onosproject/pcelabelstore/util/TestStorageService.java
@@ -15,12 +15,20 @@
  */
 package org.onosproject.pcelabelstore.util;
 
+import org.onosproject.store.service.AsyncConsistentMultimap;
+import org.onosproject.store.service.AsyncConsistentTreeMap;
+import org.onosproject.store.service.AsyncDocumentTree;
 import org.onosproject.store.service.AtomicCounterBuilder;
 import org.onosproject.store.service.AtomicValueBuilder;
 import org.onosproject.store.service.ConsistentMapBuilder;
+import org.onosproject.store.service.ConsistentMultimapBuilder;
 import org.onosproject.store.service.DistributedSetBuilder;
 import org.onosproject.store.service.EventuallyConsistentMapBuilder;
+import org.onosproject.store.service.LeaderElectorBuilder;
+import org.onosproject.store.service.Serializer;
+import org.onosproject.store.service.Topic;
 import org.onosproject.store.service.TransactionContextBuilder;
+import org.onosproject.store.service.WorkQueue;
 
 public class TestStorageService extends StorageServiceAdapter {
 
@@ -36,6 +44,11 @@
     }
 
     @Override
+    public <K, V> ConsistentMultimapBuilder<K, V> consistentMultimapBuilder() {
+        return null;
+    }
+
+    @Override
     public <E> DistributedSetBuilder<E> setBuilder() {
         return TestDistributedSet.builder();
     }
@@ -54,4 +67,34 @@
     public TransactionContextBuilder transactionContextBuilder() {
         throw new UnsupportedOperationException("transactionContextBuilder");
     }
+
+    @Override
+    public LeaderElectorBuilder leaderElectorBuilder() {
+        return null;
+    }
+
+    @Override
+    public <E> WorkQueue<E> getWorkQueue(String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
+    public <K, V> AsyncConsistentMultimap<K, V> getAsyncSetMultimap(String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
+    public <V> AsyncConsistentTreeMap<V> getAsyncTreeMap(String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
+    public <T> Topic<T> getTopic(String name, Serializer serializer) {
+        return null;
+    }
+
+    @Override
+    public <V> AsyncDocumentTree<V> getDocumentTree(String name, Serializer serializer) {
+        return null;
+    }
 }