# US 2019/0377645 A1 · Linear View-Change BFT with Optimistic Responsiveness

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

- Number: US 2019/0377645 A1
- Document ID: US20190377645A1
- Status: Published application
- Kind: A1
- Application number: 16/234,552
- Filed: 2018-12-27
- Published: 2019-12-12
- Earliest claimed: 2018-06-11
- Assignees: VMware, Inc.
- Applicants: VMware, Inc.
- Inventors: Ittai Abraham; Dahlia Malkhi; Guy Golan Gueta; Maofan Yin; Michael Reiter
- Web page: https://patentgrep.com/patent/US20190377645A1

## CPC

- G06F 11/1482: using middleware or operating system [OS] functionalities
- G06F 11/0757: {by exceeding a time limit, i.e. time-out, e.g. watchdogs}
- G06F 11/182: {based on mutual exchange of the output between redundant processing components}
- G06F 11/183: {by voting, the voting not being performed by the redundant components}
- G06F 11/187: {Voting techniques}
- G06F 2201/82: Solving problems relating to consistency
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

Techniques for implementing linear view-change with optimistic responsiveness in a BFT protocol running on a distributed system comprising n replicas are provided. According to one set of embodiments, the replicas can execute, during a view v of the BFT protocol, a first voting round comprising communicating instances of a first type of COMMIT certificate among the replicas. Further, when 2f+1 instances of the first type of COMMIT certificate associated with view v have been received by the replicas, the replicas can execute a second voting round comprising communicating instances of a second type of COMMIT certificate among the replicas. If 2f+1 instances of the second type of COMMIT certificate associated with view v are not received by the replicas within a predetermined timeout period, a view change can be initiated from view v to a view v+1.

## Claims

### Claim 1

A method for implementing linear view-change with optimistic responsiveness in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than f of the n replicas are faulty, and wherein the BFT protocol enables at least 2f+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising:
executing, by the n replicas during a view v of the BFT protocol, a first voting round comprising communicating instances of a first type of COMMIT certificate among the n replicas;
when 2f+1 instances of the first type of COMMIT certificate associated with the view v have been received by the n replicas, executing a second voting round comprising communicating instances of a second type of COMMIT certificate among the n replicas; and
if 2f+1 instances of the second type of COMMIT certificate associated with the view v are not received by the n replicas within a predetermined timeout period, initiating a view-change from the view v to a view v+1.

### Claim 2 (depends on 1)

The method of claim 1 wherein initiating the view-change comprises:
generating, by a replica in the n replicas corresponding to a new proposer for the view v+1, a PREPARE message comprising a single instance of the first type of COMMIT certificate or the second type of COMMIT certificate, the single instance corresponding to an instance of the first type or the second type that has the highest view number the new proposer is aware of at the time of the view-change; and
transmitting, by the new proposer, the PREPARE message with the single instance of the first type of COMMIT certificate or the second type of COMMIT certificate to all other replicas in the n replicas.

### Claim 3 (depends on 2)

The method of claim 2 wherein the BFT protocol is Practical BFT and wherein executing the steps of claim 2 result in a linear reduction in communication bit complexity for the view-change over Practical BFT.

### Claim 4 (depends on 2)

The method of claim 2 wherein the single instance is one of an initial n-f instances of the first type or the second type received by the new proposer from other replicas in the n replicas.

### Claim 5 (depends on 1)

The method of claim 1 wherein if the single instance is an instance of the first type of COMMIT certificate, the single instance comprises 2f+1 PREPARE votes for a proposed sequence number for a service operation invoked by a client in the one or more clients, each PREPARE vote including a signed digest of the proposed sequence number, and
wherein if the single instance is an instance of the second type of COMMIT certificate, the single instance comprises 2f+1 COMMIT votes corresponding to the first type of COMMIT certificate.

### Claim 6 (depends on 2)

The method of claim 2 wherein, upon receiving the PREPARE message at a replica r, the replica r determines whether it already holds a lock on an instance of the second type of COMMIT certificate.

### Claim 7 (depends on 6)

The method of claim 6 wherein if the replica r already holds a lock on the instance of the second type of COMMIT certificate, the replica r releases the lock if the single instance included in the PREPARE message has a higher view number than the instance of the second type of COMMIT certificate.

### Claim 8

A non-transitory computer readable storage medium having stored thereon program code embodying a method for implementing linear view-change with optimistic responsiveness in a Byzantine Fault Tolerant (BFT) protocol running on a distributed system comprising n replicas, wherein no more than f of the n replicas are faulty, and wherein the BFT protocol enables at least 2f+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the method comprising:
executing, by the n replicas during a view v of the BFT protocol, a first voting round comprising communicating instances of a first type of COMMIT certificate among the n replicas;
when 2f+1 instances of the first type of COMMIT certificate associated with the view v have been received by the n replicas, executing a second voting round comprising communicating instances of a second type of COMMIT certificate among the n replicas; and
if 2f+1 instances of the second type of COMMIT certificate associated with the view v are not received by the n replicas within a predetermined timeout period, initiating a view-change from the view v to a view v+1.

### Claim 9 (depends on 8)

The non-transitory computer readable storage medium of claim 8 wherein initiating the view-change comprises:
generating, by a replica in the n replicas corresponding to a new proposer for the view v+1, a PREPARE message comprising a single instance of the first type of COMMIT certificate or the second type of COMMIT certificate, the single instance corresponding to an instance of the first type or the second type that has the highest view number the new proposer is aware of at the time of the view-change; and
transmitting, by the new proposer, the PREPARE message with the single instance of the first type of COMMIT certificate or the second type of COMMIT certificate to all other replicas in the n replicas.

### Claim 10 (depends on 9)

The non-transitory computer readable storage medium of claim 9 wherein the BFT protocol is Practical BFT and wherein executing the steps of claim 9 result in a linear reduction in communication bit complexity for the view-change over Practical BFT.

### Claim 11 (depends on 9)

The non-transitory computer readable storage medium of claim 9 wherein the single instance is one of an initial n-f instances of the first type or the second type received by the new proposer from other replicas in the n replicas.

### Claim 12 (depends on 8)

The non-transitory computer readable storage medium of claim 8 wherein if the single instance is an instance of the first type of COMMIT certificate, the single instance comprises 2f+1 PREPARE votes for a proposed sequence number for a service operation invoked by a client in the one or more clients, each PREPARE vote including a signed digest of the proposed sequence number, and
wherein if the single instance is an instance of the second type of COMMIT certificate, the single instance comprises 2f+1 COMMIT votes corresponding to the first type of COMMIT certificate.

### Claim 13 (depends on 9)

The non-transitory computer readable storage medium of claim 9 wherein, upon receiving the PREPARE message at a replica r, the replica r determines whether it already holds a lock on an instance of the second type of COMMIT certificate.

### Claim 14 (depends on 13)

The non-transitory computer readable storage medium of claim 13 wherein if the replica r already holds a lock on the instance of the second type of COMMIT certificate, the replica r releases the lock if the single instance included in the PREPARE message has a higher view number than the instance of the second type of COMMIT certificate.

### Claim 15

A distributed system comprising:
n replicas; and
a non-transitory computer readable medium having stored thereon program code that, when executed, enables the distributed system to implement linear view-change with optimistic responsiveness in a Byzantine Fault Tolerant (BFT) protocol running on the distributed system, wherein no more than f of the n replicas are faulty, and wherein the BFT protocol enables at least 2f+1 of the n replicas to agree on how to sequence execution of a plurality of service operations originating from one or more clients, the program code causing the distributed system to:
execute, during a view v of the BFT protocol, a first voting round comprising communicating instances of a first type of COMMIT certificate among the n replicas;
when 2f+1 instances of the first type of COMMIT certificate associated with the view v have been received by the n replicas, execute a second voting round comprising communicating instances of a second type of COMMIT certificate among the n replicas; and
if 2f+1 instances of the second type of COMMIT certificate associated with the view v are not received by the n replicas within a predetermined timeout period, initiate a view-change from the view v to a view v+1.

### Claim 16 (depends on 15)

The distributed system of claim 15 wherein the program code that causes the distributed system to initiate the view-change comprises program code that causes the distributed system to:
generate, by a replica in the n replicas corresponding to a new proposer for the view v+1, a PREPARE message comprising a single instance of the first type of COMMIT certificate or the second type of COMMIT certificate, the single instance corresponding to an instance of the first type or the second type that has the highest view number the new proposer is aware of at the time of the view-change; and
transmit, by the new proposer, the PREPARE message with the single instance of the first type of COMMIT certificate or the second type of COMMIT certificate to all other replicas in the n replicas.

### Claim 17 (depends on 16)

The distributed system of claim 16 wherein the BFT protocol is Practical BFT and wherein executing the steps of claim 16 result in a linear reduction in communication bit complexity for the view-change over Practical BFT.

### Claim 18 (depends on 16)

The distributed system of claim 16 wherein the single instance is one of an initial n-f instances of the first type or the second type received by the new proposer from other replicas in the n replicas.

### Claim 19 (depends on 15)

The distributed system of claim 15 wherein if the single instance is an instance of the first type of COMMIT certificate, the single instance comprises 2f+1 PREPARE votes for a proposed sequence number for a service operation invoked by a client in the one or more clients, each PREPARE vote including a signed digest of the proposed sequence number, and wherein if the single instance is an instance of the second type of COMMIT certificate, the single instance comprises 2f+1 COMMIT votes corresponding to the first type of COMMIT certificate.

### Claim 20 (depends on 16)

The distributed system of claim 16 wherein, upon receiving the PREPARE message at a replica r, the replica r determines whether it already holds a lock on an instance of the second type of COMMIT certificate.

### Claim 21 (depends on 20)

The distributed system of claim 20 wherein if the replica r already holds a lock on the instance of the second type of COMMIT certificate, the replica r releases the lock if the single instance included in the PREPARE message has a higher view number than the instance of the second type of COMMIT certificate.
