# US 2023/0069165 A1 · Byzantine fault tolerant pre-preprocessing for state machine replication

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

- Number: US 2023/0069165 A1
- Document ID: US20230069165A1
- Status: Published application
- Kind: A1
- Application number: 17/465,830
- Filed: 2021-09-02
- Published: 2023-03-02
- Earliest claimed: 2021-09-02
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Teodor PARVANOV; Ittai ABRAHAM; Kashfat Khan; Yulia SHERMAN; Yehonatan BUCHNIK
- Web page: https://patentgrep.com/patent/US20230069165A1

## CPC

- G06F 9/4498: {Finite state machines}
- G06F 9/466: {Transaction processing}
- G06F 16/27: Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
- H04L 9/3247: {involving digital signatures}
- H04L 9/50: {using hash chains, e.g. blockchains or hash trees}
- H04L 67/1095: Replication or mirroring of data, e.g. scheduling or transport for data synchronisation between network nodes
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

In some embodiments, a first replica sends a message to second replicas for pre-processing of an operation. The first replica receives pre-processing results from the second replicas. A pre-processing result is generated by pre-processing the operation using a first state. The first replica analyzes the pre-processing results to determine whether an agreement on a validated pre-processing result is received. When it is determined the agreement on the validated pre-processing result is received, the first replica performs a consensus protocol stage with the second replicas to order the request in an order of execution of requests that defines when to execute the request with respect to another request at the second replicas. Information for the validated pre-processing result is provided to the set of second replicas to determine whether contention results between the first state and a second state that is based on the order of execution of requests.

## Claims

### Claim 1

A method for pre-processing a request for an operation in a state machine replication system comprising N replicas, the method comprising:
sending, by a first replica to a set of second replicas, a message for pre-processing of the operation;
receiving, by the first replica, a set of pre-processing results from at least a portion of the set of second replicas, wherein a pre-processing result for a respective second replica is generated by pre-processing the operation using a first state maintained by the respective second replica;
analyzing, by the first replica, the set of pre-processing results from the at least the portion of the set of second replicas to determine whether an agreement on a validated pre-processing result is received; and
when it is determined the agreement on the validated pre-processing result is received, performing, by the first replica, a consensus protocol stage with the set of second replicas to order the request in an order of execution of requests that defines when to execute the request with respect to another request at the set of second replicas, wherein information for the validated pre-processing result is provided to the set of second replicas to determine whether contention results between the first state maintained by the respective second replica and a second state maintained by a respective second replica that is based on the order of execution of requests.

### Claim 2 (depends on 1)

The method of claim 1, wherein analyzing the set of pre-processing results to determine whether the agreement on the validated pre-processing result is received comprises:
validating that a specified number of the pre-processing results in the set of pre-processing results are identical to one another.

### Claim 3 (depends on 1)

The method of claim 1, wherein analyzing the set of pre-processing results to determine whether the agreement on the validated pre-processing result is received occurs before sending a message to start the consensus protocol stage.

### Claim 4 (depends on 1)

The method of claim 1, further comprising:
including the validated pre-processing result and signatures from second replicas in the at least the portion of the set of second replicas that generated the validated pre-processed result in a message that is sent to the set of second replicas during performance of the consensus protocol stage.

### Claim 5 (depends on 1)

The method of claim 1, further comprising:
generating, by the first replica, a pre-processing result by pre-processing the operation using a first state maintained by the first replica;
when it is determined the agreement on the validated pre-processing result is received, determining, by the first replica, whether contention results between the first state maintained by the first replica and a second state maintained by the first replica that is based on the order of execution of requests; and
when the contention does not result, updating the second state maintained by the first replica to reflect the execution of the operation using the validated pre-processing result.

### Claim 6 (depends on 5)

The method of claim 5, further comprising:
when the contention results, performing an action based on contention resulting without updating the second state maintained by the first replica to reflect the execution of the operation using the validated pre-processing result.

### Claim 7 (depends on 1)

The method of claim 1, further comprising:
when it is determined the agreement on the validated pre-processing result is not received, determining whether to retry sending of the message to pre-process the operation.

### Claim 8

A non-transitory computer-readable storage medium containing instructions for pre-processing a request for an operation in a state machine replication system comprising N replicas, wherein the instructions, when executed, control a computer system to be operable for:
sending, by a first replica to a set of second replicas, a message for pre-processing of the operation;
receiving, by the first replica, a set of pre-processing results from at least a portion of the set of second replicas, wherein a pre-processing result for a respective second replica is generated by pre-processing the operation using a first state maintained by the respective second replica;
analyzing, by the first replica, the set of pre-processing results from the at least the portion of the set of second replicas to determine whether an agreement on a validated pre-processing result is received; and
when it is determined the agreement on the validated pre-processing result is received, performing, by the first replica, a consensus protocol stage with the set of second replicas to order the request in an order of execution of requests that defines when to execute the request with respect to another request at the set of second replicas, wherein information for the validated pre-processing result is provided to the set of second replicas to determine whether contention results between the first state maintained by the respective second replica and a second state maintained by a respective second replica that is based on the order of execution of requests.

### Claim 9 (depends on 8)

The non-transitory computer-readable storage medium of claim 8,
wherein analyzing the set of pre-processing results to determine whether the agreement on the validated pre-processing result is received comprises:
validating that a specified number of the pre-processing results in the set of pre-processing results are identical to one another.

### Claim 10 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, wherein analyzing the set of pre-processing results to determine whether the agreement on the validated pre-processing result is received occurs before sending a message to start the consensus protocol stage.

### Claim 11 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, further operable for:
including the validated pre-processing result and signatures from second replicas in the at least the portion of the set of second replicas that generated the validated pre-processed result in a message that is sent to the set of second replicas during performance of the consensus protocol stage.

### Claim 12 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, further operable for:
generating, by the first replica, a pre-processing result by pre-processing the operation using a first state maintained by the first replica;
when it is determined the agreement on the validated pre-processing result is received, determining, by the first replica, whether contention results between the first state maintained by the first replica and a second state maintained by the first replica that is based on the order of execution of requests; and
when the contention does not result, updating the second state maintained by the first replica to reflect the execution of the operation using the validated pre-processing result.

### Claim 13 (depends on 12)

The non-transitory computer-readable storage medium of claim 12, further operable for:
when the contention results, performing an action based on contention resulting without updating the second state maintained by the first replica to reflect the execution of the operation using the validated pre-processing result.

### Claim 14 (depends on 8)

The non-transitory computer-readable storage medium of claim 8, further operable for:
when it is determined the agreement on the validated pre-processing result is not received, determining whether to retry sending of the message to pre-process the operation.

### Claim 15

A method for pre-processing a request for an operation in a state machine replication system comprising N replicas, the method comprising:
receiving, by a first replica, a message from a second replica in a consensus protocol stage to order the request in an order of execution of requests that defines when to execute the request with respect to another request at the first replica;
determining, by the first replica, information for a pre-processing result of the operation from the message;
performing, by the first replica, a validation of the information for the pre-processing result to determine whether the consensus protocol stage should continue for the request; and
when the consensus protocol stage should continue for the request, performing, by the first replica, the consensus protocol stage to order the request in the order of execution of requests.

### Claim 16 (depends on 15)

The method of claim 15, further comprising:
receiving a pre-processing request;
pre-processing the operation to generate a pre-processing result by pre-processing the operation using a first state maintained by the first replica; and
sending information for the pre-processing result to the second replica.

### Claim 17 (depends on 16)

The method of claim 16, further comprising:
after determining the order of the request in the order of execution of requests, determining, by the first replica, whether contention results between the first state maintained by the first replica and a second state maintained by the first replica that is based on the order of execution of requests.

### Claim 18 (depends on 17)

The method of claim 17, further comprising:
when the contention does not result, updating the second state maintained the first replica to reflect the execution of the operation using the pre-processing result.

### Claim 19 (depends on 17)

The method of claim 17, further comprising:
when the contention results, performing an action based on contention resulting without updating the second state maintained by the first replica to reflect the execution of the operation using the validated pre-processing result.

### Claim 20 (depends on 15)

The method of claim 15, wherein performing the validation of the information comprises:
determining if a pre-processing result in the information for the pre-processing result is a same result as that generated when pre-processing the operation at the first replica; and
validating a set of signatures from a set of replicas in the information for the pre-processing.

### Claim 21 (depends on 15)

The method of claim 15, further comprising:
when the consensus protocol stage should not continue for the request, entering a procedure to indicate a replica is faulty in the state machine replication system.
