Linear view-change BFT with optimistic responsiveness
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.
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.
2. 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.
3. 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.
4. 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.
5. 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.
6. 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.
7. 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.
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.
9. 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.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
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.
16. 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.
17. 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.
18. 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.
19. 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.
20. 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.
21. 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.