Method and apparatus for distributed agreement on processor membership

Abstract

An apparatus and protocol to determine the group of processors that will survive communications faults and/or timed-event failures in a multiprocessor system. The processors each have a respective memory, and the processors are coupled by means of an inter-processor communication network. The processors detect that the set of processors with which they can communicate has changed. They can choose to either halt or continue operations based on minimizing the likelihood that disconnected groups of processors will continue to operate as independent systems. The processors construct a connectivity matrix on the initiation of a regroup operation. The connectivity information is used to ensure that all the processors in the final group that survives can communicate with all other processors in the group. One or more processors may halt to achieve this characteristic. A processor is suspected of having ceased operations or having a failed timer mechanism when other processors detect the absence of a periodic message from the processor. When this happens, all of the processors are subjected to a series of stages in which they repeatedly broadcast their status and connectivity to each other. The suspected processor does not advance through the stages if it has ceased operations or if its timer mechanism has failed.