Asynchronous boosting of state machine replication

Abstract

An asynchronous state machine replication solution in a system of replicas includes executing multiple instances of a consensus protocol, referred to as leader-based views (LBVs) in each replica, where each replica is a leader participant in one of the LBV instances. Each replica drives a decision based on the consensus being reached among the LBV instances, rather than relying the expiration of timers and view changes to drive progress.

1 . A method comprising:
 signaling, by a computer system, a first notification to n servers, wherein the first notification causes the n servers to initiate n concurrent instances of a consensus protocol for a current view of the consensus protocol;   in response to signaling the first notification, receiving, by the computer system, at least n-f second notifications from the n servers, wherein f is a maximum number of faulty servers tolerated by the consensus protocol, and wherein each second notification indicates that a server in the n servers has reached consensus in a quorum of the n concurrent instances;   upon receiving the at least n-f second notifications, signaling, by the computer system, a third notification to the n servers, wherein the third notification causes the n servers to elect a leader from among the n servers; and   in response to signaling the third notification, receiving, by the computer system, at least n-f fourth notifications from the n servers, wherein each fourth notification includes information regarding the elected leader.   
     
     
         2 . The method of  claim 1  wherein each server in the n servers acts as a leader participant in exactly one instance in the n concurrent instances and acts as a non-leader participant in other instances in the n concurrent instances. 
     
     
         3 . The method of  claim 1  further comprising:
 upon receiving the at least n-f fourth notifications, signaling a fifth notification to the n servers, wherein the fifth notification identifies an instance in the n concurrent instances where the elected leader was acting as a leader participant. 
 
     
     
         4 . The method of  claim 3  further comprising:
 in response to signaling the fifth notification, receiving a closing state for the instance from the elected leader, the closing state including a decision value. 
 
     
     
         5 . The method of  claim 4  further comprising:
 upon determining that the decision value is not a safe value, returning the decision value as a decided value for the current view. 
 
     
     
         6 . The method of  claim 4  further comprising:
 upon determining that the decision value is the safe value, signaling the first notification to the n servers again to initiate another n concurrent instances for a next view; and 
 providing to the n servers the closing state as an input state for said another n concurrent instances. 
 
     
     
         7 . The method of  claim 1  wherein the elected leader is a leader participant of a successfully completed instance in the n concurrent instances with a probability of 
       
         
           
             
               
                 
                   f 
                   + 
                   1 
                 
                 n 
               
               . 
             
           
         
       
     
     
         8 . A non-transitory computer-readable storage medium having stored thereon program code that, when executed by a computer system, causes the computer system to:
 signal a first notification to n servers, wherein the first notification causes the n servers to initiate n concurrent instances of a consensus protocol for a current view of the consensus protocol;   in response to signaling the first notification, receive at least n-f second notifications from the n servers, wherein f is a maximum number of faulty servers tolerated by the consensus protocol, and wherein each second notification indicates that a server in the n servers has reached consensus in a quorum of the n concurrent instances;   upon receiving the at least n-f second notifications, signal a third notification to the n servers, wherein the third notification causes the n servers to elect a leader from among the n servers; and   in response to signaling the third notification, receive at least n-f fourth notifications from the n servers, wherein each fourth notification includes information regarding the elected leader.   
     
     
         9 . The non-transitory computer-readable storage medium of  claim 8  wherein each server in the n servers acts as a leader participant in exactly one instance in the n concurrent instances and acts as a non-leader participant in other instances in the n concurrent instances. 
     
     
         10 . The non-transitory computer-readable storage medium of  claim 8  wherein the program code further causes the computer system to:
 upon receiving the at least n-f fourth notifications, signal a fifth notification to the n servers, wherein the fifth notification identifies an instance in the n concurrent instances where the elected leader was acting as a leader participant. 
 
     
     
         11 . The non-transitory computer-readable storage medium of  claim 10  wherein the program code further causes the computer system to:
 in response to signaling the fifth notification, receive a closing state for the instance from the elected leader, the closing state including a decision value. 
 
     
     
         12 . The non-transitory computer-readable storage medium of  claim 11  wherein the program code further causes the computer system to:
 upon determining that the decision value is not a safe value, return the decision value as a decided value for the current view. 
 
     
     
         13 . The non-transitory computer-readable storage medium of  claim 11  wherein the program code further causes the computer system to:
 upon determining that the decision value is the safe value, signal the first notification to the n servers again to initiate another n concurrent instances for a next view; and 
 provide to the n servers the closing state as an input state for said another n concurrent instances. 
 
     
     
         14 . The non-transitory computer-readable storage medium of  claim 8  wherein the elected leader is a leader participant of a successfully completed instance in the n concurrent instances with a probability of 
       
         
           
             
               
                 
                   f 
                   + 
                   1 
                 
                 n 
               
               . 
             
           
         
       
     
     
         15 . A computer system comprising:
 a processor; and   a computer-readable storage medium comprising instructions that cause the processor to:
 signal a first notification to n servers, wherein the first notification causes the n servers to initiate n concurrent instances of a consensus protocol for a current view of the consensus protocol; 
 in response to signaling the first notification, receive at least n-f second notifications from the n servers, wherein f is a maximum number of faulty servers tolerated by the consensus protocol, and wherein each second notification indicates that a server in the n servers has reached consensus in a quorum of the n concurrent instances; 
 upon receiving the at least n-f second notifications, signal a third notification to the n servers, wherein the third notification causes the n servers to elect a leader from among the n servers; and 
 in response to signaling the third notification, receive at least n-f fourth notifications from the n servers, wherein each fourth notification includes information regarding the elected leader. 
   
     
     
         16 . The computer system of  claim 15  wherein each server in the n servers acts as a leader participant in exactly one instance in the n concurrent instances and acts as a non-leader participant in other instances in the n concurrent instances. 
     
     
         17 . The computer system of  claim 15  wherein the instructions further cause the processor to:
 upon receiving the at least n-f fourth notifications, signal a fifth notification to the n servers, wherein the fifth notification identifies an instance in the n concurrent instances where the elected leader was acting as a leader participant. 
 
     
     
         18 . The computer system of  claim 17  wherein the instructions further cause the processor to:
 in response to signaling the fifth notification, receive a closing state for the instance from the elected leader, the closing state including a decision value. 
 
     
     
         19 . The computer system of  claim 18  wherein the instructions further cause the processor to:
 upon determining that the decision value is not a safe value, return the decision value as a decided value for the current view. 
 
     
     
         20 . The computer system of  claim 18  wherein the instructions further cause the processor to:
 upon determining that the decision value is the safe value, signal the first notification to the n servers again to initiate another n concurrent instances for a next view; and 
 provide to the n servers the closing state as an input state for said another n concurrent instances. 
 
     
     
         21 . The computer system of  claim 15  wherein the elected leader is a leader participant of a successfully completed instance in the n concurrent instances with a probability of 
       
         
           
             
               
                 
                   f 
                   + 
                   1 
                 
                 n 
               
               .