Consistent group membership for semi-active and passive replication

[0001] This application claims priority from U.S. provisional application Ser. No. 60/407,586 filed on Aug. 30, 2002, incorporated herein by reference.

[0002] This invention was made with Government support under Grant No. 70NANBOH3015, awarded by the US Department of Commerce National Institute of Standards & Technology. The Government has certain rights in this invention.

[0003] Not Applicable

[0004] A portion of the material in this patent document is subject to copyright protection under the copyright laws of the United States and of other countries. The owner of the copyright rights has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the public file or record of the United States Patent and Trademark Office, but otherwise reserves all copyright rights whatsoever. The copyright owner does not hereby waive any of its rights to have this patent document maintained in secrecy, including without limitation its rights pursuant to 37 C.F.R. § 1.14.

[0005] 1. Field of the Invention

[0006] This invention relates generally to fault-tolerant computer systems based on semi-active or passive replication and, more specifically, to the problem of maintaining a consistent group membership when the members of the group are subject to failure.

[0007] 2. Incorporation by Reference

[0008] The following patents and publications are incorporated herein by reference:

• • [0009] U.S. Pat. No. 5,696,896
  • [0010] U.S. Pat. No. 5,699,501
  • [0011] U.S. Pat. No. 5,704,032
  • [0012] U.S. Pat. No. 5,787,249
  • [0013] U.S. Pat. No. 5,787,250
  • [0014] U.S. Pat. No. 5,793,962
  • [0015] U.S. Pat. No. 5,923,831
  • [0016] U.S. Pat. No. 5,999,712

• [0017] H. Kopetz, G. Grunsteidl and J. Reisinger, Fault-tolerant membership service in a distributed real-time system, Proceedings of the International Conference on Dependable Computing for Critical Applications, Santa Barbara, Calif., August 1989, pp. 167–174.
• [0018] P. D. Ezhilchelvan, and R. de Lemos, A robust group membership algorithm for distributed real-time systems, Proceedings of the IEEE Real-Time Systems Symposium, Lake Buena Vista, Fla., December 1990, pp. 173–179.
• [0019] D. Powell (ed.), Delta-4: A Generic Architecture for Dependable Distributed Computing, Research Reports ESPRIT, Springer-Verlag, Berlin, 1991.
• [0020] S. Mishra, L. L. Peterson and R. D. Schlichting, A membership protocol based on partial order, Proceedings of the Second International Working Conference on Dependable Computing for Critical Applications 2, Tucson, Ariz., February 1991, Dependable Computing and Fault-Tolerant Systems, vol. 6, Springer-Verlag, pp. 309–331.
• [0021] F. Cristian, Reaching agreement on processor group membership in synchronous distributed systems, Distributed Computing, vol. 4, April 1991, pp. 175–187.
• [0022] A. M. Ricciardi and K. P. Birman, Using process groups to implement failure detection in asynchronous environments, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 1991, pp. 341–353.
• [0023] Y. Amir, D. Dolev, S. Kramer and D. Malki, Membership algorithms for multicast communication groups, Proceedings of the 6th International Workshop on Distributed Algorithms, Haifa, Israel, November 1992, pp. 292–312.
• [0024] K. P. Birman and R. van Renesse, Reliable Distributed Computing with the Isis Toolkit, IEEE Computer Society Press, 1994.
• [0025] L. E. Moser, P. M. Melliar-Smith and V. Agrawala, Processor membership in asynchronous distributed systems, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 5, May 1994, pp. 459–473.
• [0026] Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal and P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems, vol. 13, no. 4, November 1995, pp. 311–342.
• [0027] L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, R. K. Budhia and C. A. Lingley-Papadopoulos, Totem: A fault-tolerant multicast group communication system, Communications of the ACM, vol. 39, no. 4, April 1996, pp. 54–63.
• [0028] I. Keidar, J. Sussman, K. Marzullo and D. Dolev, A client-server oriented algorithm for virtually synchronous group membership in WANs, Proceedings of the 20th IEEE International Conference on Distributed Computing Systems, Taipei, Taiwan, April 2000, pp. 356–365.
• [0029] M. Franceschetti and J. Bruck, A group membership algorithm with a practical specification, IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 11, November 2001, pp. 1190–2000.

[0030] Many computer systems and applications structure objects into object groups or simply groups. For example, fault-tolerant systems are based on entity redundancy (replication), and the replicas of an entity are structured into a group. In software fault tolerance the entities that are typically replicated are the application processes. In hardware fault tolerance the entities that are replicated are processors and/or networks.

[0031] The term object is generally utilized herein to refer to an object, process, container, component, memory protection domain or processor, and the term group is generally utilized for referring to a set of objects.

[0032] Distributed systems achieve fault tolerance by allowing replicas of an object to be different computers, or to be hosted on different computers. In a distributed system a client invokes a method of a server by sending a request message, containing the method invocation, to the server. The server executes the method invocation and sends a reply message, containing the result of the method invocation, to the client. Both clients and servers can be members of groups, in which case the system contains both client groups and server groups. To ensure that all members of a group can receive messages reliably, even as the group membership changes, knowledge of the membership is required.

[0033] Objects can be replicated using active, semi-active or passive replication. In active replication all of the members of the group are equal, and all of the replicas execute the methods invoked on the group. In semi-active replication and passive replication one of the members of the group is the Primary and the other members are Backups. In both semi-active and passive replication, the Primary executes the methods invoked on the group. In semi-active replication the Backups receive and log the request and reply messages and perform the operations, but they do not multicast the request or reply messages. In passive replication the Backups receive and log the request and reply messages, but they do not perform the operations and do not multicast request or reply messages. The current invention applies to semi-active and passive replication.

[0034] The group membership problem is difficult because different members of the group can reach different decisions on whether the Primary is faulty and on the group membership, due to the asynchrony in the distributed system and the unreliability of the fault detectors. Most group membership algorithms employ a consensus algorithm to achieve agreement on the membership and on the Primary member of the group; however, achieving consensus in an asynchronous distributed system is impossible without the use of timeouts to bound the time within which a member must take an action. With timeouts, achieving consensus can be relatively costly in the delays that are incurred in reaching consensus and in recovering from a fault.

[0035] Many of the topics related to fault-tolerant distributed systems have been described in D. Powell, ed., Delta-4: A Generic Architecture for Dependable Distributed Computing, Springer-Verlag, 1991, incorporated herein by reference, including semi-active and passive replication. Multicast group communication has been used in distributed systems to maintain replica consistency (see, e.g., K. P. Birman and R. van Renesse, Reliable Distributed Computing with the Isis Toolkit, IEEE Computer Society Press, 1994, incorporated herein by reference, and L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, R. K. Budhia and C. A. Lingley-Papadopoulos, Totem: A fault-tolerant multicast group communication system, Communications of the ACM, vol. 39, no. 4, April 1996, pp. 54–63, incorporated herein by reference). Membership algorithms for group communication systems have been investigated by a number of researchers, as discussed below.

[0036] Membership protocols for group communication systems described in K. P. Birman and R. van Renesse, Reliable Distributed Computing with the Isis Toolkit, IEEE Computer Society Press, 1994, incorporated herein by reference, and L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal, R. K. Budhia and C. A. Lingley-Papadopoulos, Totem: A fault-tolerant multicast group communication system, Communications of the ACM, vol. 39, no. 4, April 1996, pp. 54–63, incorporated herein by reference, use the term view change to represent any change in the membership of a group. In particular, each successive membership, which involves removal or addition of a member, constitutes a new view.

[0037] Kopetz et. al. (H. Kopetz, G. Grunsteidl and J. Reisinger, Fault-tolerant membership service in a distributed real-time system, Proceedings of the International Conference on Dependable Computing for Critical Applications, Santa Barbara, Calif., August 1989, pp. 167–174, incorporated herein by reference) have developed a lock-step synchronous membership algorithm for real-time distributed systems, based on a time-division multiple-access strategy.

[0038] Cristian (F. Cristian, Reaching agreement on processor-group membership in synchronous distributed systems, Distributed Computing, vol. 4, no. 4, April 1991,175–187, incorporated herein by reference) have also described membership algorithms for synchronous systems. Those membership algorithms require synchronized clocks and bounded message transmission times. Periodically, or on demand, each processor must reaffirm its existence.

[0039] Ezhilchelvan and de Lemos (P. D. Ezhilchelvan, and R. de Lemos, A robust group membership algorithm for distributed real-time systems, Proceedings of the IEEE Real-Time Systems Symposium, Lake Buena Vista, Fla., December 1990, pp. 173–179, incorporated herein by reference) have described a similar group membership algorithm for real-time distributed systems, based on time-division multiplexing. Each processor maintains a membership status vector, which contains the processor's view of the membership status of all processors. In every cycle a processor transmits its membership status vector and recomputes its membership status vector based on the membership status vectors that it has received from the other processors.

[0040] Ricciardi and Birman (A. M. Ricciardi and K. P. Birman, Using process groups to implement failure detection in asynchronous environments, Proceedings of the Tenth Annual ACM Symposium on Principles of Distributed Computing, Montreal, Quebec, Canada, August 1991, pp. 341–353, incorporated herein by reference) have presented a three-phase commit removal algorithm that requires 5n-9 point-to-point messages to remove a processor and a relatively long delay from failure to removal.

[0041] Mishra et. al. (S. Mishra, L. L. Peterson and R. D. Schlichting, A membership protocol based on partial order, Proceedings of the Second International Working Conference on Dependable Computing for Critical Applications 2, Tucson, Ariz., February 1991, Dependable Computing and Fault-Tolerant Systems, vol. 6, Springer-Verlag, pp. 309–331, incorporated herein by reference) have presented a membership protocol based on a partial order.

[0042] The membership algorithms of L. E. Moser, P. M. Melliar-Smith and V. Agrawala, Processor membership in asynchronous distributed systems, IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 5, May 1994, pp. 459–473, incorporated herein by reference, differ from other membership algorithms in that they operate on top of a fault-tolerant total ordering algorithm and they exploit the probabilistic behavior of the communication medium. The fault tolerance of the underlying total ordering algorithm allows the system to operate without interruption during membership changes.

[0043] The membership algorithms described in Y. Amir, D. Dolev, S. Kramer and D. Malki, Membership algorithms for multicast communication groups, Proceedings of the 6th International Workshop on Distributed Algorithms, Haifa, Israel, November 1992, pp. 292–312, incorporated herein by reference, and Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal and P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems, vol. 13, no. 4, November 1995, pp. 311–342, incorporated herein by reference, achieve consensus on the membership within a bounded time, even if further faults occur, by reducing the membership set until consensus is reached and by using timeouts that bound the time spent in any state of the membership algorithm. Those algorithms also handle network partitioning and remerging of components of a partitioned network.

[0044] Keidar et. al. (I. Keidar, J. Sussman, K. Marzullo and D. Dolev, A client-server oriented algorithm for virtually synchronous group membership in WANs, Proceedings of the 20th IEEE International Conference on Distributed Computing Systems, Taipei, Taiwan, April 2000, pp. 356–365, incorporated herein by reference) have presented membership algorithms that employ an event service to disseminate notifications of fault events, as well as membership changes due to processes joining or leaving a group. On receiving an event notification for a membership change, a server determines the new membership using a one-round membership algorithm that is fast but blocks if a fault occurs. The one-round membership algorithm is used in conjunction with a slower three-round membership algorithm that does not block.

[0045] M. Franceschetti and J. Bruck, A group membership algorithm with a practical specification, IEEE Transactions on Parallel and Distributed Systems, vol. 12, no. 11, November 2001, pp. 1190–2000, incorporated herein by reference, describes a membership algorithm in which a local fault detector informs a process of a change in its local connectivity view. The process with the smallest identifier in the new local connectivity view sends a Propose message to all processes in its view, proposing a membership change. Each process records the proposal until its new view is the same as the proposed view, at which point it sends an Accept message or a Retry message to the proposer, depending on whether it agrees with the proposed view number. If the proposer receives a Retry message, it sends a new Propose message containing a new view number to all processes in its view. When the proposer has collected Accept messages from all processes in its view, it sends a Commit message. On receiving a Commit message, a process commits the new membership.

[0046] U.S. Pat. Nos. 5,696,896, 5,699,501 and 5,704,032, each of which is incorporated herein by reference, describe a group membership and group leader selection strategy in which the new group leader is selected from a membership list that is ordered in the sequence of joins to the membership. The selected leader is the next processor on the membership list after the failed group leader; in particular, it is the next active processor on the membership list. The group of processors is informed of the new group leader, after it is selected.

[0047] U.S. Pat. Nos. 5,787,249, 5,787,250 and 5,793,962, each of which is incorporated herein by reference, describe a method, program product and system for managing the membership of a group of processors in a distributed system. Processors may request to join the group of processors, and then are added to the group. Similarly, processors may request to leave the group or can fail, and then are removed from the group. The group of processors receives multicasts that are initiated by the members of the group. The group has a group leader that controls the actions that the group members perform, and the group leader is selected by a voting protocol that provides the consensus necessary to ensure that all group members agree on the group leader. In contrast, the present invention requires no consensus protocol.

[0048] U.S. Pat. No. 5,923,831, which is incorporated herein by reference, discloses a method of coordinating the membership of a group of processes in a distributed system. Initially, each process sends the other processes its view of their statuses, and then waits, up to a predetermined timeout, for similar views from the other processors, except those that, in its own view, have failed. Each process then generates a resulting view by intersecting its local view with the views that it has received from the other processes. The local views are updated based on the resulting views and are again exchanged, until a termination condition occurs. The algorithm of that invention is similar to the membership algorithms described in Y. Amir, D. Dolev, S. Kramer, D. Malki, Membership algorithms for multicast communication groups, Proceedings of the Workshop on Distributed Algorithms, Haifa, Israel, November 1992, pp. 292–312, incorporated herein by reference, and Y. Amir, L. E. Moser, P. M. Melliar-Smith, D. A. Agarwal and P. Ciarfella, The Totem single-ring ordering and membership protocol, ACM Transactions on Computer Systems, vol. 13, no. 4, November 1995, pp. 311–342, incorporated herein by reference.

[0049] U.S. Pat. No. 5,999,712, which is incorporated herein by reference, discloses a method for determining the cluster membership in a distributed system by broadcasting, either directly or indirectly, connectivity information about the nodes with which it is able to communicate. Each node elects a new cluster from the clusters that the various nodes proposed, using some deterministic algorithm, such as the cluster that is proposed more often than any other cluster.

[0050] Based on the foregoing, it can be seen that a need exists for a method of maintaining consistent group membership in distributed systems subject to semi-active and passive replication and that may be utilized within fault-tolerant systems without the need for a consensus decision and without excess overhead. The present invention satisfies those needs, as well as others, and overcomes the deficiencies of previously developed group membership methods.

[0051] This invention addresses the group membership problem in a fault-tolerant distributed system that is based on Semi-Active or Passive replication, where the Primary member of the group acts as the leader of the group and the Backup members act as followers. The mechanisms of the present invention are particularly suited to groups of replicas that provide fault tolerance, but are also useful for groups that are formed to achieve other objectives, where those groups must survive faults in their members.

[0052] A group membership algorithm, and in particular the group membership algorithm of the present invention described herein, ensures that the members of the group have a consistent view of the membership set and of the member of the group that is the Primary. The mechanisms of the present invention effect a membership change and a consistent view of the membership more quickly than other membership algorithms by avoiding the need for a multiple-round consensus algorithm.

[0053] In one embodiment, each member of the group is assigned a rank. The Primary has the lowest rank (rank=1) and the Backups have higher ranks. Each member of the group is also assigned a unique precedence, determined by the order in which it is added to the group.

[0054] It should be appreciated that it is the relationship of the ranks and precedences which is important in the present invention, wherein the terms “lower” and “higher” can be reversed so long as the associated execution is modified.

[0055] In one embodiment of the membership algorithm of the present invention, the Primary determines the addition of Backups to, and the removal of Backups from, the group. The Backup that first announces the failure of the Primary decides the new membership and becomes the new Primary, unless a Backup with a higher precedence also announces the failure of the Primary and claims to be the new Primary.

[0056] Each Backup monitors the behavior of the Primary, using a fault detection timeout that is determined by the Backup's rank. A Backup detects that the Primary is faulty if it detects a lack of valid activity from the Primary member, such as not receiving a message from the Primary within a fault detection timeout interval. The Backup of rank=2 uses a short timeout to detect that the Primary is faulty. The Backup of rank=3 uses a longer timeout to detect that the Primary is faulty, allowing time for the Backup of rank=2 to react to the fault in the Primary. If the fault detection timeout for the Primary at the Backup of rank=3 expires, the Backup of rank=3 determines that both the Primary and the Backup of rank=2 are faulty. The Backup of rank=4 uses an even longer timeout to detect that the Primary is faulty. If the fault detection timeout for the Primary at the Backup of rank=4 expires, the Backup of rank=4 determines that the Primary, the Backup of rank=2 and the Backup of rank=3 are faulty. If more than three Backups are used, the mechanisms are similar.

[0057] If two Backups both determine that the Primary is faulty and claim to be the new Primary, the Backup with the higher precedence assumes the role of the Primary. Thus, the Backup of rank=3 has authority over both the Primary and the Backup of rank=2 to reconfigure the membership, and the Backup of rank=4 has authority over the Primary, the Backup of rank=2 and the Backup of rank=3 to reconfigure the membership. Consequently, the Backup with the highest precedence has the greatest authority over the Primary and the other Backups to reconfigure the membership but, because it has the highest rank, it has the longest fault detection timeout and thus is the slowest to exercise that authority.

[0058] The advantages of the group membership algorithm disclosed here are that a consensus decision is not required to reconfigure the membership and that a membership change can be effected more quickly in the common case where the Backup of rank=2 takes control as the new Primary when it determines that the existing Primary has failed.

[0059] Note that membership protocols for group communication systems define a view change as occurring in response to any change in the membership of a group. By contrast, in the present invention, only membership changes that correspond to a change of the Primary constitute a new view. This new view is referred to herein as a primary view change. Each such new primary view has a primary view sequence number.

[0060] Note also that use of consensus algorithms for achieving agreement on group membership require the use of timeouts and have a number of disadvantages. The group membership algorithm of the present invention achieves consistent group membership among the members of a group in a distributed system. One of the members of the group is distinguished as the Primary (leader) and the other members of the group are Backups (followers):

[0061] without incurring the delays of a consensus algorithm;

[0062] without incurring the overhead of the large number of messages that must be transmitted to achieve consensus; and

[0063] without incurring a risk that different members of the group will reach different decisions about the membership and about which member is the Primary, even though a consensus algorithm is not used.

[0064] The present invention provides a zero-round membership algorithm, which is in contrast to the use of conventional membership algorithms that require one or more rounds but which block if a fault occurs, or three rounds to perform the membership algorithm without blocking.

[0065] Similar to some conventional systems, the present invention orders the membership list from which a new group leader can be selected. However, within the present invention every Backup is responsible for monitoring the behavior of the Primary and for forming a new membership, if necessary.

[0066] It can be seen, therefore, that an aspect of the invention is to provide fault tolerance in a distributed system based on Semi-Active or Passive replication.

[0067] Another aspect of the invention is utilizing a group membership method in which the Primary member of the group acts as the leader of the group and the Backup members act as followers.

[0068] Another aspect of the invention is that of having the Primary member of the group maintain memberships for the group and to distribute membership information.

[0069] Another aspect of the invention is the use of rank and precedence for the members of the group to determine which Backup is to take over as the next Primary in the event of a failure of the Primary.

[0070] Another aspect of the invention is that the Primary and Backups need not have information about the addition or removal of Backups from a remote group with which they are communicating.

[0071] Another aspect of the invention is that Backups of higher ranks utilize timeouts of greater lengths, wherein a Backup is selected for replacing the Primary even if other Backups are faulty.

[0072] Another aspect of the invention is that Backups of higher ranks have greater authority over the Primary and Backups of lower ranks in the event of failure of the Primary, but have a longer delay so as not to take over if a Backup of lower rank is operational.

[0073] A still further aspect of the invention is that the Primary and Backups only need to discover when there is a change in the Primary of a remote group with which they are communicating and don't need to discover all changes in the remote membership if those changes involve the addition or removal of a Backup.

[0074] Further aspects of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.

[0085] The context in which this invention is described is an application that is replicated using Semi-Active or Passive replication, where the members of the group are distributed across multiple computers within a distributed computer system.

[0086] When an application is replicated for fault tolerance, using Semi-Active or Passive replication, there is a single Primary replica and one or more Backup replicas, where the replicas constitute a group. In other usages of groups, it is also convenient to designate one of the members as the Primary and the other members as Backups.

[0087] In this invention the term object is used to refer to the entities that are replicated, which may be processes, containers, components, memory protection domains or processors. The invention is described in terms of a client that invokes methods of a server, although an object can act as both a client and a server in a multi-tier or peer-to-peer application, where the server also acts as a client and invokes methods of other servers. The invention applies to both client and server groups. The invention also makes reference to messages being multicast to members of the group, which can consist of a single transmission or multiple point-to-point transmissions. The mechanisms of the current invention are unaffected by such extensions.

[0088] The diagrams and the descriptions shown below will further illustrate the preferred embodiments of this invention.

[0089] The membership algorithm that is the subject of this invention uses the Primary member of the group to maintain the membership of the group and to distribute membership information. If the Primary fails, one of the Backups assumes the role of the Primary. The algorithm uses the notions of rank and precedence to determine, in the event of the failure of the Primary, which of the Backups is to become the next Primary. The precedence of a member of a group is determined by the order in which it is added to the group. The rank of the Primary member is 1, and the rank of each Backup member is greater than 1 and determines the Backup's fault detection timeout for the Primary.

[0090] To achieve reliable message delivery, both the Primary and the Backups need to know when there is a change in the Primary of a remote group with which they are communicating. Moreover, both the Primary and the Backups need to know the membership of their own group because it affects their ranks and their precedences in that group. However, the Primary and the Backups do not need to know about the addition of a Backup to, or removal of a Backup from, a remote group.

[0091] The Primary determines the addition of a new Backup to, and the removal of a Backup from, the group. Each Backup monitors the behavior of the Primary using a fault detection timeout that is determined by its rank. A Backup detects that the Primary is faulty if it does not receive a message from the Primary within the timeout.

[0092] The Backup of rank=2 uses a short timeout to detect that the Primary is faulty. The Backup of rank=3 uses a longer timeout, allowing time for the Backup of rank=2 to react to the fault in the Primary. The Backup of rank=4 uses an even longer timeout and so on.

[0093] If the fault detection timeout for the Primary at the Backup of rank=3 occurs, the Backup of rank=3 determines that both the Primary and the Backup of rank=2 are faulty. If the fault detection timeout for the Primary at the Backup of rank=4 occurs, the Backup of rank=4 determines that the Primary, the Backup of rank=2 and the Backup of rank=3 are faulty.

[0094] If two Backups both determine that the Primary is faulty and claim to be the new Primary, the Backup with the higher precedence assumes the role of the Primary. The Backup of rank=3 has authority over both the Primary and the Backup of rank=2 to reconfigure the membership, and the Backup of rank=4 has authority over the Primary, the Backup of rank=2 and the Backup of rank=3 to reconfigure the membership. Thus, the Backup with the highest precedence has the greatest authority to reconfigure the membership but, because it has the highest rank, it has the longest fault detection timeout for the Primary and thus is the slowest to exercise that authority.

[0095] Each message header, for both regular application messages and membership messages, has a primary view number field, primaryViewNum. The primaryViewNum is the number of membership changes that involve a change in the Primary. The primaryViewNum allows the Primary and the Backups to discover when there is a change in the primary view of a remote group with which they are communicating, i.e., that there is a new Primary for the remote group and, consequently, that request, reply and other messages multicast to, or multicast by, the former Primary of the remote group might have been lost. This primaryViewNum is different from the view number, used by multicast group communication systems, that changes whenever any change in the membership occurs, including adding and removing not only the Primary but also the Backups.

[0096] The membership of a group is changed by means of AnnouncePrimary, AddBackup and RemoveBackup membership messages. The AnnouncePrimary message is multicast by a Backup to request or confirm a change of the Primary. The AddBackup message is used by the Primary to add a Backup to the group. The RemoveBackup message is used by the Primary to remove a Backup from the group.

[0097] The Primary is removed from the group either because it is determined to be faulty or for some other reason such as resource management. FIG. 1, FIG. 2 and FIG. 3 illustrate three different scenarios in which the Primary has been detected to be faulty.

[0098] The members of a group are ordered by rank r, where the Primary has rank=1 and the Backups have rank>=2. The ranks determine which Backup becomes the next Primary, if the Primary fails. If the Backup of rank=2 also fails, the Backup of rank=3 is the next-in-line, and so forth.

[0099] To minimize the risk that two Backups both claim to be the next new Primary, the fault detection timeouts for the Primary in the Backups increase with increasing rank. For example, the Backup of rank=2 might have a timeout of 10 ms, the Backup of rank=3 a timeout of 30 ms and the Backup of rank=4 a timeout of 50 ms. Thus, the 30 ms timeout for the Backup of rank=3 allows 10 ms of inaction by the Primary, 10 ms of inaction by the Backup of rank=2 and 10 ms for skew between the timeouts for the Primary in the different Backups. Triggering the Backup of rank=3, with its longer timeout, is rare, while race conditions are even more rare.

[0100] To eliminate the possibility that two Backups both claim to be the next new Primary, the members are ordered by precedence wherein, if member m1 has precedence p1 and member m2 has precedence p2, and p1<p2, then member m1 was added to the group before member m2. Thus, if two Backups of different ranks both claim to be the next new Primary, the Backup with the higher precedence breaks the tie and becomes the new Primary.

[0101] If a Backup detects that the Primary is faulty, because it has not received a message from the Primary before the timeout (FIG. 4), the Backup multicasts an AnnouncePrimary message to its local group, denouncing the current Primary and appointing itself as the new Primary. The header of the AnnouncePrimary message contains the group identifier and the primary view number before the membership change, and the payload contains the Backup's identifier, rank r and precedence p. Effectively, the Backup of precedence p excludes the old Primary and the Backups of precedences<p from the membership. Such a Backup of precedence<p did not send an AnnouncePrimary message quickly enough to become the new Primary and, thus, the Backup of precedence p declares the Backups of precedence<p to be faulty.

[0102] A Backup does not multicast an AnnouncePrimary message that promotes itself as the new Primary before its timeout for the existing Primary expires.

[0103] If a Backup receives an AnnouncePrimary message for a new membership (FIG. 5) and the precedence of the proposed Primary is less than the precedence of the current Primary, the Backup ignores the AnnouncePrimary message. If a Backup receives an AnnouncePrimary message with a precedence p for the proposed new Primary, the Backup subsequently ignores any AnnouncePrimary message with a precedence for the proposed new Primary less than p.

[0104] When a Backup receives an AnnouncePrimary message for a new primary view, the Backup resets its fault detection timeouts.

[0105] A Backup is added to a group for any of a number of reasons, such as the minimum number of members having fallen below a desired threshold.

[0106] The Primary adds the new Backup member to its local copy of the group membership set and then multicasts an AddBackup message, containing the identifier, precedence and rank of the Backup that it is adding to the group, as shown in FIG. 6 through FIG. 9.

[0107] When a Backup receives the AddBackup message, it adds the new member as a Backup to its local copy of the group membership, with the identifier, precedence and rank of the new Backup contained in the AddBackup message.

[0108] A Backup member is removed from a group because it is determined to be faulty or for some other reason.

[0109] The Primary removes the Backup from its local copy of the group membership set and then multicasts a RemoveBackup message, containing the identifier of the Backup that it is removing from the group, to the group.

[0110] When a Backup receives the RemoveBackup message, containing the identifier of the Backup being removed, it removes the Backup from its local copy of the group membership set.

[0111] in FIG. 1 there are four members 2, 4, 6 and 8. Of these, the Primary 2 has rank=1 and precedence=114, the Backup 4 of rank=2 has precedence=115, the Backup 6 of rank=3 has precedence=116 and the Backup 8 of rank=4 has precedence=117. The number of Backups is determined by the nature of the application, the hardware/software platform and the degree of resilience required; three Backups are shown for illustration purposes.

[0112] After a period of normal fault-free operation, the Primary becomes faulty 10. This fault is not detected immediately; rather, after a short period of time, the fault detection timeout for the Primary in the Backup of rank=2 expires 12 and the Backup of rank=2 detects the fault in the Primary. The fault detection timeout for the Primary in the Backup of rank=2 is likely to expire before the fault detection timeout for the Primary in the Backup of rank=3 or the Backup of rank=4, because the timeout in the Backup of rank=2 is shorter than the other timeouts.

[0113] When the Backup of rank=2 detects a fault in the Primary 12, the Backup of rank=2 multicasts a message that announces the fault and that it is forming a new membership with itself as the Primary 14. Once it has multicast that message, the Backup of rank=2 determines that the faulty Primary is offline 16 and the Backup of rank=2 then becomes the new Primary 18. The Backup of rank=3 and the Backup of rank=4 remain Backups, but the former Backup of rank=3 becomes a Backup 20 of rank=2 and the former Backup of rank=4 becomes a Backup 22 of rank=3. Their precedences remain unchanged.

[0114] If, after it has been repaired, the former Primary rejoins the group, it does so as a Backup 24 of rank=4, that is one greater than the highest rank of any of the current members of the group, and with a precedence=118, that is one greater than the highest precedence of any current or prior member of the group.

[0115] FIG. 2 shows the same set of four members as FIG. 1, with a Primary 30 and three Backups 32, 34 and 36. In FIG. 2, however, the Primary becomes faulty 38 and the Backup of rank=2 also becomes faulty 40. Because the Backup of rank=2 is faulty, its fault detection timeout does not expire and the Backup of rank=2 does not detect the fault in the Primary at the time at which it would have been expected to do so 42.

[0116] Consequently, after a slightly longer delay, the fault detection timeout for the Primary in the Backup of rank=3 expires 44 and the Backup of rank=3 determines that both the Primary and the Backup of rank=2 are faulty. The Backup of rank=3 multicasts 46 a message that announces the faults and also a new membership with itself as the Primary. Once it has multicast the message, the Backup of rank=3 determines that the former Primary that failed is offline 48 and that the Backup of rank=2 that failed is offline 50. The former Backup of rank=3 then assumes the role of the new Primary 52.

[0117] FIG. 3 shows the same set of four members, with a Primary 60 and three Backups 62, 64 and 66. In FIG. 3 the Primary becomes faulty 68, but the Backup of rank=2 does not become faulty 70. For whatever reason, the Backup of rank=2 does not detect the faulty Primary at the time at which it is expected to detect the fault 72.

[0118] Consequently, after a slightly longer delay, the fault detection timeout for the Primary in the Backup of rank=3 expires 74 and the Backup of rank=3 determines that both the Primary and the Backup of rank=2 are faulty. The Backup of rank=3 then multicasts a message 76 that announces those faults and also a new membership with itself as the Primary. Once it has multicast that message, the Backup of rank=3 determines that the old Primary and the Backup of rank=2 are offline 78, 80 and the Backup of rank=3 then becomes the new Primary 82. When the former Backup of rank=2 receives the announcement of the new membership, multicast by the former Backup of rank=3, the former Backup of rank=2 determines that the new Primary has a precedence greater than its own precedence, removes itself from the membership and places itself offline. Subsequently, the former Backup of rank=2 can apply for readmission to the membership.

[0119] FIG. 4 is a flow diagram that shows the actions of a Backup when its fault detection timeout for the Primary expires 100. First, the Backup checks whether its membership is a recent new membership 102. If the membership is a recent new membership, the Backup starts a fault detection timeout for the Primary 112 and then exits 114. Otherwise, the Backup removes the Primary and all Backups with ranks less than its own rank 104. The Backup then creates a new membership set, determines the precedences and calculates the ranks of the members in that membership set 106, and appoints itself as the new Primary 108. It then multicasts a message that contains an announcement of the new membership, along with the precedences and ranks of the members 110, and exits 114.

[0120] In general, the steps executed on expiration of the fault detection timeout for the Primary in a Backup, comprise the following:

[0121] if recent new membership

• • [0122] start fault detection timeout

[0123] else

• • [0124] remove current Primary from membership
  • [0125] remove all Backups with rank<myRank from the membership
  • [0126] create new membership
  • [0127] determine precedences and calculate ranks
  • [0128] currentPrimary=myself
  • [0129] myRole=Primary
  • [0130] multicast announcement of new membership along with precedences and ranks

[0131] FIG. 5 is a flow diagram that shows the actions of a member on reception of an announcement of a new membership 120. First, the member checks whether the precedence of the new Primary is greater than its own precedence 122. If the precedence of the new Primary is greater than its own precedence, it leaves the membership 128, waits for the membership to stabilize 130, starts a membership application timeout 132, transmits an application for membership 134 and exits 140.

[0132] If the precedence of the new Primary is less than or equal to its own precedence, the member checks whether the precedence of the new Primary is less than the precedence of the current Primary 124. If the precedence of the new Primary is less than the precedence of the current Primary, it ignores the announcement 138 and exits 140.

[0133] If the precedence of the new Primary is greater than or equal to the precedence of the current Primary, the member checks whether it is in the new membership 126. If it is in the new membership, the member records the new membership, including the ranks and precedences of the members, and the new current Primary 136 and exits 140.

[0134] If it is not in the new membership, the member leaves the membership 128, waits for the membership to stabilize 130, starts the membership application timeout 132, multicasts an application for membership 134 and exits 140.

[0135] In general, the steps executed on reception of announcement of a new membership, comprise:

[0136] if precedence of new Primary>myPrecedence

• • [0137] leave membership
  • [0138] wait for the membership to stabilize
  • [0139] start membership application timeout
  • [0140] multicast application for membership

[0141] else

• • [0142] if precedence of new Primary>=precedence of currentPrimary
    • [0143] if I am in the new membership
      • [0144] record new membership and currentPrimary
        • [0145] including ranks and precedences
    • [0146] else
      • [0147] leave membership
      • [0148] wait for the membership to stabilize
      • [0149] start membership application timeout
      • [0150] multicast application for membership
  • [0151] else
    • [0152] ignore announcement

[0153] FIG. 6 is a flow diagram that shows the actions of a member when it receives an application to join the membership 150. First, the member checks whether it is the Primary 152. If it is not the Primary, the member ignores the application 162 and exits 164.

[0154] If the member is the Primary, it checks whether the applicant is a member of the current membership 154. If the applicant is a member of the current membership, the Primary ignores the application 162 and exits 164.

[0155] If the applicant is not a member of the current membership, the Primary determines the precedence and calculates the rank for the new applicant member 156, adds the applicant to its local copy of the membership 158, multicasts an announcement of the new membership along with the precedences and ranks of the members 160 and exits 164.

[0156] The following general steps are performed when a member receives an application to join the membership:

[0157] if myRole ==Primary

• • [0158] if the applicant is not already a member
    • [0159] determine precedence and calculate rank of new member
    • [0160] add the applicant to membership
    • [0161] multicast announcement of new membership along with precedences and ranks

[0162] else

• • [0163] ignore application

[0164] FIG. 7 is a flow diagram that shows the actions of an applicant for membership when it receives an announcement of a new membership 170. First, the applicant checks whether it is in the new membership 172. If it is not in the new membership, the applicant ignores the announcement 180 and exits 182.

[0165] If it is in the new membership, the applicant cancels the membership application timeout 174, records the membership along with the ranks and precedences of the members 176, sets its role to Backup 178 and exits 182.

[0166] The following general steps are performed when the applicant for membership receives an announcement of new membership:

[0167] if I am the applicant and I am in the new membership

• • [0168] cancel membership application timeout
  • [0169] record membership of group along with
    • [0170] ranks and precedences
  • [0171] myRole=Backup

[0172] else

• • [0173] ignore announcement

[0174] FIG. 8 is a flow diagram that shows the actions of a member when it receives a message from a Primary other than its current Primary 190. First, it checks whether the precedence of the new Primary is greater than its own precedence 192. If the precedence of the new Primary is greater than its own precedence, the member leaves the membership 200, waits for the membership to stabilize 202, starts the membership application timeout 204, multicasts an application for membership 206 and exits 208.

[0175] If the precedence of the new Primary is less than or equal to its own precedence, the member checks whether the precedence of the new Primary is greater than the precedence of the current Primary 194. If the precedence of the new Primary is greater than the precedence of the current Primary, the member requests retransmission of the announcement of the new membership by the new Primary 196 and exits 208.

[0176] If the precedence of the new Primary is less than or equal to the precedence of the current Primary, the member ignores the message 198 and exits 208.

[0177] The following general steps are performed on reception of a message from a Primary other than the current Primary:

[0178] if precedence of new Primary>myPrecedence

• • [0179] leave membership
  • [0180] wait for the membership to stabilize
  • [0181] start membership application timeout
  • [0182] multicast application for membership

[0183] else

• • [0184] if precedence of new Primary>precedence of currentPrimary
    • [0185] request retransmission of announcement of
      • [0186] new membership
  • [0187] else
    • [0188] ignore message

[0189] FIG. 9 is a flow diagram that shows the actions of an applicant when a membership application timeout expires 210. The applicant starts the membership application timeout 212, multicasts the application for membership 214 and exits 216.

[0190] The following general steps are performed on expiration of membership application timeout:

[0191] start membership application timeout

[0192] multicast application for membership

[0193] The above description includes example scenarios and flowcharts for an embodiment of the present invention to describe general operation of the present invention. It should be appreciated that the invention may be implemented with different programming by one of ordinary skill in the art, with the system capable of providing fault tolerance in a wide variety of circumstances (scenarios) without departing from the teachings of the present invention.

[0194] Although the description above contains many details, these should not be construed as limiting the scope of the invention but as merely providing illustrations of some of the presently preferred embodiments of this invention. Therefore, it will be appreciated that the scope of the present invention fully encompasses other embodiments which may become obvious to those skilled in the art, and that the scope of the present invention is accordingly to be limited by nothing other than the appended claims, in which reference to an element in the singular is not intended to mean “one and only one” unless explicitly so stated, but rather “one or more.” All structural and functional equivalents to the elements of the above-described preferred embodiment that are known to those of ordinary skill in the art are expressly incorporated herein by reference and are intended to be encompassed by the present claims. Moreover, it is not necessary for a device or method to address each and every problem sought to be solved by the present invention, for it to be encompassed by the present claims. Furthermore, no element, component, or method step in the present disclosure is intended to be dedicated to the public regardless of whether the element, component, or method step is explicitly recited in the claims. No claim element herein is to be construed under the provisions of 35 U.S.C. 112, sixth paragraph, unless the element is expressly recited using the phrase “means for.”