On Properties of the Group Membership Problem
Mikhail Nesterenko · 2007
Abstract.We study fault tolerance properties of the group membership problem (GMP) in asynchronous systems. This problem requires each process to determine the processes with which it can communicate. We compare the properties of the GMP and consensus. We define failure sensitivity as the necessary property of a failure detector to enable a solution to the GMP. We demonstrate that the known consensus failure detectors — Ω, Σ, Σ ν are fault insensitive and thus insufficient to solve the GMP. In contrast we define a new reachability failure detector R and show it to be the weakest failure detector to solve the GMP. Furthermore, we demonstrate that R implements the consensus failure detectors. This shows that the GMP is a strictly stronger problem than consensus with respect to the failure detectors that it requires. We present our findings using the primary partition variant of the GMP. We extend them to the partitionable GMP as well as eventual GMP: a weaker variant of the GMP where a process is allowed to make finitely many mistakes in its group membership output. 1