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);
+        }
+    }
+}