Design and Implementation of a Group Membership Protocol

摘要

A group membership protocol ensures agreement and consistent commit actions amonggroup members to maintain a sequence of identical group views in spite of continuous changes, either voluntary or otherwise, in processors' membership status. In asynchronous distributed environments, such consistency among group views must be guaranteed using messages over a network which does not bound message delivery times. Assuming a network that only provides a reliable, FIFO channel between any pair of processors, one approach to designing such a protocol is to centralize the responsibility to detect changes, ensure agreement, and commit them consistently in a single manager process. This approach is complicated by the fact that a protocol to elect a new manager with a consistent membership proposal must be executed when the manager itself fails. In this thesis, a membership protocol based on ordering of group members in a logical ring that eliminates the need for such centralized responsibility is presented. Agreement and commit actions are token-based and the protocol ensures that no tokens are lost or duplicated due to changes in membership. It is able to process continuous changes to the membership, does not depend upon any majority-based decisions, and processes joins and departures identically. The cost of committing a change is always 2n point-to-point messages over FIFO channels where n is the group size. The protocol correctness is proven in a formal framework. The implementation details for the protocol to execute on a network of SUN workstations is presented. Detailed examples of the behavior of the protocol for various sequences of changes to group membership is presented.