Fault-tolerant Distributed Systems Group Membership Problem

Group Membership Service (GMS) has been one of the most extensively studied problems in fault-tolerant distributed systems since the early 1990s. The problem of GMS is for a group of processes to maintain and agree on the set of processes currently deemed to be operational, where the system environments are often dynamic: processes fail, leave or join the system from time to time. The problem initially arose from Replication services and was later considered one of the basic building blocks in a wide range of fault-tolerant applications where processes cooperate to perform a common task. However, in the presence of asynchrony, failures, network partitions and processes dynamically joining and leaving, the problem has proved to be difficult to define and solve.After surveying up to 30 papers including those recently proposed, we endeavor to present a comprehensive yet clear taxonomy of GMS emphasizing on its interaction with a Membership Discovery Service (MDS), which we believe will facilitate a better understanding of the problem. A list of candidate properties satisfied by existing GMS is also provided with our taxonomy. We further address several subtle issues to help avoid pitfalls in GMS design. As far as we know, ours is the first to study GMS in the light of the mixed concerns contained in it, its solvability influenced by the impossibility results in asynchronous environments and its overlapping nature.