diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/AntiEntropyReply.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/AntiEntropyReply.java
index 94c20ea..9bc095e 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/AntiEntropyReply.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/AntiEntropyReply.java
@@ -18,10 +18,10 @@
  * Suggest to the sender about the more up-to-date data this node has,
  * and request for more recent data that the receiver has.
  */
-public class AntiEntropyReply<ID, VALUE> extends ClusterMessage {
+public class AntiEntropyReply<ID, V extends VersionedValue<?>> extends ClusterMessage {
 
     private final NodeId sender;
-    private final ImmutableMap<ID, VersionedValue<VALUE>> suggestion;
+    private final ImmutableMap<ID, V> suggestion;
     private final ImmutableSet<ID> request;
 
     /**
@@ -32,7 +32,7 @@
      * @param request Collection of identifiers
      */
     public AntiEntropyReply(NodeId sender,
-                            Map<ID, VersionedValue<VALUE>> suggestion,
+                            Map<ID, V> suggestion,
                             Set<ID> request) {
         super(AE_REPLY);
         this.sender = sender;
@@ -44,14 +44,34 @@
         return sender;
     }
 
-    public ImmutableMap<ID, VersionedValue<VALUE>> suggestion() {
+    /**
+     * Returns collection of values, which the recipient of this reply is likely
+     * to be missing or has outdated version.
+     *
+     * @return
+     */
+    public ImmutableMap<ID, V> suggestion() {
         return suggestion;
     }
 
+    /**
+     * Returns collection of identifier to request.
+     *
+     * @return collection of identifier to request
+     */
     public ImmutableSet<ID> request() {
         return request;
     }
 
+    /**
+     * Checks if reply contains any suggestion or request.
+     *
+     * @return true if nothing is suggested and requested
+     */
+    public boolean isEmpty() {
+        return suggestion.isEmpty() && request.isEmpty();
+    }
+
     // Default constructor for serializer
     protected AntiEntropyReply() {
         super(AE_REPLY);
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/DeviceAntiEntropyAdvertisement.java b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/DeviceAntiEntropyAdvertisement.java
new file mode 100644
index 0000000..301884c
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/DeviceAntiEntropyAdvertisement.java
@@ -0,0 +1,39 @@
+package org.onlab.onos.store.device.impl;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.Map;
+
+import org.onlab.onos.cluster.NodeId;
+import org.onlab.onos.net.Device;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.store.Timestamp;
+import org.onlab.onos.store.cluster.messaging.AntiEntropyAdvertisement;
+
+// TODO DeviceID needs to be changed to something like (ProviderID, DeviceID)
+// TODO: Handle Port as part of these messages, or separate messages for Ports?
+
+public class DeviceAntiEntropyAdvertisement
+    extends AntiEntropyAdvertisement<DeviceId> {
+
+
+    public DeviceAntiEntropyAdvertisement(NodeId sender,
+            Map<DeviceId, Timestamp> advertisement) {
+        super(sender, advertisement);
+    }
+
+    // May need to add ProviderID, etc.
+    public static DeviceAntiEntropyAdvertisement create(
+            NodeId self,
+            Collection<VersionedValue<Device>> localValues) {
+
+        Map<DeviceId, Timestamp> ads = new HashMap<>(localValues.size());
+        for (VersionedValue<Device> e : localValues) {
+            ads.put(e.entity().id(), e.timestamp());
+        }
+        return new DeviceAntiEntropyAdvertisement(self, ads);
+    }
+
+    // For serializer
+    protected DeviceAntiEntropyAdvertisement() {}
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/DeviceAntiEntropyReply.java b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/DeviceAntiEntropyReply.java
new file mode 100644
index 0000000..011713e
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/DeviceAntiEntropyReply.java
@@ -0,0 +1,102 @@
+package org.onlab.onos.store.device.impl;
+
+import java.util.Collection;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+import org.onlab.onos.cluster.NodeId;
+import org.onlab.onos.net.Device;
+import org.onlab.onos.net.DeviceId;
+import org.onlab.onos.store.Timestamp;
+import org.onlab.onos.store.cluster.messaging.AntiEntropyReply;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.ImmutableSet;
+
+public class DeviceAntiEntropyReply
+    extends AntiEntropyReply<DeviceId, VersionedValue<Device>> {
+
+
+    public DeviceAntiEntropyReply(NodeId sender,
+            Map<DeviceId, VersionedValue<Device>> suggestion,
+            Set<DeviceId> request) {
+        super(sender, suggestion, request);
+    }
+
+    /**
+     * Creates a reply to Anti-Entropy advertisement.
+     *
+     * @param advertisement to respond to
+     * @param self node identifier representing local node
+     * @param localValues local values held on this node
+     * @return reply message
+     */
+    public static DeviceAntiEntropyReply reply(
+            DeviceAntiEntropyAdvertisement advertisement,
+            NodeId self,
+            Collection<VersionedValue<Device>> localValues
+            ) {
+
+        ImmutableMap<DeviceId, Timestamp> ads = advertisement.advertisement();
+
+        ImmutableMap.Builder<DeviceId, VersionedValue<Device>>
+            sug = ImmutableMap.builder();
+
+        Set<DeviceId> req = new HashSet<>(ads.keySet());
+
+        for (VersionedValue<Device> e : localValues) {
+            final DeviceId id = e.entity().id();
+            final Timestamp local = e.timestamp();
+            final Timestamp theirs = ads.get(id);
+            if (theirs == null) {
+                // they don't have it, suggest
+                sug.put(id, e);
+                // don't need theirs
+                req.remove(id);
+            } else if (local.compareTo(theirs) < 0) {
+                // they got older one, suggest
+                sug.put(id, e);
+                // don't need theirs
+                req.remove(id);
+            } else if (local.equals(theirs)) {
+                // same, don't need theirs
+                req.remove(id);
+            }
+        }
+
+        return new DeviceAntiEntropyReply(self, sug.build(), req);
+    }
+
+    /**
+     * Creates a reply to request for values held locally.
+     *
+     * @param requests message containing the request
+     * @param self node identifier representing local node
+     * @param localValues local valeds held on this node
+     * @return reply message
+     */
+    public static DeviceAntiEntropyReply reply(
+            DeviceAntiEntropyReply requests,
+            NodeId self,
+            Map<DeviceId, VersionedValue<Device>> localValues
+            ) {
+
+        Set<DeviceId> reqs = requests.request();
+
+        Map<DeviceId, VersionedValue<Device>> requested = new HashMap<>(reqs.size());
+        for (DeviceId id : reqs) {
+            final VersionedValue<Device> value = localValues.get(id);
+            if (value != null) {
+                requested.put(id, value);
+            }
+        }
+
+        Set<DeviceId> empty = ImmutableSet.of();
+        return new DeviceAntiEntropyReply(self, requested, empty);
+    }
+
+    // For serializer
+    protected DeviceAntiEntropyReply() {}
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/OnosDistributedDeviceStore.java b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/OnosDistributedDeviceStore.java
index bd5f2fd..4a0d347 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/OnosDistributedDeviceStore.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/device/impl/OnosDistributedDeviceStore.java
@@ -40,6 +40,7 @@
 import java.util.Objects;
 import java.util.Set;
 import java.util.concurrent.ConcurrentHashMap;
+import java.util.concurrent.ConcurrentMap;
 
 import static com.google.common.base.Preconditions.checkArgument;
 import static org.onlab.onos.net.device.DeviceEvent.Type.*;
@@ -59,8 +60,8 @@
 
     public static final String DEVICE_NOT_FOUND = "Device with ID %s not found";
 
-    private ConcurrentHashMap<DeviceId, VersionedValue<Device>> devices;
-    private ConcurrentHashMap<DeviceId, Map<PortNumber, VersionedValue<Port>>> devicePorts;
+    private ConcurrentMap<DeviceId, VersionedValue<Device>> devices;
+    private ConcurrentMap<DeviceId, Map<PortNumber, VersionedValue<Port>>> devicePorts;
 
     @Reference(cardinality = ReferenceCardinality.MANDATORY_UNARY)
     protected ClockService clockService;