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
new file mode 100644
index 0000000..2577ca0
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/DistributedPrimitives.java
@@ -0,0 +1,103 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onosproject.store.primitives.impl;
+
+import java.util.function.Function;
+
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncDistributedSet;
+
+/**
+ * Misc utilities for working with {@code DistributedPrimitive}s.
+ */
+public final class DistributedPrimitives {
+
+    private DistributedPrimitives() {}
+
+    /**
+     * Creates an instance of {@code AsyncDistributedSet} that is backed by a {@code AsyncConsistentMap}.
+     *
+     * @param map backing map
+     * @return set
+     * @param <E> set element type
+     */
+    public static <E> AsyncDistributedSet<E> newSetFromMap(AsyncConsistentMap<E, Boolean> map) {
+        return new DefaultAsyncDistributedSet<>(map, map.name(), true);
+    }
+
+    /**
+     * Creates an instance of {@code AsyncConsistentMap} that records metrics for all its operations.
+     *
+     * @param map map whose operations are to be metered
+     * @return metered map
+     * @param <K> map key type
+     * @param <V> map value type
+     */
+    public static <K, V> AsyncConsistentMap<K, V> newMeteredMap(AsyncConsistentMap<K, V> map) {
+        return new MeteredAsyncConsistentMap<>(map);
+    }
+
+    /**
+     * Creates an instance of {@code AsyncConsistentMap} that caches entries on get.
+     *
+     * @param map backing map
+     * @return caching map
+     * @param <K> map key type
+     * @param <V> map value type
+     */
+    public static <K, V> AsyncConsistentMap<K, V> newCachingMap(AsyncConsistentMap<K, V> map) {
+        return new CachingAsyncConsistentMap<>(map);
+    }
+
+    /**
+     * Creates an instance of {@code AsyncConsistentMap} that disallows updates.
+     *
+     * @param map backing map
+     * @return unmodifiable map
+     * @param <K> map key type
+     * @param <V> map value type
+     */
+    public static <K, V> AsyncConsistentMap<K, V> newUnmodifiableMap(AsyncConsistentMap<K, V> map) {
+        return new UnmodifiableAsyncConsistentMap<>(map);
+    }
+
+    /**
+     * Creates an instance of {@code AsyncConsistentMap} that transforms operations inputs and applies them
+     * to corresponding operation in a different typed map and returns the output after reverse transforming it.
+     *
+     * @param map backing map
+     * @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> AsyncConsistentMap<K1, V1> newTranscodingMap(AsyncConsistentMap<K2, V2> map,
+            Function<K1, K2> keyEncoder,
+            Function<K2, K1> keyDecoder,
+            Function<V1, V2> valueEncoder,
+            Function<V2, V1> valueDecoder) {
+        return new TranscodingAsyncConsistentMap<K1, V1, K2, V2>(map,
+                keyEncoder,
+                keyDecoder,
+                valueEncoder,
+                valueDecoder);
+    }
+}
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
new file mode 100644
index 0000000..20c2a98
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/FederatedDistributedPrimitiveCreator.java
@@ -0,0 +1,106 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onosproject.store.primitives.impl;
+
+import static com.google.common.base.Preconditions.checkNotNull;
+
+import java.util.List;
+import java.util.Map;
+import java.util.TreeMap;
+
+import org.apache.commons.lang.StringUtils;
+import org.onlab.util.Tools;
+import org.onosproject.cluster.PartitionId;
+import org.onosproject.store.primitives.DistributedPrimitiveCreator;
+import org.onosproject.store.service.AsyncAtomicCounter;
+import org.onosproject.store.service.AsyncAtomicValue;
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.AsyncDistributedSet;
+import org.onosproject.store.service.AsyncLeaderElector;
+import org.onosproject.store.service.DistributedQueue;
+import org.onosproject.store.service.Serializer;
+
+import com.google.common.collect.Lists;
+import com.google.common.collect.Maps;
+import com.google.common.hash.HashCode;
+import com.google.common.hash.Hashing;
+import com.google.common.primitives.Bytes;
+
+/**
+ * {@code DistributedPrimitiveCreator} that federates responsibility for creating
+ * distributed primitives to a collection of other {@link DistributedPrimitiveCreator creators}.
+ */
+public class FederatedDistributedPrimitiveCreator implements DistributedPrimitiveCreator {
+
+    private final TreeMap<PartitionId, DistributedPrimitiveCreator> members;
+    private final List<PartitionId> sortedMemberPartitionIds;
+
+    public FederatedDistributedPrimitiveCreator(Map<PartitionId, DistributedPrimitiveCreator> members) {
+        this.members = Maps.newTreeMap();
+        this.members.putAll(checkNotNull(members));
+        this.sortedMemberPartitionIds = Lists.newArrayList(members.keySet());
+    }
+
+    @Override
+    public <K, V> AsyncConsistentMap<K, V> newAsyncConsistentMap(String name, Serializer serializer) {
+        checkNotNull(name);
+        checkNotNull(serializer);
+        Map<PartitionId, AsyncConsistentMap<K, V>> maps =
+                Maps.transformValues(members,
+                                     partition -> partition.newAsyncConsistentMap(name, serializer));
+        Hasher<K> hasher = key -> {
+            long hashCode = HashCode.fromBytes(Bytes.ensureCapacity(serializer.encode(key), 8, 0)).asLong();
+            return sortedMemberPartitionIds.get(Hashing.consistentHash(hashCode, members.size()));
+        };
+        return new PartitionedAsyncConsistentMap<>(name, maps, hasher);
+    }
+
+    @Override
+    public <E> AsyncDistributedSet<E> newAsyncDistributedSet(String name, Serializer serializer) {
+        return DistributedPrimitives.newSetFromMap(newAsyncConsistentMap(name, serializer));
+    }
+
+    @Override
+    public AsyncAtomicCounter newAsyncCounter(String name) {
+        return getCreator(name).newAsyncCounter(name);
+    }
+
+    @Override
+    public <V> AsyncAtomicValue<V> newAsyncAtomicValue(String name, Serializer serializer) {
+        return getCreator(name).newAsyncAtomicValue(name, serializer);
+    }
+
+    @Override
+    public <E> DistributedQueue<E> newDistributedQueue(String name, Serializer serializer) {
+        return getCreator(name).newDistributedQueue(name, serializer);
+    }
+
+    @Override
+    public AsyncLeaderElector newAsyncLeaderElector(String name) {
+        return getCreator(name).newAsyncLeaderElector(name);
+    }
+
+    /**
+     * Returns the {@code DistributedPrimitiveCreator} to use for hosting a primitive.
+     * @param name primitive name
+     * @return primitive creator
+     */
+    private DistributedPrimitiveCreator getCreator(String name) {
+        long hashCode = HashCode.fromBytes(Tools.getBytesUtf8(StringUtils.leftPad(name, 8))).asLong();
+        int index = Hashing.consistentHash(hashCode, members.size());
+        return members.get(sortedMemberPartitionIds.get(index));
+    }
+}
diff --git a/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/TranscodingAsyncConsistentMap.java b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/TranscodingAsyncConsistentMap.java
new file mode 100644
index 0000000..c6dd578
--- /dev/null
+++ b/core/store/primitives/src/main/java/org/onosproject/store/primitives/impl/TranscodingAsyncConsistentMap.java
@@ -0,0 +1,215 @@
+/*
+ * Copyright 2016 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *     http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.onosproject.store.primitives.impl;
+
+import java.util.Collection;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+import java.util.concurrent.CompletableFuture;
+import java.util.function.BiFunction;
+import java.util.function.Function;
+import java.util.function.Predicate;
+import java.util.stream.Collectors;
+
+import org.onosproject.store.service.AsyncConsistentMap;
+import org.onosproject.store.service.MapEvent;
+import org.onosproject.store.service.MapEventListener;
+import org.onosproject.store.service.Versioned;
+
+import com.google.common.collect.Maps;
+
+/**
+ * An {@code AsyncConsistentMap} that maps its operations to operations on a
+ * differently typed {@code AsyncConsistentMap} by transcoding operation inputs and outputs.
+ *
+ * @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 TranscodingAsyncConsistentMap<K1, V1, K2, V2> implements AsyncConsistentMap<K1, V1> {
+
+    private final AsyncConsistentMap<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<Versioned<V2>, Versioned<V1>> versionedValueTransform;
+    private final Map<MapEventListener<K1, V1>, InternalBackingMapEventListener> listeners =
+            Maps.newIdentityHashMap();
+
+    public TranscodingAsyncConsistentMap(AsyncConsistentMap<K2, V2> backingMap,
+                                   Function<K1, K2> keyEncoder,
+                                   Function<K2, K1> keyDecoder,
+                                   Function<V1, V2> valueEncoder,
+                                   Function<V2, V1> valueDecoder) {
+        this.backingMap = backingMap;
+        this.keyEncoder = k -> k == null ? null : keyEncoder.apply(k);
+        this.keyDecoder = keyDecoder;
+        this.valueEncoder = v -> v == null ? null : valueEncoder.apply(v);
+        this.valueDecoder = valueDecoder;
+        this.versionedValueTransform = v -> v == null ? null : v.map(valueDecoder);
+    }
+
+    @Override
+    public String name() {
+        return backingMap.name();
+    }
+
+    @Override
+    public CompletableFuture<Integer> size() {
+        return backingMap.size();
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsKey(K1 key) {
+        return backingMap.containsKey(keyEncoder.apply(key));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> containsValue(V1 value) {
+        return backingMap.containsValue(valueEncoder.apply(value));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> get(K1 key) {
+        return backingMap.get(keyEncoder.apply(key)).thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> computeIf(K1 key,
+            Predicate<? super V1> condition,
+            BiFunction<? super K1, ? super V1, ? extends V1> remappingFunction) {
+        return backingMap.computeIf(keyEncoder.apply(key),
+                                    v -> condition.test(valueDecoder.apply(v)),
+                                    (k, v) -> valueEncoder.apply(remappingFunction.apply(keyDecoder.apply(k),
+                                                                                         valueDecoder.apply(v))))
+                         .thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> put(K1 key, V1 value) {
+        return backingMap.put(keyEncoder.apply(key), valueEncoder.apply(value))
+                         .thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> putAndGet(K1 key, V1 value) {
+        return backingMap.putAndGet(keyEncoder.apply(key), valueEncoder.apply(value))
+                         .thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> remove(K1 key) {
+        return backingMap.remove(keyEncoder.apply(key)).thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Void> clear() {
+        return backingMap.clear();
+    }
+
+    @Override
+    public CompletableFuture<Set<K1>> keySet() {
+        return backingMap.keySet()
+                         .thenApply(s -> s.stream().map(keyDecoder).collect(Collectors.toSet()));
+    }
+
+    @Override
+    public CompletableFuture<Collection<Versioned<V1>>> values() {
+        return backingMap.values()
+                .thenApply(c -> c.stream().map(versionedValueTransform).collect(Collectors.toList()));
+    }
+
+    @Override
+    public CompletableFuture<Set<Entry<K1, Versioned<V1>>>> entrySet() {
+        return backingMap.entrySet()
+                         .thenApply(s -> s.stream()
+                                          .map(e -> Maps.immutableEntry(keyDecoder.apply(e.getKey()),
+                                                                        versionedValueTransform.apply(e.getValue())))
+                                          .collect(Collectors.toSet()));
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> putIfAbsent(K1 key, V1 value) {
+        return backingMap.putIfAbsent(keyEncoder.apply(key), valueEncoder.apply(value))
+                         .thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K1 key, V1 value) {
+        return backingMap.remove(keyEncoder.apply(key), valueEncoder.apply(value));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> remove(K1 key, long version) {
+        return backingMap.remove(keyEncoder.apply(key), version);
+    }
+
+    @Override
+    public CompletableFuture<Versioned<V1>> replace(K1 key, V1 value) {
+        return backingMap.replace(keyEncoder.apply(key), valueEncoder.apply(value))
+                .thenApply(versionedValueTransform);
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K1 key, V1 oldValue, V1 newValue) {
+        return backingMap.replace(keyEncoder.apply(key), valueEncoder.apply(oldValue), valueEncoder.apply(newValue));
+    }
+
+    @Override
+    public CompletableFuture<Boolean> replace(K1 key, long oldVersion, V1 newValue) {
+        return backingMap.replace(keyEncoder.apply(key), oldVersion, valueEncoder.apply(newValue));
+    }
+
+    @Override
+    public CompletableFuture<Void> addListener(MapEventListener<K1, V1> listener) {
+        synchronized (listeners) {
+            InternalBackingMapEventListener backingMapListener =
+                    listeners.computeIfAbsent(listener, k -> new InternalBackingMapEventListener(listener));
+            return backingMap.addListener(backingMapListener);
+        }
+    }
+
+    @Override
+    public CompletableFuture<Void> removeListener(MapEventListener<K1, V1> listener) {
+        InternalBackingMapEventListener backingMapListener = listeners.remove(listener);
+        if (backingMapListener != null) {
+            return backingMap.removeListener(backingMapListener);
+        } else {
+            return CompletableFuture.completedFuture(null);
+        }
+    }
+
+    private class InternalBackingMapEventListener implements MapEventListener<K2, V2> {
+
+        private final MapEventListener<K1, V1> listener;
+
+        InternalBackingMapEventListener(MapEventListener<K1, V1> listener) {
+            this.listener = listener;
+        }
+
+        @Override
+        public void event(MapEvent<K2, V2> event) {
+            listener.event(new MapEvent<K1, V1>(event.name(),
+                    keyDecoder.apply(event.key()),
+                    event.newValue().map(valueDecoder),
+                    event.oldValue().map(valueDecoder)));
+        }
+    }
+}