diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentMap.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentMap.java
new file mode 100644
index 0000000..cf90ab0
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentMap.java
@@ -0,0 +1,200 @@
+package org.onosproject.store.service;
+
+import java.util.Collection;
+import java.util.List;
+import java.util.Set;
+import java.util.Map.Entry;
+
+/**
+ * A distributed, strongly consistent map.
+ * <p>
+ * This map offers strong read-after-update (where update == create/update/delete)
+ * consistency. All operations to the map are serialized and applied in a consistent
+ * manner.
+ * <p>
+ * The stronger consistency comes at the expense of availability in
+ * the event of a network partition. A network partition can be either due to
+ * a temporary disruption in network connectivity between participating nodes
+ * or due to a node being temporarily down.
+ * </p><p>
+ * All values stored in this map are versioned and the API supports optimistic
+ * concurrency by allowing conditional updates that take into consideration
+ * the version or value that was previously read.
+ * </p><p>
+ * The map also supports atomic batch updates (transactions). One can provide a list
+ * of updates to be applied atomically if and only if all the operations are guaranteed
+ * to succeed i.e. all their preconditions are met. For example, the precondition
+ * for a putIfAbsent API call is absence of a mapping for the key. Similarly, the
+ * precondition for a conditional replace operation is the presence of an expected
+ * version or value
+ * </p><p>
+ * This map does not allow null values. All methods can throw a ConsistentMapException
+ * (which extends RuntimeException) to indicate failures.
+ *
+ */
+public interface ConsistentMap<K, V> {
+
+    /**
+     * Returns the number of entries in the map.
+     *
+     * @return map size.
+     */
+    int size();
+
+    /**
+     * Returns true if the map is empty.
+     *
+     * @return true if map has no entries, false otherwise.
+     */
+    boolean isEmpty();
+
+    /**
+     * Returns true if this map contains a mapping for the specified key.
+     *
+     * @param key key
+     * @return true if map contains key, false otherwise.
+     */
+    boolean containsKey(K key);
+
+    /**
+     * Returns true if this map contains the specified value.
+     *
+     * @param value value
+     * @return true if map contains value, false otherwise.
+     */
+    boolean containsValue(V value);
+
+    /**
+     * Returns the value (and version) to which the specified key is mapped, or null if this
+     * map contains no mapping for the key.
+     *
+     * @param key the key whose associated value (and version) is to be returned
+     * @return the value (and version) to which the specified key is mapped, or null if
+     * this map contains no mapping for the key
+     */
+    Versioned<V> get(K key);
+
+    /**
+     * Associates the specified value with the specified key in this map (optional operation).
+     * If the map previously contained a mapping for the key, the old value is replaced by the
+     * specified value.
+     *
+     * @param key key with which the specified value is to be associated
+     * @param value value to be associated with the specified key
+     * @return the previous value (and version) associated with key, or null if there was
+     * no mapping for key.
+     */
+    Versioned<V> put(K key, V value);
+
+    /**
+     * Removes the mapping for a key from this map if it is present (optional operation).
+     *
+     * @param key key whose value is to be removed from the map
+     * @return the value (and version) to which this map previously associated the key,
+     * or null if the map contained no mapping for the key.
+     */
+    Versioned<V> remove(K key);
+
+    /**
+     * Removes all of the mappings from this map (optional operation).
+     * The map will be empty after this call returns.
+     */
+    void clear();
+
+    /**
+     * Returns a Set view of the keys contained in this map.
+     * This method differs from the behavior of java.util.Map.keySet() in that
+     * what is returned is a unmodifiable snapshot view of the keys in the ConsistentMap.
+     * Attempts to modify the returned set, whether direct or via its iterator,
+     * result in an UnsupportedOperationException.
+     *
+     * @return a set of the keys contained in this map
+     */
+    Set<K> keySet();
+
+    /**
+     * Returns the collection of values (and associated versions) contained in this map.
+     * This method differs from the behavior of java.util.Map.values() in that
+     * what is returned is a unmodifiable snapshot view of the values in the ConsistentMap.
+     * Attempts to modify the returned collection, whether direct or via its iterator,
+     * result in an UnsupportedOperationException.
+     *
+     * @return a collection of the values (and associated versions) contained in this map
+     */
+    Collection<Versioned<V>> values();
+
+    /**
+     * Returns the set of entries contained in this map.
+     * This method differs from the behavior of java.util.Map.entrySet() in that
+     * what is returned is a unmodifiable snapshot view of the entries in the ConsistentMap.
+     * Attempts to modify the returned set, whether direct or via its iterator,
+     * result in an UnsupportedOperationException.
+     *
+     * @return set of entries contained in this map.
+     */
+    Set<Entry<K, Versioned<V>>> entrySet();
+
+    /**
+     * If the specified key is not already associated with a value
+     * associates it with the given value and returns null, else returns the current value.
+     *
+     * @param key key with which the specified value is to be associated
+     * @param value value to be associated with the specified key
+     * @return the previous value associated with the specified key or null
+     * if key does not already mapped to a value.
+     */
+    Versioned<V> putIfAbsent(K key, V value);
+
+    /**
+     * Removes the entry for the specified key only if it is currently
+     * mapped to the specified value.
+     *
+     * @param key key with which the specified value is associated
+     * @param value value expected to be associated with the specified key
+     * @return true if the value was removed
+     */
+    boolean remove(K key, V value);
+
+    /**
+     * Removes the entry for the specified key only if its current
+     * version in the map is equal to the specified version.
+     *
+     * @param key key with which the specified version is associated
+     * @param version version expected to be associated with the specified key
+     * @return true if the value was removed
+     */
+    boolean remove(K key, long version);
+
+    /**
+     * Replaces the entry for the specified key only if currently mapped
+     * to the specified value.
+     *
+     * @param key key with which the specified value is associated
+     * @param oldValue value expected to be associated with the specified key
+     * @param newValue value to be associated with the specified key
+     * @return true if the value was replaced
+     */
+    boolean replace(K key, V oldValue, V newValue);
+
+    /**
+     * Replaces the entry for the specified key only if it is currently mapped to the
+     * specified version.
+     *
+     * @param key key key with which the specified value is associated
+     * @param oldVersion version expected to be associated with the specified key
+     * @param newValue value to be associated with the specified key
+     * @return true if the value was replaced
+     */
+    boolean replace(K key, long oldVersion, V newValue);
+
+    /**
+     * Atomically apply the specified list of updates to the map.
+     * If any of the updates cannot be applied due to a precondition
+     * violation, none of the updates will be applied and the state of
+     * the map remains unaltered.
+     *
+     * @param updates list of updates to apply atomically.
+     * @return true if the map was updated.
+     */
+    boolean batchUpdate(List<UpdateOperation<K, V>> updates);
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/ConsistentMapException.java b/core/api/src/main/java/org/onosproject/store/service/ConsistentMapException.java
new file mode 100644
index 0000000..2ba4dee
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/ConsistentMapException.java
@@ -0,0 +1,26 @@
+package org.onosproject.store.service;
+
+/**
+ * Top level exception for ConsistentMap failures.
+ */
+@SuppressWarnings("serial")
+public class ConsistentMapException extends RuntimeException {
+    public ConsistentMapException() {
+    }
+
+    public ConsistentMapException(Throwable t) {
+        super(t);
+    }
+
+    /**
+     * ConsistentMap operation timeout.
+     */
+    public static class Timeout extends ConsistentMapException {
+    }
+
+    /**
+     * ConsistentMap operation interrupted.
+     */
+    public static class Interrupted extends ConsistentMapException {
+    }
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/Serializer.java b/core/api/src/main/java/org/onosproject/store/service/Serializer.java
new file mode 100644
index 0000000..f43090f
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/Serializer.java
@@ -0,0 +1,22 @@
+package org.onosproject.store.service;
+
+/**
+ * Interface for serialization for store artifacts.
+ */
+public interface Serializer {
+    /**
+     * Serialize the specified object.
+     * @param object object to serialize.
+     * @return serialized bytes.
+     * @param <T> encoded type
+     */
+    <T> byte[] encode(T object);
+
+    /**
+     * Deserialize the specified bytes.
+     * @param bytes byte array to deserialize.
+     * @return deserialized object.
+     * @param <T> decoded type
+     */
+    <T> T decode(byte[] bytes);
+}
\ No newline at end of file
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
new file mode 100644
index 0000000..cfae271
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/StorageService.java
@@ -0,0 +1,27 @@
+package org.onosproject.store.service;
+
+/**
+ * Storage service.
+ * <p>
+ * This service provides operations for creating key-value stores.
+ * One can chose to create key-value stores with varying properties such
+ * as strongly consistent vs eventually consistent, durable vs volatile.
+ * <p>
+ * Various store implementations should leverage the data structures provided
+ * by this service
+ */
+public interface StorageService {
+
+    /**
+     * Creates a ConsistentMap.
+     *
+     * @param name map name
+     * @param serializer serializer to use for serializing keys and values.
+     * @return consistent map.
+     * @param <K> key type
+     * @param <V> value type
+     */
+    <K, V> ConsistentMap<K , V> createConsistentMap(String name, Serializer serializer);
+
+    // TODO: add API for creating Eventually Consistent Map.
+}
\ No newline at end of file
diff --git a/core/api/src/main/java/org/onosproject/store/service/UpdateOperation.java b/core/api/src/main/java/org/onosproject/store/service/UpdateOperation.java
new file mode 100644
index 0000000..224efbe
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/UpdateOperation.java
@@ -0,0 +1,182 @@
+package org.onosproject.store.service;
+
+import static com.google.common.base.Preconditions.*;
+
+import com.google.common.base.MoreObjects;
+
+/**
+ * Database update operation.
+ *
+ * @param <K> key type.
+ * @param <V> value type.
+ */
+public class UpdateOperation<K, V> {
+
+    /**
+     * Type of database update operation.
+     */
+    public static enum Type {
+        PUT,
+        PUT_IF_ABSENT,
+        PUT_IF_VERSION_MATCH,
+        PUT_IF_VALUE_MATCH,
+        REMOVE,
+        REMOVE_IF_VERSION_MATCH,
+        REMOVE_IF_VALUE_MATCH,
+    }
+
+    private Type type;
+    private String tableName;
+    private K key;
+    private V value;
+    private V currentValue;
+    private long currentVersion = -1;
+
+    /**
+     * Returns the type of update operation.
+     * @return type of update.
+     */
+    public Type type() {
+        return type;
+    }
+
+    /**
+     * Returns the tableName being updated.
+     * @return table name.
+     */
+    public String tableName() {
+        return tableName;
+    }
+
+    /**
+     * Returns the item key being updated.
+     * @return item key
+     */
+    public K key() {
+        return key;
+    }
+
+    /**
+     * Returns the new value.
+     * @return item's target value.
+     */
+    public V value() {
+        return value;
+    }
+
+    /**
+     * Returns the expected current value in the database value for the key.
+     * @return current value in database.
+     */
+    public V currentValue() {
+        return currentValue;
+    }
+
+    /**
+     * Returns the expected current version in the database for the key.
+     * @return expected version.
+     */
+    public long currentVersion() {
+        return currentVersion;
+    }
+
+    @Override
+    public String toString() {
+        return MoreObjects.toStringHelper(this)
+            .add("type", type)
+            .add("tableName", tableName)
+            .add("key", key)
+            .add("value", value)
+            .add("currentValue", currentValue)
+            .add("currentVersion", currentVersion)
+            .toString();
+    }
+
+    /**
+     * Creates a new builder instance.
+     * @param <K> key type.
+     * @param <V> value type.
+     *
+     * @return builder.
+     */
+    public static <K, V> Builder<K, V> newBuilder() {
+        return new Builder<>();
+    }
+
+    /**
+     * UpdatOperation builder.
+     *
+     * @param <K> key type.
+     * @param <V> value type.
+     */
+    public static final class Builder<K, V> {
+
+        private UpdateOperation<K, V> operation = new UpdateOperation<>();
+
+        public UpdateOperation<K, V> build() {
+            validateInputs();
+            return operation;
+        }
+
+        public Builder<K, V> withType(Type type) {
+            operation.type = checkNotNull(type, "type cannot be null");
+            return this;
+        }
+
+        public Builder<K, V> withTableName(String tableName) {
+            operation.tableName = checkNotNull(tableName, "tableName cannot be null");
+            return this;
+        }
+
+        public Builder<K, V> withKey(K key) {
+            operation.key = checkNotNull(key, "key cannot be null");
+            return this;
+        }
+
+        public Builder<K, V> withCurrentValue(V value) {
+            operation.currentValue = checkNotNull(value, "currentValue cannot be null");
+            return this;
+        }
+
+        public Builder<K, V> withValue(V value) {
+            operation.value = checkNotNull(value, "value cannot be null");
+            return this;
+        }
+
+        public Builder<K, V> withCurrentVersion(long version) {
+            checkArgument(version >= 0, "version cannot be negative");
+            operation.currentVersion = version;
+            return this;
+        }
+
+        private void validateInputs() {
+            checkNotNull(operation.type, "type must be specified");
+            checkNotNull(operation.tableName, "table name must be specified");
+            checkNotNull(operation.key, "key must be specified");
+            switch (operation.type) {
+            case PUT:
+            case PUT_IF_ABSENT:
+                checkNotNull(operation.value, "value must be specified.");
+                break;
+            case PUT_IF_VERSION_MATCH:
+                checkNotNull(operation.value, "value must be specified.");
+                checkState(operation.currentVersion >= 0, "current version must be specified");
+                break;
+            case PUT_IF_VALUE_MATCH:
+                checkNotNull(operation.value, "value must be specified.");
+                checkNotNull(operation.currentValue, "currentValue must be specified.");
+                break;
+            case REMOVE:
+                break;
+            case REMOVE_IF_VERSION_MATCH:
+                checkState(operation.currentVersion >= 0, "current version must be specified");
+                break;
+            case REMOVE_IF_VALUE_MATCH:
+                checkNotNull(operation.currentValue, "currentValue must be specified.");
+                break;
+            default:
+                throw new IllegalStateException("Unknown operation type");
+            }
+        }
+    }
+}
diff --git a/core/api/src/main/java/org/onosproject/store/service/Versioned.java b/core/api/src/main/java/org/onosproject/store/service/Versioned.java
new file mode 100644
index 0000000..2026437
--- /dev/null
+++ b/core/api/src/main/java/org/onosproject/store/service/Versioned.java
@@ -0,0 +1,50 @@
+package org.onosproject.store.service;
+
+import com.google.common.base.MoreObjects;
+
+/**
+ * Versioned value.
+ *
+ * @param <V> value type.
+ */
+public class Versioned<V> {
+
+    private final V value;
+    private final long version;
+
+    /**
+     * Constructs a new versioned value.
+     * @param value value
+     * @param version version
+     */
+    public Versioned(V value, long version) {
+        this.value = value;
+        this.version = version;
+    }
+
+    /**
+     * Returns the value.
+     *
+     * @return value.
+     */
+    public V value() {
+        return value;
+    }
+
+    /**
+     * Returns the version.
+     *
+     * @return version
+     */
+    public long version() {
+        return version;
+    }
+
+    @Override
+    public String toString() {
+        return MoreObjects.toStringHelper(this)
+            .add("value", value)
+            .add("version", version)
+            .toString();
+    }
+}