diff --git a/core/api/src/main/java/org/onosproject/store/service/ClockService.java b/core/api/src/main/java/org/onosproject/store/service/ClockService.java
new file mode 100644
index 0000000..a0de0a9
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/ClockService.java
@@ -0,0 +1,35 @@
+/*
+ * Copyright 2015 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.Timestamp;
+
+/**
+ * Clock service that can generate timestamps based off of two input objects.
+ * Implementations are free to only take one or none of the objects into account
+ * when generating timestamps.
+ */
+public interface ClockService<T, U> {
+
+    /**
+     * Gets a new timestamp for the given objects.
+     *
+     * @param object1 First object to use when generating timestamps
+     * @param object2 Second object to use when generating timestamps
+     * @return the new timestamp
+     */
+    public Timestamp getTimestamp(T object1, U object2);
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMap.java b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMap.java
new file mode 100644
index 0000000..58a81cc
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMap.java
@@ -0,0 +1,197 @@
+/*
+ * Copyright 2015 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 java.util.Collection;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * A distributed, eventually consistent map.
+ * <p>
+ * This map does not offer read after writes consistency. Operations are
+ * serialized via the timestamps issued by the clock service. If two updates
+ * are in conflict, the update with the more recent timestamp will endure.
+ * </p><p>
+ * The interface is mostly similar to {@link java.util.Map} with some minor
+ * semantic changes and the addition of a listener framework (because the map
+ * can be mutated by clients on other instances, not only through the local Java
+ * API).
+ * </p><p>
+ * Clients are expected to register an
+ * {@link EventuallyConsistentMapListener} if they
+ * are interested in receiving notifications of update to the map.
+ * </p><p>
+ * Null values are not allowed in this map.
+ * </p>
+ */
+public interface EventuallyConsistentMap<K, V> {
+
+    /**
+     * Returns the number of key-value mappings in this map.
+     *
+     * @return number of key-value mappings
+     */
+    public int size();
+
+    /**
+     * Returns true if this map is empty.
+     *
+     * @return true if this map is empty, otherwise false
+     */
+    public boolean isEmpty();
+
+    /**
+     * Returns true if the map contains a mapping for the specified key.
+     *
+     * @param key the key to check if this map contains
+     * @return true if this map has a mapping for the key, otherwise false
+     */
+    public boolean containsKey(K key);
+
+    /**
+     * Returns true if the map contains a mapping from any key to the specified
+     * value.
+     *
+     * @param value the value to check if this map has a mapping for
+     * @return true if this map has a mapping to this value, otherwise false
+     */
+    public boolean containsValue(V value);
+
+    /**
+     * Returns the value mapped to the specified key.
+     *
+     * @param key the key to look up in this map
+     * @return the value mapped to the key, or null if no mapping is found
+     */
+    public V get(K key);
+
+    /**
+     * Associates the specified value to the specified key in this map.
+     * <p>
+     * Note: this differs from the specification of {@link java.util.Map}
+     * because it does not return the previous value associated with the key.
+     * Clients are expected to register an
+     * {@link EventuallyConsistentMapListener} if
+     * they are interested in receiving notification of updates to the map.
+     * </p><p>
+     * Null values are not allowed in the map.
+     * </p>
+     *
+     * @param key the key to add a mapping for in this map
+     * @param value the value to associate with the key in this map
+     */
+    public void put(K key, V value);
+
+    /**
+     * Removes the mapping associated with the specified key from the map.
+     * <p>
+     * Note: this differs from the specification of {@link java.util.Map}
+     * because it does not return the previous value associated with the key.
+     * Clients are expected to register an
+     * {@link EventuallyConsistentMapListener} if
+     * they are interested in receiving notification of updates to the map.
+     * </p>
+     *
+     * @param key the key to remove the mapping for
+     */
+    public void remove(K key);
+
+    /**
+     * Removes the given key-value mapping from the map, if it exists.
+     * <p>
+     * This actually means remove any values up to and including the timestamp
+     * given by {@link org.onosproject.store.service.ClockService#getTimestamp(Object, Object)}.
+     * Any mappings that produce an earlier timestamp than this given key-value
+     * pair will be removed, and any mappings that produce a later timestamp
+     * will supersede this remove.
+     * </p><p>
+     * Note: this differs from the specification of {@link java.util.Map}
+     * because it does not return a boolean indication whether a value was removed.
+     * Clients are expected to register an
+     * {@link EventuallyConsistentMapListener} if
+     * they are interested in receiving notification of updates to the map.
+     * </p>
+     *
+     * @param key the key to remove the mapping for
+     * @param value the value mapped to the key
+     */
+    public void remove(K key, V value);
+
+    /**
+     * Adds mappings for all key-value pairs in the specified map to this map.
+     * <p>
+     * This will be more efficient in communication than calling individual put
+     * operations.
+     * </p>
+     *
+     * @param m a map of values to add to this map
+     */
+    public void putAll(Map<? extends K, ? extends V> m);
+
+    /**
+     * Removes all mappings from this map.
+     */
+    public void clear();
+
+    /**
+     * Returns a set of the keys in this map. Changes to the set are not
+     * reflected back to the map.
+     *
+     * @return set of keys in the map
+     */
+    public Set<K> keySet();
+
+    /**
+     * Returns a collections of values in this map. Changes to the collection
+     * are not reflected back to the map.
+     *
+     * @return collection of values in the map
+     */
+    public Collection<V> values();
+
+    /**
+     * Returns a set of mappings contained in this map. Changes to the set are
+     * not reflected back to the map.
+     *
+     * @return set of key-value mappings in this map
+     */
+    public Set<Map.Entry<K, V>> entrySet();
+
+    /**
+     * Adds the specified listener to the map which will be notified whenever
+     * the mappings in the map are changed.
+     *
+     * @param listener listener to register for events
+     */
+    public void addListener(EventuallyConsistentMapListener<K, V> listener);
+
+    /**
+     * Removes the specified listener from the map such that it will no longer
+     * receive change notifications.
+     *
+     * @param listener listener to deregister for events
+     */
+    public void removeListener(EventuallyConsistentMapListener<K, V> listener);
+
+    /**
+     * Shuts down the map and breaks communication between different instances.
+     * This allows the map objects to be cleaned up and garbage collected.
+     * Calls to any methods on the map subsequent to calling destroy() will
+     * throw a {@link java.lang.RuntimeException}.
+     */
+    public void destroy();
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapBuilder.java b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapBuilder.java
new file mode 100644
index 0000000..779c329
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapBuilder.java
@@ -0,0 +1,176 @@
+/*
+ * Copyright 2015 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.onlab.util.KryoNamespace;
+import org.onosproject.cluster.NodeId;
+
+import java.util.Collection;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.ScheduledExecutorService;
+import java.util.concurrent.TimeUnit;
+import java.util.function.BiFunction;
+
+/**
+ * Builder for eventually consistent maps.
+ *
+ * @param <K> type for map keys
+ * @param <V> type for map values
+ */
+public interface EventuallyConsistentMapBuilder<K, V> {
+
+    /**
+     * Sets the name of the map.
+     * <p>
+     * Each map is identified by a string map name. EventuallyConsistentMapImpl
+     * objects in different JVMs that use the same map name will form a
+     * distributed map across JVMs (provided the cluster service is aware of
+     * both nodes).
+     * </p>
+     * <p>
+     * Note: This is a mandatory parameter.
+     * </p>
+     *
+     * @param name name of the map
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withName(String name);
+
+    /**
+     * Sets a serializer builder that can be used to create a serializer that
+     * can serialize both the keys and values put into the map. The serializer
+     * builder should be pre-populated with any classes that will be put into
+     * the map.
+     * <p>
+     * Note: This is a mandatory parameter.
+     * </p>
+     *
+     * @param serializerBuilder serializer builder
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withSerializer(
+            KryoNamespace.Builder serializerBuilder);
+
+    /**
+     * Sets the clock service to use for generating timestamps for map updates.
+     * <p>
+     * The client must provide an {@link org.onosproject.store.service.ClockService}
+     * which can generate timestamps for a given key. The clock service is free
+     * to generate timestamps however it wishes, however these timestamps will
+     * be used to serialize updates to the map so they must be strict enough
+     * to ensure updates are properly ordered for the use case (i.e. in some
+     * cases wallclock time will suffice, whereas in other cases logical time
+     * will be necessary).
+     * </p>
+     * <p>
+     * Note: This is a mandatory parameter.
+     * </p>
+     *
+     * @param clockService clock service
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withClockService(
+            ClockService<K, V> clockService);
+
+    /**
+     * Sets the executor to use for processing events coming in from peers.
+     *
+     * @param executor event executor
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withEventExecutor(
+            ExecutorService executor);
+
+    /**
+     * Sets the executor to use for sending events to peers.
+     *
+     * @param executor event executor
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withCommunicationExecutor(
+            ExecutorService executor);
+
+    /**
+     * Sets the executor to use for background anti-entropy tasks.
+     *
+     * @param executor event executor
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withBackgroundExecutor(
+            ScheduledExecutorService executor);
+
+    /**
+     * Sets a function that can determine which peers to replicate updates to.
+     * <p>
+     * The default function replicates to all nodes.
+     * </p>
+     *
+     * @param peerUpdateFunction function that takes a K, V input and returns
+     *                           a collection of NodeIds to replicate the event
+     *                           to
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withPeerUpdateFunction(
+            BiFunction<K, V, Collection<NodeId>> peerUpdateFunction);
+
+    /**
+     * Prevents this map from writing tombstones of items that have been
+     * removed. This may result in zombie items reappearing after they have
+     * been removed.
+     * <p>
+     * The default behavior is tombstones are enabled.
+     * </p>
+     *
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withTombstonesDisabled();
+
+    /**
+     * Configures how often to run the anti-entropy background task.
+     * <p>
+     * The default anti-entropy period is 5 seconds.
+     * </p>
+     *
+     * @param period anti-entropy period
+     * @param unit time unit for the period
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withAntiEntropyPeriod(
+            long period, TimeUnit unit);
+
+    /**
+     * Configure anti-entropy to converge faster at the cost of doing more work
+     * for each anti-entropy cycle. Suited to maps with low update rate where
+     * convergence time is more important than throughput.
+     * <p>
+     * The default behavior is to do less anti-entropy work at the cost of
+     * slower convergence.
+     * </p>
+     *
+     * @return this EventuallyConsistentMapBuilder
+     */
+    public EventuallyConsistentMapBuilder<K, V> withFasterConvergence();
+
+    /**
+     * Builds an eventually consistent map based on the configuration options
+     * supplied to this builder.
+     *
+     * @return new eventually consistent map
+     * @throws java.lang.RuntimeException if a mandatory parameter is missing
+     */
+    public EventuallyConsistentMap<K, V> build();
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapEvent.java b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapEvent.java
new file mode 100644
index 0000000..8f63325
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapEvent.java
@@ -0,0 +1,101 @@
+/*
+ * Copyright 2015 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 com.google.common.base.MoreObjects;
+
+import java.util.Objects;
+
+/**
+ * Event object signalling that the map was modified.
+ */
+public class EventuallyConsistentMapEvent<K, V> {
+
+    public enum Type {
+        PUT,
+        REMOVE
+    }
+
+    private final Type type;
+    private final K key;
+    private final V value;
+
+    /**
+     * Creates a new event object.
+     *
+     * @param type the type of the event
+     * @param key the key the event concerns
+     * @param value the value related to the key, or null for remove events
+     */
+    public EventuallyConsistentMapEvent(Type type, K key, V value) {
+        this.type = type;
+        this.key = key;
+        this.value = value;
+    }
+
+    /**
+     * Returns the type of the event.
+     *
+     * @return the type of the event
+     */
+    public Type type() {
+        return type;
+    }
+
+    /**
+     * Returns the key this event concerns.
+     *
+     * @return the key
+     */
+    public K key() {
+        return key;
+    }
+
+    /**
+     * Returns the value associated with this event.
+     *
+     * @return the value, or null if the event was REMOVE
+     */
+    public V value() {
+        return value;
+    }
+
+    @Override
+    public boolean equals(Object o) {
+        if (!(o instanceof EventuallyConsistentMapEvent)) {
+            return false;
+        }
+
+        EventuallyConsistentMapEvent that = (EventuallyConsistentMapEvent) o;
+        return Objects.equals(this.type, that.type) &&
+                Objects.equals(this.key, that.key) &&
+                Objects.equals(this.value, that.value);
+    }
+
+    @Override
+    public int hashCode() {
+        return Objects.hash(type, key, value);
+    }
+
+    @Override
+    public String toString() {
+        return MoreObjects.toStringHelper(getClass())
+                .add("type", type)
+                .add("key", key)
+                .add("value", value)
+                .toString();
+    }
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapListener.java b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapListener.java
new file mode 100644
index 0000000..686255e
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/EventuallyConsistentMapListener.java
@@ -0,0 +1,30 @@
+/*
+ * Copyright 2015 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;
+
+/**
+ * Listener interested in receiving modification events for an
+ * EventuallyConsistentMap.
+ */
+public interface EventuallyConsistentMapListener<K, V> {
+
+    /**
+     * Reacts to the specified event.
+     *
+     * @param event the event
+     */
+    public void event(EventuallyConsistentMapEvent<K, V> event);
+}
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 7e447cc..a59e376 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
@@ -30,6 +30,7 @@
 
     /**
      * Creates a ConsistentMap.
+     *
      * @param name map name
      * @param serializer serializer to use for serializing keys and values
      * @return consistent map.
@@ -40,6 +41,7 @@
 
     /**
      * Creates a AsyncConsistentMap.
+     *
      * @param name map name
      * @param serializer serializer to use for serializing keys and values
      * @return async consistent map
@@ -50,7 +52,18 @@
 
     /**
      * Creates a new transaction context.
+     *
      * @return transaction context
      */
     TransactionContext createTransactionContext();
-}
\ No newline at end of file
+
+    /**
+     * Creates a new EventuallyConsistentMapBuilder.
+     *
+     * @param <K> key type
+     * @param <V> value type
+     * @return builder for an eventually consistent map
+     */
+    <K, V> EventuallyConsistentMapBuilder<K, V> eventuallyConsistentMapBuilder();
+
+}