diff --git a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentMultimap.java b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentMultimap.java
index c14b187..51f0934 100644
--- a/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentMultimap.java
+++ b/core/api/src/main/java/org/onosproject/store/primitives/DefaultConsistentMultimap.java
@@ -111,11 +111,21 @@
     }
 
     @Override
+    public boolean removeAll(Map<K, Collection<? extends V>> mapping) {
+        return complete(asyncMultimap.removeAll(mapping));
+    }
+
+    @Override
     public boolean putAll(K key, Collection<? extends V> values) {
         return complete(asyncMultimap.putAll(key, values));
     }
 
     @Override
+    public boolean putAll(Map<K, Collection<? extends V>> mapping) {
+        return complete(asyncMultimap.putAll(mapping));
+    }
+
+    @Override
     public Versioned<Collection<? extends V>> replaceValues(
             K key, Collection<V> values) {
         return complete(asyncMultimap.replaceValues(key, values));
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 94943b8..b86845e 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
@@ -166,6 +166,19 @@
     CompletableFuture<Versioned<Collection<? extends V>>> removeAll(K key);
 
     /**
+     * Removes the set of key-value pairs with the specified key and values if they
+     * exist. In implementations that allow duplicates each instance of a key
+     * will remove one matching entry, which one is not defined. Equivalent to
+     * repeated calls to {@code remove()} for each key value pair but more
+     * efficient.
+     *
+     * @param mapping the keys-values to be removed
+     * @return a future whose value will be true if the map changes because of
+     * this call, false otherwise.
+     */
+    CompletableFuture<Boolean> removeAll(Map<K, Collection<? extends V>> mapping);
+
+    /**
      * Adds the set of key-value pairs of the specified key with each of the
      * values in the iterable if each key-value pair does not already exist,
      * if the pair does exist the behavior is implementation specific.
@@ -180,6 +193,18 @@
                                       Collection<? extends V> values);
 
     /**
+     * Adds the set of key-value pairs of the specified mapping with each of
+     * the values in the iterable if each key-value pair does not already exist,
+     * if the pair does exist the behavior is implementation specific.
+     * (Same as repeated puts but with efficiency gains.)
+     *
+     * @param mapping the keys-values to be added
+     * @return a future whose value will be true if any change in the map
+     * results from this call, false otherwise
+     */
+    CompletableFuture<Boolean> putAll(Map<K, Collection<? extends V>> mapping);
+
+    /**
      * Stores all the values in values associated with the key specified,
      * removes all preexisting values and returns a collection of the removed
      * values which may be empty if the entry did not exist.
diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimap.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimap.java
index 99045a8..8aabca7 100644
--- a/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimap.java
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentMultimap.java
@@ -149,6 +149,18 @@
     Versioned<Collection<? extends V>> removeAll(K key);
 
     /**
+     * Removes the set of key-value pairs with the specified key and values if they
+     * exist. In implementations that allow duplicates each instance of a key
+     * will remove one matching entry, which one is not defined. Equivalent to
+     * repeated calls to {@code remove()} for each key value pair but more
+     * efficient.
+     *
+     * @param mapping the keys-values to be removed
+     * @return true if the map changes because of this call, false otherwise.
+     */
+    boolean removeAll(Map<K, Collection<? extends V>> mapping);
+
+    /**
      * Adds the set of key-value pairs of the specified key with each of the
      * values in the iterable if each key-value pair does not already exist,
      * if the pair does exist the behavior is implementation specific.
@@ -162,6 +174,18 @@
     boolean putAll(K key, Collection<? extends V> values);
 
     /**
+     * Adds the set of key-value pairs of the specified mapping with each of
+     * the values in the iterable if each key-value pair does not already exist,
+     * if the pair does exist the behavior is implementation specific.
+     * (Same as repeated puts but with efficiency gains.)
+     *
+     * @param mapping the keys-values to be added
+     * @return true if any change in the map results from this call,
+     * false otherwise
+     */
+    boolean putAll(Map<K, Collection<? extends V>> mapping);
+
+    /**
      * Stores all the values in values associated with the key specified,
      * removes all preexisting values and returns a collection of the removed
      * values which may be empty if the entry did not exist.
diff --git a/core/api/src/test/java/org/onosproject/store/primitives/DefaultConsistentMultimapTest.java b/core/api/src/test/java/org/onosproject/store/primitives/DefaultConsistentMultimapTest.java
new file mode 100644
index 0000000..61a175a
--- /dev/null
+++ b/core/api/src/test/java/org/onosproject/store/primitives/DefaultConsistentMultimapTest.java
@@ -0,0 +1,176 @@
+/*
+ * Copyright 2019-present Open Networking Foundation
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.store.primitives;
+
+import com.google.common.collect.HashMultimap;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Multimap;
+import org.junit.Test;
+import org.onosproject.store.service.AsyncConsistentMultimapAdapter;
+import org.onosproject.store.service.ConsistentMultimap;
+import org.onosproject.store.service.Versioned;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Map;
+import java.util.concurrent.CompletableFuture;
+
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.containsInAnyOrder;
+import static org.hamcrest.Matchers.is;
+
+/**
+ * Tests for DefaultConsistentMultiMap.
+ */
+public class DefaultConsistentMultimapTest {
+
+    private static final String KEY1 = "AAA";
+    private static final String VALUE1 = "111";
+    private static final String KEY2 = "BBB";
+    private static final String VALUE2 = "222";
+    private static final String KEY3 = "CCC";
+    private static final String VALUE3 = "333";
+    private static final String KEY4 = "DDD";
+    private static final String VALUE4 = "444";
+    private final List<String> allKeys = Lists.newArrayList(KEY1, KEY2,
+                                                            KEY3, KEY4);
+    private final List<String> allValues = Lists.newArrayList(VALUE1, VALUE2,
+                                                              VALUE3, VALUE4);
+
+    /**
+     * Tests the behavior of public APIs of the default consistent multi-map
+     * implementation.
+     */
+    @Test
+    public void testBehavior() {
+        // Initialize the map
+        Multimap<String, String> baseMap = HashMultimap.create();
+        AsyncConsistentMultimapMock<String, String> asyncMultiMap = new AsyncConsistentMultimapMock<>(baseMap);
+        ConsistentMultimap<String, String> newMap = new DefaultConsistentMultimap<>(asyncMultiMap, 69);
+
+        // Verify is empty
+        assertThat(newMap.size(), is(0));
+        assertThat(newMap.isEmpty(), is(true));
+
+        // Test multi put
+        Map<String, Collection<? extends String>> mapping = Maps.newHashMap();
+        // First build the mappings having each key a different mapping
+        allKeys.forEach(key -> {
+            switch (key) {
+                case KEY1:
+                    mapping.put(key, Lists.newArrayList(allValues.subList(0, 1)));
+                    break;
+                case KEY2:
+                    mapping.put(key, Lists.newArrayList(allValues.subList(0, 2)));
+                    break;
+                case KEY3:
+                    mapping.put(key, Lists.newArrayList(allValues.subList(0, 3)));
+                    break;
+                default:
+                    mapping.put(key, Lists.newArrayList(allValues.subList(0, 4)));
+                    break;
+            }
+        });
+        // Success
+        assertThat(newMap.putAll(mapping), is(true));
+        // Failure
+        assertThat(newMap.putAll(mapping), is(false));
+        // Verify operation
+        assertThat(newMap.size(), is(10));
+        assertThat(newMap.isEmpty(), is(false));
+        // verify mapping is ok
+
+        allKeys.forEach(key -> {
+            List<String> actual = Lists.newArrayList(Versioned.valueOrNull(newMap.get(key)));
+            switch (key) {
+                case KEY1:
+                    assertThat(actual, containsInAnyOrder(allValues.subList(0, 1).toArray()));
+                    break;
+                case KEY2:
+                    assertThat(actual, containsInAnyOrder(allValues.subList(0, 2).toArray()));
+                    break;
+                case KEY3:
+                    assertThat(actual, containsInAnyOrder(allValues.subList(0, 3).toArray()));
+                    break;
+                default:
+                    assertThat(actual, containsInAnyOrder(allValues.subList(0, 4).toArray()));
+                    break;
+            }
+        });
+        // Success
+        assertThat(newMap.removeAll(mapping), is(true));
+        // Failure
+        assertThat(newMap.removeAll(mapping), is(false));
+        // Verify operation
+        assertThat(newMap.size(), is(0));
+        assertThat(newMap.isEmpty(), is(true));
+    }
+
+    public static class AsyncConsistentMultimapMock<K, V> extends AsyncConsistentMultimapAdapter<K, V> {
+        private final Multimap<K, V> baseMap;
+        private static final int DEFAULT_CREATION_TIME = 0;
+        private static final int DEFAULT_VERSION = 0;
+
+        AsyncConsistentMultimapMock(Multimap<K, V> newBaseMap) {
+            baseMap = newBaseMap;
+        }
+
+        Versioned<Collection<? extends V>> makeVersioned(Collection<? extends V> v) {
+            return new Versioned<>(v, DEFAULT_VERSION, DEFAULT_CREATION_TIME);
+        }
+
+        @Override
+        public CompletableFuture<Integer> size() {
+            return CompletableFuture.completedFuture(baseMap.size());
+        }
+
+        @Override
+        public CompletableFuture<Boolean> isEmpty() {
+            return CompletableFuture.completedFuture(baseMap.isEmpty());
+        }
+
+        @Override
+        public CompletableFuture<Boolean> putAll(Map<K, Collection<? extends V>> mapping) {
+            CompletableFuture<Boolean> result = CompletableFuture.completedFuture(false);
+            for (Map.Entry<K, Collection<? extends V>> entry : mapping.entrySet()) {
+                if (baseMap.putAll(entry.getKey(), entry.getValue())) {
+                    result = CompletableFuture.completedFuture(true);
+                }
+            }
+            return result;
+        }
+
+        @Override
+        public CompletableFuture<Versioned<Collection<? extends V>>> get(K key) {
+            return CompletableFuture.completedFuture(makeVersioned(baseMap.get(key)));
+        }
+
+        @Override
+        public CompletableFuture<Boolean> removeAll(Map<K, Collection<? extends V>> mapping) {
+            CompletableFuture<Boolean> result = CompletableFuture.completedFuture(false);
+            for (Map.Entry<K, Collection<? extends V>> entry : mapping.entrySet()) {
+                for (V value : entry.getValue()) {
+                    if (baseMap.remove(entry.getKey(), value)) {
+                        result = CompletableFuture.completedFuture(true);
+                    }
+                }
+            }
+            return result;
+        }
+    }
+}
diff --git a/core/api/src/test/java/org/onosproject/store/service/AsyncConsistentMultimapAdapter.java b/core/api/src/test/java/org/onosproject/store/service/AsyncConsistentMultimapAdapter.java
new file mode 100644
index 0000000..4bb2618
--- /dev/null
+++ b/core/api/src/test/java/org/onosproject/store/service/AsyncConsistentMultimapAdapter.java
@@ -0,0 +1,205 @@
+/*
+ * Copyright 2019-present Open Networking Foundation
+ *
+ * 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 com.google.common.collect.Multiset;
+import org.onosproject.core.ApplicationId;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.concurrent.Executor;
+import java.util.function.Consumer;
+
+public class AsyncConsistentMultimapAdapter<K, V> implements AsyncConsistentMultimap<K, V> {
+
+    @Override
+    public String name() {
+        return null;
+    }
+
+    @Override
+    public Type primitiveType() {
+        return null;
+    }
+
+    @Override
+    public ApplicationId applicationId() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Void> destroy() {
+        return null;
+    }
+
+    @Override
+    public void addStatusChangeListener(Consumer<Status> listener) {
+
+    }
+
+    @Override
+    public void removeStatusChangeListener(Consumer<Status> listener) {
+
+    }
+
+    @Override
+    public Collection<Consumer<Status>> statusChangeListeners() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> isEmpty() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsKey(K key) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsValue(V value) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsEntry(K key, V value) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> put(K key, V value) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>> putAndGet(K key, V value) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K key, V value) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>> removeAndGet(K key, V value) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> removeAll(K key, Collection<? extends V> values) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>> removeAll(K key) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> removeAll(Map<K, Collection<? extends V>> mapping) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> putAll(K key, Collection<? extends V> values) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Boolean> putAll(Map<K, Collection<? extends V>> mapping) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>> replaceValues(K key, Collection<V> values) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Versioned<Collection<? extends V>>> get(K key) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Set<K>> keySet() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Multiset<K>> keys() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Multiset<V>> values() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Collection<Map.Entry<K, V>>> entries() {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Void> addListener(MultimapEventListener<K, V> listener) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Void> addListener(MultimapEventListener<K, V> listener, Executor executor) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Void> removeListener(MultimapEventListener<K, V> listener) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<Map<K, Collection<V>>> asMap() {
+        return null;
+    }
+
+    @Override
+    public ConsistentMultimap<K, V> asMultimap() {
+        return null;
+    }
+
+    @Override
+    public ConsistentMultimap<K, V> asMultimap(long timeoutMillis) {
+        return null;
+    }
+
+    @Override
+    public CompletableFuture<AsyncIterator<Map.Entry<K, V>>> iterator() {
+        return null;
+    }
+}
diff --git a/core/api/src/test/java/org/onosproject/store/service/TestConsistentMultimap.java b/core/api/src/test/java/org/onosproject/store/service/TestConsistentMultimap.java
index 08be2e4..f70d186 100644
--- a/core/api/src/test/java/org/onosproject/store/service/TestConsistentMultimap.java
+++ b/core/api/src/test/java/org/onosproject/store/service/TestConsistentMultimap.java
@@ -24,6 +24,7 @@
 import java.util.Set;
 import java.util.concurrent.Executor;
 import java.util.concurrent.atomic.AtomicLong;
+import java.util.stream.Collectors;
 
 /**
  * Implementation to test ConsistentMultimap. Very limited.
@@ -103,11 +104,42 @@
     }
 
     @Override
+    public boolean removeAll(Map<K, Collection<? extends V>> mapping) {
+        // Semantic is that any change in the map should return true
+        boolean result = false;
+        for (Map.Entry<K, Collection<? extends V>> entry : mapping.entrySet()) {
+            Collection<? extends Versioned<V>> versionedValues = entry.getValue().stream()
+                    .map(this::version)
+                    .collect(Collectors.toList());
+            for (Versioned<V> value : versionedValues) {
+                if (innermap.remove(entry.getKey(), value)) {
+                    result = true;
+                }
+            }
+        }
+        return result;
+    }
+
+    @Override
     public boolean putAll(K key, Collection<? extends V> values) {
         return false;
     }
 
     @Override
+    public boolean putAll(Map<K, Collection<? extends V>> mapping) {
+        // Semantic is that any change in the map should return true
+        boolean result = false;
+        for (Map.Entry<K, Collection<? extends V>> entry : mapping.entrySet()) {
+            Collection<? extends Versioned<V>> versionedValues = entry.getValue().stream()
+                    .map(this::version).collect(Collectors.toList());
+            if (innermap.putAll(entry.getKey(), versionedValues)) {
+                result = true;
+            }
+        }
+        return result;
+    }
+
+    @Override
     public Versioned<Collection<? extends V>> replaceValues(K key, Collection<V> values) {
         return null;
     }
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/atomix/primitives/impl/AtomixConsistentMultimap.java b/core/store/primitives/src/main/java/org/onosproject/store/atomix/primitives/impl/AtomixConsistentMultimap.java
index 96d7e8c..e444eb5 100644
--- a/core/store/primitives/src/main/java/org/onosproject/store/atomix/primitives/impl/AtomixConsistentMultimap.java
+++ b/core/store/primitives/src/main/java/org/onosproject/store/atomix/primitives/impl/AtomixConsistentMultimap.java
@@ -109,11 +109,21 @@
     }
 
     @Override
+    public CompletableFuture<Boolean> removeAll(Map<K, Collection<? extends V>> mapping) {
+        return adaptMapFuture(atomixMultimap.removeAll(mapping));
+    }
+
+    @Override
     public CompletableFuture<Boolean> putAll(K key, Collection<? extends V> values) {
         return adaptMapFuture(atomixMultimap.putAll(key, values));
     }
 
     @Override
+    public CompletableFuture<Boolean> putAll(Map<K, Collection<? extends V>> mapping) {
+        return adaptMapFuture(atomixMultimap.putAll(mapping));
+    }
+
+    @Override
     @SuppressWarnings("unchecked")
     public CompletableFuture<Versioned<Collection<? extends V>>> replaceValues(K key, Collection<V> values) {
         return adaptMapFuture(atomixMultimap.replaceValues(key, values).thenApply(this::toVersioned));