Patent ID: 8549142

Claim:
A network of replicated servers providing a service, comprising: a plurality of server replicas; a leader elected from among the plurality of server replicas in accordance with a leader election protocol for coordinating ordering of operations among the plurality of server replicas, the remainder of the plurality of server replicas being non-leaders; and a view change protocol executed by the plurality of server replicas after the election of the leader, each iteration of the view change protocol corresponding to a unique view number, wherein the view change protocol: directs each server replica to broadcast its own state and to cooperate with the other server replicas to determine when a sufficient number of server replicas have received states that were broadcasted by a sufficiently large subset of the plurality of server replicas; directs each non-leader to inform the leader when it is determined that the sufficient number of server replicas have received states that were broadcasted by the sufficiently large subset of the plurality of server replicas; directs the leader to select an official state from among the states broadcast by the server replicas and broadcast the selection of the official state to the non-leaders; directs each server replica to agree on the official state selected by the leader; directs each server replica to cooperate with the other server replicas to order operations not ordered as part of the official state, said cooperation including the exchange of information associated with particular view numbers, wherein said information is prioritized in accordance with said view numbers; and directs the non-leaders to monitor a length of time between when the non-leader informs the leader that the sufficient number of server replicas have received states that were broadcasted by the sufficiently large subset of the plurality of server replicas and when knowledge of the official state has been received by the non-leader, and to execute the leader election protocol to elect a new leader when it is determined that the monitored length of time is greater than a threshold value that is dependent upon current network conditions.