The Group Membership Problem in Asynchronous Systems

Abstract

The thesis formally defines the class of Process Group Membership Problems (GMP) for asynchronous systems. These problems involve maintaining a list of processes belonging to the system, and updating it as processes join (are started) and leave (terminate or fail). We investigate closely the strongest member of the GMP class. Strong GMP presents this list in a consistent manner to all processes using it: the sequence of joins and leaves are identical. We show that despite prevalent beliefs, strong consistency and efficiency are not conflicting goals. This should have significant implications for distributed systems since the need for process membership agreement arises in many canonical problems in distributed computing. We present an inexpensive means (the S-GMP algorithm) of assuring complete, system-wide agreement on process membership. We discuss the role of process membership in distributed systems and how to use S-GMP to build a Membership Resource Manager (MRM). The thesis also examines whether any weaker member of the GMP class suffices to specify an MRM. In doing so we justify using Strong GMP over two much weaker GMP instances in three important ways. First, by comparing Strong GMP and its minimal solution with the weaker instances and their minimal solutions, we arrive at the surprising result that Strong GMP is often less expensive than the others, notably in executions in which membership changes are frequent. Second, we show that a membership service defined by Strong GMP is more robust, more responsive and more adaptable than a membership service defined by weaker GMP instances. Third, we compare membership services defined by the various GMPs according to the utility each service provides higher-level, distributed applications. That is, ignoring implementation costs, how useful are the different GMP consistency guarantees as a platform on which to build distributed solutions to distributed problems? We show that the consistency guarantees of Strong GMP make it (i.e. and the membership service Strong GMP defines) more useful to higher-level distributed applications. Finally, the thesis presents experimental results from implementing S-GMP. The data demonstrate that a centralized Membership Resource Manager is a non-intrusive service around which to design distributed systems and provide system-wide consistency. The data quantify and help clarify the tradeoffs between replication degree, overall system size and process failure frequency. These initial results should guide future MRM design and development.