Is there a strictly agreed protocol for group membership?

Question

I am looking for an algorithm in which groups of connected nodes can be combined together to form a new group (by creating connections between nodes from different groups). And where the group can be divided into sections to create new sections.

Unlike a consistent style of membership protocols (such as described in the Raft document), where only one group can remain after a section, I would like each new section to form a new group.

Also, I would like for each section of each of its members to agree on who belongs to this section, with a strong guarantee of consistency.

Or else, I would like to have the following property: After a group undergoes a membership change, if two nodes belonging to the original group can still communicate (there is a path between them), they must agree on the sequence of changes that occurred to the group .

I understand that the fact that each new section is consistent with a different set of members in a sense means that the Consistency part of the CAP theorem is weakened. I hope that such a protocol can exist (?).

Answer 1

A consensus protocol (such as Paxos, Raft, etc.) cannot be used to develop a multi-group membership protocol. This is due to the fact that all consensus protocols are based on the fundamental idea that any decision can be made only if most members "agreed" to accept it. Thus, the split-brain phenomenon is avoided, since there cannot be two sections (larger than most: (n/2)+1 ) that agree to another leader (and therefore a set of members), because at least , one member will be a member of both sections and would vote for only one of the sections (the one that asked to vote first).

One of the protocols that can be used to create a protocol for membership in several groups is Virtual Synchronization . However, note that virtual synchronization is a protocol used to send messages to (statically) predefined process groups, as well as existing members of these groups. As a result, it is not intended for cases when new process groups should be created (dynamically) in each new section. Also note that virtual synchronization is a protocol that does not scale for larger members, since message latency is proportional to the size of the groups.

I believe that using the virtual synchronization protocol, you could develop a membership protocol that could satisfy the condition

After a group undergoes a change in membership, if two nodes belonging to the original group can still interact (there is a path between them), they must agree on the sequence of changes that occurred with the group

However, note that this membership is not strictly consistent in the strict sense, because a failure in a node can propagate within a group. However, deliveries of messages (which is important for most) will be delivered in such a way that these deliveries are subject to group membership. This is achieved by imposing the order of message delivery on the side of participants.

---

Another alternative approach for a membership protocol is gossip-based membership protocols , while realistic implementations are integrated into various tools in the industry, such as Consul . To use this approach, you can emit several different message classes from each member, depending on the different groups that you want to track. However, again these groups are statically determined within the protocol and, ultimately, are consistent (which means that every failure will be finally detected by all living members).

---

As a conclusion, I believe that a strictly agreed membership protocol is not possible in a strict definition, since you cannot distinguish between an inappropriate member and a member that reacts really, really slowly (the basis of FLP and the CAP theorem).