Patent Publication Number: US-11641313-B2

Title: Asynchronous liveness boosting of state machine replication

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     Pursuant to 35 U.S.C. § 119(e), this application is entitled to and claims the benefit of the filing date of U.S. Provisional App. No. 62/938,695 filed Nov. 21, 2019, the content of which is incorporated herein by reference in its entirety for all purposes. 
    
    
     BACKGROUND 
     State Machine Replication (SMR) is a basic component in distributed computing for building fault-tolerant systems. An important aspect of every distributed fault-tolerant system is ensuring that all processes (nodes, servers) within the system arrive at the same conclusion. This is known as requiring “consensus” among parties (participants). A consensus protocol specifies a process among the distributed processes to achieve agreement on a proposed data value. A goal of a consensus protocol is to ensure that every transaction is replicated and recorded in all the machines in the network in the same order. A property of consensus protocols is referred to as “liveness.” A consensus protocol is said to be “live” if it is can process new transactions and valid transactions are eventually replicated and recorded. A liveness fault can occur, for example, when a transaction is omitted, information is withheld by a node, and so on. 
     A distributed system can be characterized as being synchronous, asynchronous, or partially synchronous. In a synchronous system, there is some maximum value (“upper bound”) on the time between when a node sends a message and when you can be certain that the receiving node hears the message. In an asynchronous system, messages can take arbitrarily long to reach the nodes and each node can take an arbitrary amount of time to respond. This includes “infinity” meaning that it takes forever for some event to occur. This model is important because it more accurately captures real-world implementations where nodes on the network can fail. In a partially synchronous system, the view is that messages will eventually reach a node. 
     With the emergence of cross organization Byzantine fault tolerant (BFT) systems, such as Blockchains, which maintain assets with high stake and devise to change the financial world, the assumption of partially synchronous communication may be no longer valid. For example, it is enough for an attacker to dynamically block one party at a time, e.g., through a denial of service, to prevent progress or fairness from leader-based consensus algorithms that are designed for the partially synchronous model (e.g., Practical BFT (PBFT) and Paxos). 
     In practice, building reliable systems via state machine replication (SMR) requires resilience against all network conditions, including malicious attacks. The best way to model such settings is by assuming asynchronous communication links. However, it is known that deterministic asynchronous SMR solutions are not possible. Two principal approaches are used to circumvent this result. The first approach expects partial synchrony, in which protocols are designed to guarantee safety under worst case network conditions, but are able to satisfy progress only during “long enough” periods of network synchrony. Although this approach is inherently vulnerable to network attacks and delays, it is commonly used in practice. In fact, most deployed systems, several of which have become de facto standards for building reliable systems (e.g., Paxos, PBFT), adopt this approach due to their speed during synchronous attack-free network periods, and their relative simplicity. The second approach employs randomization to guarantee eventual progress with probability 1 under all network conditions. However, although randomized asynchronous solutions are theoretically more robust, they are rarely deployed in practice due to their complexity and overhead, and are mostly the focus of theoretical academic work. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       With respect to the discussion to follow and in particular to the drawings, it is stressed that the particulars shown represent examples for purposes of illustrative discussion, and are presented in the cause of providing a description of principles and conceptual aspects of the present disclosure. In this regard, no attempt is made to show implementation details beyond what is needed for a fundamental understanding of the present disclosure. The discussion to follow, in conjunction with the drawings, makes apparent to those of skill in the art how embodiments in accordance with the present disclosure may be practiced. Similar or same reference numbers may be used to identify or otherwise refer to similar or same elements in the various drawings and supporting descriptions. In the accompanying drawings: 
         FIG.  1    is a high level representation of a system in accordance with the present disclosure. 
         FIG.  2    illustrates details of a framework for driving decisions in accordance with the present disclosure. 
         FIG.  3    shows operations performed by parties in a system to reach consensus in accordance with the present disclosure. 
         FIGS.  4 A and  4 B  show illustrative underlying consensus protocols (algorithms) that can be adapted in accordance with the present disclosure. 
         FIG.  5    illustrates processing by a party to generate a DONE notification. 
         FIG.  6    shows an illustrative example of the framework mechanism. 
         FIG.  7    shows operations of the framework mechanism in accordance with the present disclosure. 
         FIG.  8    illustrates processing in the framework mechanism to generate a READY notification. 
         FIG.  9    is an illustrative example of a computer system adapted to operate in accordance with the present disclosure. 
     
    
    
     DETAILED DESCRIPTION 
     In practice, building reliable systems via state machine replication (SMR) requires resilience against all network conditions, including failed nodes, failed communication links, malicious attacks, and so on. A common approach to modelling such settings is by assuming asynchronous communication, which represents a worst-case communication scenario. The present disclosure describes a control mechanism referred to as “the framework” for the design of fault tolerant SMR systems. The framework includes a leader-based-view (LBV) component that encapsulates the core logic of a leader-based view-by-view consensus paradigm (the view implementation) designed for the partially synchronous communication model, and makes a non-trivial use of it in order to boost liveness of existing SMR solutions. The framework hides any model assumptions that a specific SMR implementation might have, including the ratio of faulty to correct parties and types of faulty parties, as long as it provides the properties required by the LBV abstraction. For example, when instantiated with a partially synchronous consensus algorithm (protocol) designed to tolerate crash failures, e.g., Paxos and Raft, the framework of the present disclosure yields an asynchronous SMR for n=2f+1 parties, where n refers to the number of participants (parties, replicas, nodes, etc.) that participate in the protocol and f is the number of participants that can fail or otherwise be compromised. If the underlying consensus protocol is a byzantine solution like PBFT or HotStuff, the framework yields an asynchronous byzantine SMR for n=3f+1 parties. 
     Processing in accordance with the present disclosure can provide liveness boosting by controlling the view-change trigger via a wave mechanism. Rather than using timers, the wave mechanism uses an application programming interface (API) provided by the LBV component to generically rearrange view-by-view protocols in a way that allows progress at network speed. The wave mechanism is based on a property that all view-by-view protocols share, namely if the leader of a view is correct and timers never expire, then eventually a decision will be made in this view. Given this property, a wave operate as follows: Instead of running one LBV instance (as view-by-view protocols do), a wave runs n LBV instances (the leader-based phase) simultaneously, each with a distinct designated leader. Then, the wave performs a barrier synchronization in which parties wait until a quorum of the instances have reached a decision. As noted above, all instances with correct leaders eventually decide so eventually the barrier synchronization is reached. 
     As used herein “correct” is a technical term in the art of consensus algorithms. A correct party, for example, is a party that does not experience failure, is not compromised, does not behave maliciously, and so on. 
     After the barrier is reached, one LBV instance is selected unpredictably and uniformly at random. The chosen instance “wins,” and all other instances are ignored. Then, parties (participants) invoke the view-change phase in the chosen instance (only). The view-change phase here has two purposes. First, it boosts termination. If the chosen instance has reached a decision, meaning that a significantly large quorum of parties decided, then all correct parties learn this decision during the view-change phase. Otherwise, if the chosen instance has not reached a decision, as in every view-by-view protocol, the view-change phase ensures safety by making sure the leaders of the next wave can only propose safe values. The next wave enacts n new LBV instances, each one with a different leader that proposes a value according to the information returned from the view-change phase of the chosen instance of the previous wave. Note that since parties wait for a quorum of LBVs to reach a decision in each wave before randomly choosing one, the chosen LBV instance has a constant probability of having a decision, hence, together with the termination boosting provided by the viewchange phase, we get progress, in expectation, in a constant number of waves. 
     The framework of the present disclosure can take any view-by-view protocol designed for the partially synchronous model and transform it into an asynchronous solution. Meaning that the framework can turn any protocol that is safe under asynchrony into a protocol that also guarantees eventual progress. An aspect of the framework is fairness. The election mechanism of the framework provides an equal chance for all correct parties to drive decisions during synchrony, and optimally bounds the probability to decide a value proposed by a correct party during asynchrony. Another aspect of the framework is its model indifference, namely the framework does not add any model assumptions to the assumptions made by the underlying consensus protocol. For example, when the underlying consensus protocol is a BFT protocol such as PBFT we get an asynchronous byzantine state machine replication. Likewise, when the underlying consensus protocol is a crash-failure solution like Paxos or Raft we get the first asynchronous SMR system tolerating any minority of failures. 
     In the following description, for purposes of explanation, numerous examples and specific details are set forth in order to provide a thorough understanding of embodiments of the present disclosure. Particular embodiments as expressed in the claims may include some or all of the features in these examples, alone or in combination with other features described below, and may further include modifications and equivalents of the features and concepts described herein. 
       FIG.  1    shows a system  100  for distributed state machine replication (SMR) in accordance with the present disclosure. Some aspects of a conventional SMR are described to provide context for the present disclosure. Nodes (e.g., servers)  102  simulate a state machine in a fault tolerant manner. Clients  12  send commands as if there is a single state machine. Maintaining a single state machine in a single, however, is prone to crashes or Byzantine faults. Thus, instead of maintaining a single node, system  100  uses multiple nodes  102 , sometimes referred to as replicas, with the expectation that some of them can be faulty. The group of nodes presents the same interface as that of a single node to the client. 
     Nodes (also referred to as replicas)  102  all initially start with the same state. However, when they receive concurrent requests from a client  12 , honest replicas first need to agree on the sequence of client commands received by them. This problem is called log replication, and it is a multi-shot version of consensus; “single-shot” refers to reaching consensus on a single command, whereas “multi-shot” refers to reaching consensus on a sequence of commands on command at a time. After the sequence is agreed upon, the nodes can apply the commands in the shared log, one by one to recreate the system state. All honest replicas maintain an identical state at all times. 
     A goal of system  100  is to guarantee the following:
         Safety—This means that any two honest replicas will store the same sequence of commands in their logs.   Liveness—This means that honest server replicas will eventually execute a command proposed by a client.       

     Just to illustrate with a specific example, a commonly known application of SMR is the blockchain, which is the underlying mechanism for Bitcoin. A blockchain is a monotonically increasing list of records (or blocks) that are linked together using cryptographic techniques. Blocks consist of valid transactions that are hashed and encoded. Each block contains a cryptographic hash of the previous block in the chain. Core to the blockchain is the notion of a ledger, an unalterable, append-only log of the transactions that take place across various entities. To maintain the integrity of the ledger, the various entities need a way to “agree” (i.e., to reach consensus) on which set of blocks (transaction) are to be appended to the ledger. One or more faulty nodes can skew the outcome, resulting in consensus that is unachievable or incorrect. 
     Going forward in the present disclosure, the term “party” will be used interchangeably with nodes (replicas)  102 . Items to be agreed on (e.g., commands, blocks, etc.) will be referred to more generally as “values.” A node receives values (commands, block, etc.) from clients  12 , which are stored in the node&#39;s input queue  114  to be processed. Agreed upon values are stored in the node&#39;s output queue  116  (e.g., shared log, the ledger, etc.). 
     The example shown in  FIG.  1    comprises a network of four participating nodes (referred to herein as parties)  102 , although it will be appreciated that in other embodiments system  100  can comprise a larger number of parties. In accordance with the present disclosure, each party  102  can execute a consensus protocol in accordance with framework mechanism  106  (referred to herein as framework  106 , or simply the framework). Each party  102  can exchange leader-based view (LBV) messages  104  with each other. LBV messages  104  can include messages that relate to the execution of the underlying consensus protocol itself, and messages that relate to operation of the framework mechanism. 
     The framework mechanism provides asynchronous boosting that is model agnostic and applicable to a consensus leader-based view-by-view protocols designed for the partially synchronous communication model, such as PBFT, Paxos, and HotStuff for example. Consensus protocols that follow the leader-based view-by-view paradigm divide executions into a sequence of views, each with a designated leader. Each view is then further divided into two phases. First, the leader-based phase in which the designated leader tries to drive progress by getting all parties to commit its value. Then, when parties suspect that the leader is faulty, whether it is really faulty or due to asynchrony or network attacks, they start the view-change phase in which they exchange information to safely wedge the current view and move to the next one. 
     The leader-based view (LBV) is an abstraction that encapsulates the core logic of every view and provides an API that allows de-coupling of the leader-based phase from the view-change phase. In the partial synchrony approach, view-change phases are triggered with timers: parties start a timer at the beginning of each view and if the timer expires before the leader drives progress, parties move to the view-change phase. However, this may not be live during periods of network asynchrony as views may expire indefinitely without progress. 
     The framework of the present disclosure does not rely on timeouts. By de-coupling the leader-based phase from the view-change phase, we avoid having to use timers. As explained below, parties operating under the framework run several instances of the underlying consensus protocol where each party is a leader in one of those instance. The view-change phase occurs when a quorum of parties as leaders reach consensus in their leader-based phase rather than relying on a timer. 
     As shown in  FIG.  1   , reaching consensus on the decision of a value using framework  106  progresses in one or more “waves”  112 . Aspects of framework  106  in accordance with the present disclosure are discussed in more detail below. Briefly, however, each wave  112  processes a proposed input value in accordance with an underlying consensus protocol. In the case of the first wave, wave 1  in  FIG.  1    for example, the proposed value can come from a queue  114  of input values. In the case of a wave (wave 2 , not shown) subsequent to the first wave, the proposed value (input) to wave 2  is the proposed value is contained in the closing state of the previous wave (waves). LBV instances module  122  represents the concurrent execution of the underlying consensus protocols by each party  102 , both as a leader and a non-leader. LBV instances module  122  includes an LBV instance ( FIG.  2   ) that represents execution of the underlying consensus protocol by a party  102 , where that party is a leader participant in the LBV instance and the other parties are non-leader participants in the LBV instance. Each party  102  in the system is associated with an LBV instance. 
     Each party in wave  112  synchronizes at barrier  124 , waiting for a number (n f) DONE notifications  126  from the LBV instances. Leader election  128  represents the election of a leader from among the LBV instances (chosen LBV). If the chosen LBV instance has reached a decision, then each party can store the agreed-upon value in their respective queue  116  of output values. If the chosen LBV instance has not reached a decision, then processing can continue with another wave  112  using the closing state of the chosen LBV instance as input to the next wave. The closing state includes all the necessary information required by the underlying consensus protocol (e.g., a safe value for a leader to propose and a validation function for all parties use to check if the proposed value is safe). A sequence of one or more waves  112  to reach consensus on a single value represents a single-shot agreement. 
       FIG.  2    shows additional details of framework  106 . The framework describes processing to drive parties  102  to reach consensus on a proposed value in accordance with the present disclosure. Each party  102  includes input queue  114  comprising values that it wants to propose. When a party (e.g., P 1 ) wants to propose a value from its input queue  114 , the party will invoke the framework with the proposed value, which can be encapsulated in an initial input state (S init ) to the framework. As will be explained below, the framework will drive processing by the parties to reach consensus (i.e., agree on) the proposed value in accordance with the underlying consensus protocol. As explained above, the framework proceeds in waves, so the proposed value provided to the first wave comes from the input queue, and the proposed value that is input to a subsequent wave is contained in the closing state (S n−1 ) of a previous wave. In some embodiments, the input queues can be first-in, first-out (FIFO) queues. Accordingly, parties do not advance to the next slot in the queue until they learn the decision of the proposed value in the current slot. 
     In some embodiments, framework  106  can initiate a wave  112  by engaging parties  102  in the system to run the underlying consensus protocol. More specifically, an instance of the underlying consensus protocol is initiated for each party, where that party is designated as the leader. Each instance of the underlying consensus protocol is referred to herein as an LBV instance, and is shown in  FIG.  2    as an instance among a collection of LBV instances in LBV instances block  122 . For example, LBV&lt;IDn, p1&gt;, represents execution of the underlying consensus protocol where party P 1  is the leader. Likewise, LBV&lt;IDn, pj&gt;, represents execution of the underlying consensus protocol where party P j  is the leader, and so on. Accordingly, for n parties each wave will instantiate n corresponding LBV instances, where LBV&lt;IDn, px&gt; has party P x  as leader. For simplicity, we can denote LBV&lt;IDn, px&gt; as LBV x . 
     LBV instances that execute the underlying consensus protocol in accordance with the present disclosure, as a whole, exhibits the following properties: 
     Liveness:
         Engage-Termination: For every instance with a correct leader, if all correct parties invoke engage and no correct party invokes wedge&amp;exchange, then engage invocations by all correct parties eventually return.   Wedge&amp;Exchange-Termination: For every instance, if all correct parties invoke wedge&amp;exchange then all wedge&amp;exchange by correct parties eventually return.       

     Safety:
         Validity: For every instance, if an engage or wedge&amp;exchange invocation by a correct party returns a value v, then v is externally valid.   Completeness: For every instance, if f+1 engage invocations by correct parties return, then no wedge&amp;exchange invocation by a correct party returns a value v=⊥ (referred to as a safe value).   Agreement: If an engage or wedge&amp;exchange invoked in some instance by a correct party returns a value v≠⊥ and some other engage or wedge&amp;exchange invoked in some instance by a correct party returns v′≠⊥ then v=v′.       

     In accordance with the present disclosure, framework  106  includes a wedge and exchange mechanism that comprises barrier  124 . The barrier represents a synchronization point during a wave where parties  102  wait for an event before proceeding. In accordance with the present disclosure, parties  102  wait for the occurrence of n−f DONE notifications  126 , before proceeding to the leader election  128 . As explained below, a DONE notification indicates that a decision has been reached by a quorum of LVB instances; i.e., n−f  FIG.  2    shows that party P j  has been elected leader and that a wedge and exchange (W&amp;E) is invoked on the LBV instance in which party P j  is the leader (LBV j ) to “wedge” the LVB instance and determine what happened in its leader-base phase. The closing state (S n+1 ) and decided value (v n+1 ) are obtained from the state information for party P j  for the next wave. 
     Framework  106  in accordance with the present disclosure captures the core properties provided by a single view in leader-based view-by-view algorithms (e.g., Paxos, PBFT, HotStuff, etc.), but avoids their timeout mechanism. Each view in such an algorithm consists of two phases: first, all parties wait for the leader to perform the leader-based phase to drive a decision on some value v, and then, if the leader fails to do it fast enough, the parties switch to the view-change phase in which they wedge the current leader and exchange information in order to get the closing state of the view. To decide when to switch between the phases, existing algorithms use timeouts, which prevent them from guaranteeing progress during asynchronous periods. The wedge and exchange mechanism described above can boost liveness because the mechanism does not rely on a timeout to switch from the leader-based phase to the view-change phase. Instead, the wedge and exchange mechanism proceeds as soon as n−f DONE notifications are detected. 
     To this end, framework  106  exposes two methods (mechanisms), engage and wedge&amp;exchange, where the engage method starts the first phase of the view (leader-based) and the wedge&amp;exchange method switches to the second phase of the view (view-change). By exposing these two methods, the framework takes over the responsibility on when to switch between the phases from the view so that the process no longer relies on timeouts inside a view, while still preserving all safety guarantees provided by a view in a leader-based view-by-view protocol. By taking over responsibility on when to switch between the phases, the framework can more quickly respond to asynchronous situations, for example when a party becomes unresponsive due to failure or an attack. 
     Framework  106  operates in accordance with the following pseudocode: 
                             ALGORITHM 1                                                 1:   upon SS-propose(id, S) do                              2:   state ← S ; wave ← 1            3:   while true do                              4:   ID ←    id, wave               5:       state′, value    ← WAVE(ID, state)            6:   if value , ⊥ and did not decide before then                              7:   decide    id, value                                 8:   state ← state′            9:   wave ← wave + 1                             10:   procedure WAVE(ID, state)                             11:   for all p j  = p 1 , . . . , p n  do                             12:   invoke engage     ID, pj     (state)    non-blocking                             13:   barrier-sync ID ( )           14:   leader ← elect ID ( )           15:   return wedge&amp;exchange     ID, leader     ( )                             16:   upon engage    ID, p j     returns v do                             17:   send “ID, ENGAGE-DONE” to party p j                               18:   upon receiving n-f “ID, ENGAGE-DONE” messages do                             19:   invoke barrier-ready ID ( )                        
where an invocation of the protocol (SS-propose(id, S)) gets an initial state S and identification id, where the initial state S contains all the initial specific information (including the proposed value) required by the leader-based view-by-view protocol instantiated in the LBV abstraction.
 
     As noted above, the protocol proceeds in waves. The state is updated at the and of every wave and a decision is made the first time a wave returns a non-empty value. At the beginning of every wave, each party invokes the engage operation in n LBV instances associated with the wave, each with a different leader. Each invocation gets the state obtained in the end of the previous wave or the initial one in case of the first wave. 
     Parties invoke barrier-sync and wait for it to return. As explained below in accordance with the B-Coordination property, barrier-sync returns only after f+1 correct parties invoke barrier-ready. When an engage invocation in an LBV instance with leader p j  returns, a correct party sends an “ENGAGE-DONE” message to party p j , and whenever a party gets n−f such messages it invokes barrier-ready( ). Denote an LBV instance as successfully completed when f+1 correct parties completed the first phase, i.e., their engage returned, and note, therefore, that a correct party invokes barrier-ready only after the LBV instance in which it acts as the leader was successfully completed. Thus, a barrier-sync invocation by a correct party returns only after f+1 LBV instances successfully completed. 
     Next, when the barrier-sync( ) returns, parties elect a unique leader via leader election, and further consider only its LBV instance. Note that since parties wait until f+1 LBV instances have successfully completed before electing the leader, the parties elect a successfully completed instance with a constant probability of 
                 f   +   1     n     ,         
and even an adaptive adversary has no power to prevent it.
 
     Finally, all parties invoke wedge&amp;exchange (W&amp;E) in the elected LBV instance to wedge and find out what happened in its first phase, using the returned state for the next wave and possibly receiving a decision value. By the above completeness property of LBV, if a successfully completed LBV instance is elected, then all wedge&amp;exchange invocations by correct parties return v≠⊥ and thus all correct parties decide v in this wave. Therefore, after a small number of 
             n     f   +   1           
waves all correct parties decide in expectation. Note that the sequence of chosen LBV instances form a properly composed execution, and thus since parties return only values returned from chosen LBVs, our algorithm inherits its safety guarantees from the leader-based protocol the LBV is instantiated with.
 
     The discussion will now turn to a description of an illustrative embodiment in accordance with Algorithm 1. Framework  106  represents a mechanism and properties of the mechanism to drive parties  102  to reach consensus on a queue of input values, one value (slot) at a time, in accordance with the present disclosure. As noted above, the framework runs an underlying consensus protocol (algorithm). In accordance with the present disclosure, each part  102  runs multiple instances of the underlying protocol. Framework  106  includes mechanics to control and coordinate the parties. The discussion will now turn to a description of processing in each party  102  and the control and coordinate mechanics of the framework. 
     Referring to  FIG.  3    and other figures, the discussion will now turn to a high level description of operations and processing by each party (e.g., node  102 ,  FIG.  1   ) in a system (e.g.,  100 ) to reach consensus in accordance with the present disclosure. As shown and explained in  FIG.  1   , the framework (e.g.,  106 ) progresses in waves  112 . The processing described in  FIG.  3    below represents processing in each party for a wave. In some embodiments, the party can include computer executable program code, which when executed by the processor(s) in the party&#39;s computer system (e.g.,  902 ,  FIG.  9   ), can cause the party to perform processing in accordance with  FIG.  3   . The operation and processing blocks described below are not necessarily executed in the order shown, and can be allocated for execution among one ore more concurrently executing processes and/or threads. 
     At operation  302 , each party can instantiate an instance of a leader-based view (LBV) in accordance with the underlying consensus protocol in response to receiving an ENGAGE notification (ENGAGE-DONE in algorithm 1) from the framework. This notification is discussed in more detail below. In some embodiments, for example, the engage method can be a signaling mechanism; e.g., a remote procedure call (RPC). The ENGAGE notification can include state information that includes all the necessary information required by the underlying consensus protocol (e.g., a safe value for a leader to propose and a validation function for all parties use to check if the proposed value is safe) to initiate the LBV instance. In the case of the initial wave (e.g.,  112 ,  FIG.  1   ), the ENGAGE notification can indicate this is the initial wave so that the party knows to obtain the proposed value from its input queue (e.g.,  114 ). 
     Referring for a moment to  FIGS.  4 A and  4 B , details of an instance of leader-based view (LBV) will be described in the context of illustrative examples of well known consensus protocols.  FIG.  4 A  shows execution in the leader phase of the Practical Byzantine Fault Tolerance (PBFT) consensus protocol and  FIG.  4 B  shows leader-phase execution of the HotStuff protocol. The examples show party P 1  is the leader participant and parties P 2 , P 3 , P 4  are non-leader participants in the LBV instances shown in  FIG.  4 A  and in  FIG.  4 B . It will be appreciated that the underlying consensus protocol can be any asynchronous consensus protocol. 
     In accordance with the present disclosure, the framework mechanism signals each party in the system to run the underlying protocol as a leader using the ENGAGE notification.  FIG.  2   , for example, shows that the engage method is invoked for each party. Accordingly, party P 1  runs the underlying protocol as the leader in LBV 1 , while the other parties (P 2 −P n ) in LBV 1  participate as non-leaders. Party P 2  runs the underlying protocol as the leader in LBV 2 , while the other parties (P 1  and P 3 −P n ) in LBV 2  participate as non-leaders. In general, party P j  runs the underlying protocol as the leader in LBV j , while the other parties (P 1 −P j−1  and P j+1 −P n ) in LBV j  participate as non-leaders, and so on. It can be seen that each party in the system participates in an LBV instance, either as the leader or as a non-leader. As such, in accordance with the present disclosure, each party in a system of n parties (nodes, replicas, etc.) participates in n instances of the underlying protocol, either as a leader or a non-leader. 
     At operation  304 , each party can signal a COMMIT notification. In some embodiments, for example, when a party in an LBV instance (whether as leader or non-leader) reaches a decision, the party can signal a COMMIT notification to indicate the party has reached consensus on the proposed value. The criterion for signaling a COMMIT notification will depend on the particular underlying consensus protocol. Referring to  FIG.  4 A , for example, in the PBFT protocol, when a party (e.g., P 1 ) receives a quorum (n−f) of COMMIT messages from the other parties, this can be deemed as the party having reached consensus with the other parties in this LBV instance, where n is the number of parties (in this case, n=4) and f is the number of parties that can fail (in this case, f=1). Accordingly, the party can signal a COMMIT notification. Supposing that all parties in  FIG.  4 A  are correct, each party will signal a corresponding COMMIT signal to indicate to the framework that the party has reached consensus in the given LBV instance. Likewise, in the HotStuff protocol of  FIG.  4 B  the leader will signal a COMMIT notification when it receives (n−f) COMMIT votes (consensus reached) from the non-leader participants. On the other hand, each non-leader participant signals a COMMIT notification when the participant receives a DECIDE message from the leader. 
     At operation  306 , each party can signal a DONE notification to the framework. In accordance with the present disclosure, a party can signal a DONE notification when the party has signaled (n−f) COMMIT notifications. Referring to  FIG.  5    for a moment, the figure illustrates this aspect of the present disclosure. As explained above a party P i , in accordance with the present disclosure, executes n LBV instances of the underlying consensus protocol; running one instance as a leader and running n−1 instances as a non-leader. Party P i  can signal a COMMIT notification from each instance of the protocol, depending on the decision outcome in that instance. In some embodiments, P i  can include a commit collector  502  which tracks the number of COMMIT notifications that were signaled by P i , whether as a leader or as a non-leader. For example, the commit collector  502  can be a process or thread that executes on P i  and counts the number of COMMIT notifications that it signals. Continuing with  FIG.  3   , when the party has signaled (n−f) COMMIT notifications, the party can signal a DONE notification  504  to the framework. 
     At operation  308 , each party can pause after it has signaled the DONE notification. In accordance with the present disclosure, further progress by a party in terms of processing a wave can be paused at this time. This “pause” can be represented as barrier  124  in  FIG.  2   . In accordance with the present disclosure, every party that signals a DONE notification can pause at this barrier. This barrier is used to synchronize between parties, ensuring that correct parties wait for each other before progressing. The barrier is characterized by the following properties:
         B-Coordination: No barrier-sync invocation by a correct party returns before f+1 correct parties invoke barrier-ready.   B-Termination: If all correct parties invoke barrier-ready then all barrier-sync invocations by correct parties eventually return.   B-Agreement: If some barrier-sync invocation by a correct party returns, then all barrier-sync invocations by correct parties eventually return.
 
Each party will hit barrier  124  and pause after sending its DONE notification.
       

     At operation  310 , each party can wait for a READY notification from the framework before proceeding past the barrier. 
     At operation  312 , each party can elect a leader in response to receiving a READY notification from the framework. This notification is discussed in more detail below. Referring to  FIG.  2   , in accordance with the present disclosure, the party can proceed to leader election when it receives a READY notification from the framework. Leader election in accordance with the present disclosure, includes the party selecting a leader from among the parties in the system. As will be seen, the elected leader is a “leader” in the sense that it&#39;s closing state may become the input state to a subsequent wave. Each party receiving the READY notification will proceed and perform leader election. 
     Leader election algorithms are known. A leader election algorithm will decide on exactly one leader among the parties in the system when executed by the parties in the system. A valid leader election algorithm in accordance with the present disclosure has the following properties:
         L-Termination: If f+1 correct parties perform leader election, then all invocations by correct parties return (complete the algorithm).   L-Agreement: All invocations of the leader election algorithm by correct parties that return, return the same party.   L-Validity: If an invocation of the leader election algorithm by a correct party returns, it returns a party pi with probability 1/n for every piϵ{p1, . . . , pn}.   L-Unpredictability: The probability of the adversary (faulty party) to predict the returned value of an elect invocation by a correct party before any correct party invokes elect is at most 1/n.
 
The party can signal the framework with an ELECTED LEADER notification, including information about the elected leader.
       

     At operation  314 , each party can respond to a W/E (wedge &amp; exchange) notification from the framework. As will be explained, the W/E notification identifies the LBV instance in which the elected leader was executing as the leader participant. Thus, for example, if party P j  is the elected leader per leader election in operation  312 , the W/E notification will identify the LBV instance. Each party, in response to receiving the W/E notification, will find out what happened in the identified LBV instance. The party that is the leader in the identified LBV instance will provide its state information and a decision value to the framework. Processing in this wave can be deemed complete so each party can terminate its LBV instances in preparation for another possible wave. 
     The discussion will now turn to a description of the framework mechanism  106  shown in  FIG.  1   . The framework mechanism can be embodied in system  100  in any suitable manner.  FIG.  1   , for example, shows that in some embodiments the framework mechanism can be embodied as background processes executing in the parties themselves. Framework signaling can be passed between parties as LBV messages  104 . Referring to  FIG.  6   , in some embodiments, the framework mechanism can be another node (framework node)  602  in the system. The framework node  602  can receive signaling from parties P 1 -P 4  (e.g., using RPCs) and send notifications to the parties, in accordance with processing in  FIG.  3    for example. 
     Referring to  FIG.  7    and other figures, the discussion will now turn to a high level description of operations and processing by the framework mechanism ( 106 ,  FIG.  1   ) in accordance with the present disclosure. In some embodiments, the framework mechanism can include computer executable program code that executes in the parties  102  or in a separate framework node ( FIG.  6   ). The computer executable program code, when executed by a processor (e.g.,  902 ,  FIG.  9   ), can cause the processor to perform operations in accordance with  FIG.  7   . The operation and processing blocks described below are not necessarily executed in the order shown, and can be allocated for execution among one ore more concurrently executing processes and/or threads. 
     At operation  702 , the framework mechanism can signal each party with an ENGAGE notification. In some embodiments, for example, the ENGAGE notification can be a message that is sent to each party. Recall from  FIG.  3    that each party, in response to receiving an ENGAGE notification, initiates an instance of the underlying consensus protocol as the leader. 
     At operation  704 , the framework mechanism can wait until it receives a DONE notification from (n−f) parties before continuing on to operation  706 . Referring for a moment to  FIG.  8   , the figure illustrates this aspect of the present disclosure. In some embodiments, for example, the framework mechanism can include a done collector  802 . Recall that each party can signal a DONE notification. The done collector  802  can track and count the number of DONE notifications signaled by the parties before continuing on to operation  706 . 
     At operation  706 , the framework mechanism can signal each party with a READY notification. In some embodiments, for example, the READY notification can be a message that is sent to each party. 
     At operation  708 , the framework mechanism can wait until it receives ELECTED LEADER notifications from (n−f) parties before continuing on to operation  710 . The ELECTED LEADER notification can include information identifying the party that was elected the leader. 
     At operation  710 , the framework mechanism can signal each party with a W/E notification. The W/E notification can include the LBV instance in which the elected leader (identified in operation  708 ) is the leader participant. Thus, for example, if party P j  is the elected leader, the W/E notification will identify instance LBV j . 
     At operation  712 , the framework mechanism can terminate with a decision or initiate another wave. In some embodiments, for example, if the value decided by the elected leader (elected party) is not a safe value (⊥), then processing can continue at operation  714 . If the value decided by the elected leader is the safe value, the framework mechanism can initiate another wave (view) to continue driving the process in order to reach a decision. Processing can return to operation  702  to initiate the next wave. In some embodiments, for example, the framework mechanism can use the closing state of the elected leader (identified at operation  708 ) as the input state for the next wave. Because the framework mechanism starts a new view (wave) using the closing state of the previous view (i.e., closing state of the elected leader), the process can ensure safety because correct parties will decide on the same value. Formally, we say that the LBVs are properly composed by a party p in an execution if p i  invokes the engage of the first instance with some fixed initial state (which depends on the instantiated protocol), and for every instance k&gt;1, p i  invokes its engage with the output of wedge&amp;exchange at instance k−1. In addition, we say that the LBV instances are properly composed in an execution if they are properly composed by all correct parties. 
     At operation  714 , the framework mechanism can decide the value that was decided by the elected leader. Processing can be deemed complete because a decision has been reached. As noted above, by the Completeness property of LBV, if a successfully completed LBV instance is elected, then all W&amp;E invocations by correct parties return v≠⊥ and thus all correct parties decide v in this wave. Therefore, when the framework mechanism returns the decision of the elected leader, the value is correct. Moreover, since all parties wait until f+1 LBV instances have successfully completed before electing the leader, the parties elect a successfully completed instance with a constant probability of 
                 f   +   1     n     ,         
and even an adaptive adversary has no power to prevent it.
 
Asynchronous Fair State Machine Replication
 
     The discussion will now turn to a description of the framework mechanism in the context of an asynchronous fair state machine replication (SMR). The pseudocode for the asynchronous fair state machine replication appears in Algorithm 2: 
                             ALGORITHM 2                                                 1:   upon SMR-propose(S) do                              2:   slot ← 0            3:   for every s ∈ N do                              4:   M[s] ← { }            5:   V [s] ← ⊥; D[s] ← false                              6:   while true do                              7:   slot ← slot + 1            8:   SS-propose(slot, S[slot])            9:   wait until D[slot] = true           10:   send “slot, DECIDE, value” to all parties           11:   barrier-ready slot ( )           12:   barrier-sync slot ( )           13:   free all resources associated with slot           14:   output    slot, V[slot]                                15:   upon decide    slot, v    do                             16:   V [slot] ←v; D[slot] ← true                             17:   upon receiving “slot, DECIDE, v” from party pj do                             18:   M[slot] ← M[slot] ∪ {    pj, v    }           19:   if ∃v s.t. |{p |    p, v    ∈ M[slot]}| = f + 1 then                             20:   V [slot] ←v; D[slot] ← true                        
The parameter S, passed to the SMR-propose invocation, is a vector consisting of an initial state for each slot. We use an instance of the asynchronous single-shot agreement to agree on the value of each slot, and thus the SMR algorithm inherits the Integrity, Fairness, Validity and Agreement properties from the single-shot one. In order to satisfy FIFO, parties do not advance to the next slot until they learn the decision of the current one, and in order to satisfy Halting they de-allocate all resources associated with the current slot and abandon the slot&#39;s single-shot algorithm once they move. Note that abandoning a single-shot algorithm might violate its Termination because it relies on the participation of all correct parties. Therefore, to satisfy the Termination of the SMR, we use a forwarding mechanism to reliably broadcast the decision value before abandoning the current slot and moving to the next one.
 
     Because the framework is model agnostic, parties do not explicitly use threshold signatures and decision proofs in the forwarding mechanism. Instead, in every slot, correct parties waits until they either decide on a value v (via the slot&#39;s single-shot agreement) or receive f+1 “DECIDE” messages from parties claiming they have decided on a value v. In the second case, the receiving party knows that at least one correct party decided v even in the byzantine failure model. Then, to make sure that all correct parties eventually finish waiting even though some might have moved to the next slot already, parties use the barrier abstraction that provides the required guarantee with its B-Coordination property. Note that although the above forwarding mechanism works for both byzantine and crash failures models, in the latter case the forwarding mechanism can be simplified: a party only needs to echo its decision value before it moves to the next slot. So in this case, the lines 4, 11, 12, 18, and 19 in the pseudocode can be dropped. 
       FIG.  9    depicts a simplified block diagram of an example computer system  900  according to certain embodiments. Computer system  900  can be used to implement nodes (parties, replicas)  102  ( FIG.  1   ) and framework node  602  ( FIG.  6   ) described in the present disclosure. As shown in  FIG.  9   , computer system  900  includes one or more processors  902  that communicate with a number of peripheral devices via bus subsystem  904 . These peripheral devices include storage subsystem  906  (comprising memory subsystem  908  and file storage subsystem  910 ), user interface input devices  912 , user interface output devices  914 , and network interface subsystem  916 . 
     Bus subsystem  904  can provide a mechanism for letting the various components and subsystems of computer system  900  communicate with each other as intended. Although bus subsystem  904  is shown schematically as a single bus, alternative embodiments of the bus subsystem can utilize multiple busses. 
     Network interface subsystem  916  can serve as an interface for communicating data between computer system  900  and other computer systems or networks. Embodiments of network interface subsystem  916  can include, e.g., an Ethernet card, a Wi-Fi and/or cellular adapter, a modem (telephone, satellite, cable, ISDN, etc.), digital subscriber line (DSL) units, and/or the like. 
     User interface input devices  912  can include a keyboard, pointing devices (e.g., mouse, trackball, touchpad, etc.), a touch-screen incorporated into a display, audio input devices (e.g., voice recognition systems, microphones, etc.) and other types of input devices. In general, use of the term “input device” is intended to include all possible types of devices and mechanisms for inputting information into computer system  900 . 
     User interface output devices  914  can include a display subsystem, a printer, or non-visual displays such as audio output devices, etc. The display subsystem can be, e.g., a flat-panel device such as a liquid crystal display (LCD) or organic light-emitting diode (OLED) display. In general, use of the term “output device” is intended to include all possible types of devices and mechanisms for outputting information from computer system  900 . 
     Memory subsystem  906  includes memory subsystem  908  and file/disk storage subsystem  910  represent non-transitory computer-readable storage media that can store program code and/or data, which when executed by processor  902 , can cause processor  902  to perform operations in accordance with embodiments of the present disclosure. 
     Memory subsystem  908  includes a number of memories including main random access memory (RAM)  918  for storage of instructions and data during program execution and read-only memory (ROM)  920  in which fixed instructions are stored. File storage subsystem  910  can provide persistent (i.e., non-volatile) storage for program and data files, and can include a magnetic or solid-state hard disk drive, an optical drive along with associated removable media (e.g., CD-ROM, DVD, Blu-Ray, etc.), a removable flash memory-based drive or card, and/or other types of storage media known in the art. 
     It should be appreciated that computer system  900  is illustrative and many other configurations having more or fewer components than system  900  are possible. 
     The above description illustrates various embodiments of the present disclosure along with examples of how aspects of the present disclosure may be implemented. The above examples and embodiments should not be deemed to be the only embodiments, and are presented to illustrate the flexibility and advantages of the present disclosure as defined by the following claims. Based on the above disclosure and the following claims, other arrangements, embodiments, implementations and equivalents may be employed without departing from the scope of the disclosure as defined by the claims.