ASYNCHRONOUS BOOSTING OF STATE MACHINE REPLICATION
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
.