# US 2012/0254412 A1 · Replicated state machine utilizing view change protocol resilient to performance attacks

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2012/0254412 A1
- Document ID: US20120254412A1
- Status: Published application
- Kind: A1
- Application number: 13/422,258
- Filed: 2012-03-16
- Published: 2012-10-04
- Earliest claimed: 2011-03-28
- Assignees: Siemens Aktiengesellschaft
- Inventors: Stuart Goose; Jonathan Kirsch
- Web page: https://patentgrep.com/patent/US20120254412A1

## CPC

- G06F 9/5072: {Grid computing}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

A network of replicated servers providing a service includes a plurality of server replicas. A leader is elected from among the plurality of server replicas for coordinating ordering of operations among the plurality of server replicas. A view change protocol is executed by the plurality of server replicas after the election of the leader. Each iteration of the view change protocol corresponds to a unique view number. The server replicas are directed by the view change protocol to cooperate to order operations by exchange of information associated with particular view numbers. The information is prioritized in accordance with the view numbers. The non-leaders monitor the response time of the leader and 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.

## Claims

### Claim 1

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.

### Claim 2 (depends on 1)

The network of replicated servers of claim 1, wherein the operations whose order is coordinated by the leader include client queries or requests to be processed by the server replicas.

### Claim 3 (depends on 1)

The network of replicated servers of claim 1, wherein the state of each of the server replicas is dependent upon what operations were executed by the respective server replica or in what order those operations were executed in.

### Claim 4 (depends on 1)

The network of replicated servers of claim 1, wherein the server replicas execute a checkpoint protocol for enabling the server replicas to generate provably-correct checkpoints of their state and then discard messages used to order operations reflected within the state.

### Claim 5 (depends on 4)

The network of replicated servers of claim 4, wherein the states broadcast by the server replicas include a most recently-acquired checkpoint and the server replicas determine that they have received the sufficient number of states that were broadcast by the sufficiently large subset of the plurality of server replicas when they have received matching states from a set of 2f+1 server replicas.

### Claim 6 (depends on 1)

The network of replicated servers of claim 1, wherein the leader broadcasts the selection of the official state to the non-leaders without broadcasting the official state itself.

### Claim 7 (depends on 1)

The network of replicated servers of claim 1, wherein prioritizing the information in accordance with particular view numbers includes using only ordering information, for particular operations, having a highest available view number and disregarding ordering information, for particular operations, where a view number is lower than that of other available ordering information.

### Claim 8 (depends on 1)

The network of replicated servers of claim 1, wherein the 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 is finite and measurable with respect to network conditions when the leader is functioning correctly.

### Claim 9 (depends on 8)

The network of replicated servers of claim 8, wherein the network conditions are assessed by the server replicas by monitoring roundtrip times of messages sent to each other.

### Claim 10 (depends on 1)

The network of replicated servers of claim 1, wherein the information prioritized in accordance with said view numbers is bounded to a particular quantity when the server replicas experience cascading failures.

### Claim 11 (depends on 1)

The network of replicated servers of claim 1, wherein the view change protocol is tolerant of up to a number f of the server replicas experiencing Byzantine faults where the total number of server replicas is at least 3f+1.

### Claim 12

A method for performing view change in a system of replicated servers providing a service, comprising:
executing a view change protocol after a leader is elected from among a 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, each iteration of the view change protocol corresponding to a unique view number;
broadcasting server replica states, from each server replica, and determining when a sufficient number of server replicas have received states that were broadcasted by a sufficiently large subset of the plurality of server replicas by the exchange of information between the non-leaders;
informing 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;
selecting an official state from among the states broadcast by the server replicas and broadcasting the selection of the official state to the non-leaders;
cooperating among the server replicas to agree upon the official state selected by the leader and 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
monitoring 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 executing 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.

### Claim 13 (depends on 12)

The method of claim 12, additionally comprising:
directing 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.

### Claim 14 (depends on 12)

The method of claim 12, wherein the operations whose order is coordinated by the leader include client queries or requests to be processed by the server replicas.

### Claim 15 (depends on 12)

The method of claim 12, wherein the state of each of the server replicas is dependent upon what operations were executed by the respective server replica or in what order those operations were executed in.

### Claim 16 (depends on 12)

The method of claim 12, wherein the server replicas execute a checkpoint protocol for enabling the server replicas to generate provably-correct checkpoints of their state and then discard messages used to order operations reflected within the state.

### Claim 17 (depends on 12)

The method of claim 12, wherein prioritizing the information in accordance with particular view numbers includes using only ordering information, for particular operations, having a highest available view number and disregarding ordering information, for particular operations, where a view number is lower than that of other available ordering information.

### Claim 18 (depends on 12)

The method of claim 12, wherein the 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 is finite and measurable with respect to network conditions when the leader is functioning correctly.

### Claim 19 (depends on 18)

The method of claim 18, wherein the network conditions are assessed by the server replicas by monitoring roundtrip times of messages sent to each other.

### Claim 20 (depends on 12)

The method of claim 12, wherein the information prioritized in accordance with said view numbers is bounded to a particular quantity when the server replicas experience cascading failures

### Claim 21 (depends on 12)

The method of claim 12, wherein the view change protocol is tolerant of up to a number f of the server replicas experiencing Byzantine faults where the total number of server replicas is at least 3f+1.

### Claim 22

A network of replicated servers providing a service, comprising:
a plurality of server replicas;
a leader elected from 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,
wherein the view change protocol:
directs each server replica to cooperate with the other server replicas to determine information pertaining to the state of the server replicas and to send said information pertaining to the state of the server replicas to the leader;
directs the leader to select an official state using the information pertaining to the state of the server replicas received from the server replicas and to transmit the selection of the official state to the non-leaders;
directs each server replica to cooperate with the other server replicas to order operations not ordered as part of the official state; and
directs the non-leaders to monitor a length of time between when the non-leader sends said information pertaining to the state of the server replicas to the leader and when the selection of the official state is received from the leader, and 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.
