diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/ClusterMembershipMessage.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/ClusterMembershipMessage.java
new file mode 100644
index 0000000..ea00185
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/ClusterMembershipMessage.java
@@ -0,0 +1,66 @@
+package org.onlab.onos.store.cluster.messaging;
+
+import org.onlab.onos.cluster.NodeId;
+import org.onlab.packet.IpPrefix;
+
+/**
+ * Base for cluster membership messages.
+ */
+public abstract class ClusterMembershipMessage extends ClusterMessage {
+
+    private NodeId nodeId;
+    private IpPrefix ipAddress;
+    private int tcpPort;
+
+    // For serialization
+    protected ClusterMembershipMessage() {
+        super(MessageSubject.HELLO);
+        nodeId = null;
+        ipAddress = null;
+        tcpPort = 0;
+    }
+
+    /**
+     * Creates a new membership message for the specified end-point data.
+     *
+     * @param subject   message subject
+     * @param nodeId    sending node identification
+     * @param ipAddress sending node IP address
+     * @param tcpPort   sending node TCP port
+     */
+    protected ClusterMembershipMessage(MessageSubject subject, NodeId nodeId,
+                                       IpPrefix ipAddress, int tcpPort) {
+        super(subject);
+        this.nodeId = nodeId;
+        this.ipAddress = ipAddress;
+        this.tcpPort = tcpPort;
+    }
+
+    /**
+     * Returns the sending node identifer.
+     *
+     * @return node identifier
+     */
+    public NodeId nodeId() {
+        return nodeId;
+    }
+
+    /**
+     * Returns the sending node IP address.
+     *
+     * @return node IP address
+     */
+    public IpPrefix ipAddress() {
+        return ipAddress;
+    }
+
+    /**
+     * Returns the sending node TCP listen port.
+     *
+     * @return TCP listen port
+     */
+    public int tcpPort() {
+        return tcpPort;
+    }
+
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/GoodbyeMessage.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/GoodbyeMessage.java
deleted file mode 100644
index e9326f3..0000000
--- a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/GoodbyeMessage.java
+++ /dev/null
@@ -1,37 +0,0 @@
-package org.onlab.onos.store.cluster.messaging;
-
-import org.onlab.onos.cluster.NodeId;
-
-/**
- * Goodbye message that nodes use to leave the cluster for good.
- */
-public class GoodbyeMessage extends ClusterMessage {
-
-    private NodeId nodeId;
-
-    // For serialization
-    private GoodbyeMessage() {
-        super(MessageSubject.GOODBYE);
-        nodeId = null;
-    }
-
-    /**
-     * Creates a new goodbye message.
-     *
-     * @param nodeId sending node identification
-     */
-    public GoodbyeMessage(NodeId nodeId) {
-        super(MessageSubject.HELLO);
-        this.nodeId = nodeId;
-    }
-
-    /**
-     * Returns the sending node identifer.
-     *
-     * @return node identifier
-     */
-    public NodeId nodeId() {
-        return nodeId;
-    }
-
-}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/HelloMessage.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/HelloMessage.java
index 923e21e..d692e4e 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/HelloMessage.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/HelloMessage.java
@@ -6,18 +6,10 @@
 /**
  * Hello message that nodes use to greet each other.
  */
-public class HelloMessage extends ClusterMessage {
-
-    private NodeId nodeId;
-    private IpPrefix ipAddress;
-    private int tcpPort;
+public class HelloMessage extends ClusterMembershipMessage {
 
     // For serialization
     private HelloMessage() {
-        super(MessageSubject.HELLO);
-        nodeId = null;
-        ipAddress = null;
-        tcpPort = 0;
     }
 
     /**
@@ -28,37 +20,7 @@
      * @param tcpPort   sending node TCP port
      */
     public HelloMessage(NodeId nodeId, IpPrefix ipAddress, int tcpPort) {
-        super(MessageSubject.HELLO);
-        this.nodeId = nodeId;
-        this.ipAddress = ipAddress;
-        this.tcpPort = tcpPort;
-    }
-
-    /**
-     * Returns the sending node identifer.
-     *
-     * @return node identifier
-     */
-    public NodeId nodeId() {
-        return nodeId;
-    }
-
-    /**
-     * Returns the sending node IP address.
-     *
-     * @return node IP address
-     */
-    public IpPrefix ipAddress() {
-        return ipAddress;
-    }
-
-    /**
-     * Returns the sending node TCP listen port.
-     *
-     * @return TCP listen port
-     */
-    public int tcpPort() {
-        return tcpPort;
+        super(MessageSubject.HELLO, nodeId, ipAddress, tcpPort);
     }
 
 }
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/LeavingMemberMessage.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/LeavingMemberMessage.java
new file mode 100644
index 0000000..59686b8
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/LeavingMemberMessage.java
@@ -0,0 +1,24 @@
+package org.onlab.onos.store.cluster.messaging;
+
+import org.onlab.onos.cluster.NodeId;
+
+/**
+ * Announcement message that nodes use to gossip about team departures.
+ */
+public class LeavingMemberMessage extends ClusterMembershipMessage {
+
+    // For serialization
+    private LeavingMemberMessage() {
+        super();
+    }
+
+    /**
+     * Creates a new goodbye message.
+     *
+     * @param nodeId sending node identification
+     */
+    public LeavingMemberMessage(NodeId nodeId) {
+        super(MessageSubject.LEAVING_MEMBER, nodeId, null, 0);
+    }
+
+}
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/MessageSubject.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/MessageSubject.java
index bf86c5b..c7badf2 100644
--- a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/MessageSubject.java
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/MessageSubject.java
@@ -8,8 +8,11 @@
     /** Represents a first greeting message. */
     HELLO,
 
-    /** Signifies node's intent to leave the cluster. */
-    GOODBYE,
+    /** Signifies announcement about new member. */
+    NEW_MEMBER,
+
+    /** Signifies announcement about leaving member. */
+    LEAVING_MEMBER,
 
     /** Signifies a heart-beat message. */
     ECHO
diff --git a/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/NewMemberMessage.java b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/NewMemberMessage.java
new file mode 100644
index 0000000..53bc282
--- /dev/null
+++ b/core/store/dist/src/main/java/org/onlab/onos/store/cluster/messaging/NewMemberMessage.java
@@ -0,0 +1,26 @@
+package org.onlab.onos.store.cluster.messaging;
+
+import org.onlab.onos.cluster.NodeId;
+import org.onlab.packet.IpPrefix;
+
+/**
+ * Announcement message that nodes use to gossip about new arrivals.
+ */
+public class NewMemberMessage extends ClusterMembershipMessage {
+
+    // For serialization
+    private NewMemberMessage() {
+    }
+
+    /**
+     * Creates a new gossip message for the specified end-point data.
+     *
+     * @param nodeId    sending node identification
+     * @param ipAddress sending node IP address
+     * @param tcpPort   sending node TCP port
+     */
+    public NewMemberMessage(NodeId nodeId, IpPrefix ipAddress, int tcpPort) {
+        super(MessageSubject.NEW_MEMBER, nodeId, ipAddress, tcpPort);
+    }
+
+}