{'fraction_non_alphanumeric': 0.03363784434530132, 'fraction_numerical': 0.010197578075207138, 'mean_word_length': 4.527661795407098, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Bernoulli Meets PBFT: Modeling BFT Performance in the Presence of Dynamic Failures

The publication of the pivotal state machine replication protocol PBFT laid the foundation for a large body of BFT protocols. While many successors to PBFT have been developed, there is no general technique to predict the performance of these protocols under realistic network conditions such as unreliable links. In this paper, we introduce a probabilistic model for evaluating BFT protocols in the presence of dynamic link and crash failures. Based on modeling techniques from communication theory, the network state of replicas is captured and used to derive the success probability of the protocol execution. To this end, we examine the influence of link and crash failure rates as well as the number of replicas. The model is derived from the communication pattern, making it implementation-independent and facilitating an adaptation to other BFT protocols. The model is validated with a simulation of PBFT and \smart. Further, a comparison in protocol behavior of PBFT, Zyzzyva and SBFT is performed and critical failure thresholds are identified.


Introduction
The rapidly increasing connectivity of devices, as for example envisioned by the Internet of things, entices the development of large-scale, globally distributed systems. The European Metrology Cloud project [33], which aims to coordinate the digital transformation of legal metrology, is a prime example. The scale and complexity of such systems leads to a higher risk of failure and/or malicious behavior. The demand for trust and reliability, however, remains unchanged.
A technique to offer higher fault tolerance and availability for distributed systems is state machine replication (SMR). It requires processes to find agreement on the order of state transitions and, thus, consensus on the system state. One of the most prominent Byzantine fault tolerant (BFT) protocols is Practical Byzantine Fault Tolerance (PBFT) [10]. Many modern systems, including the recent surge of blockchain applications, utilize PBFT, or a variation of it, as their core consensus algorithm, e.g., BFT-SMaRt [4], Tendermint [7], RBFT [3], CheapBFT [18], and Hyperledger Fabric v0.6 [2].
The network can be described as either synchronous or asynchronous. To bridge the gap between completely synchronous/asynchronous systems, the term partially synchronous was introduced [12]. A partially synchronous system may start in an asynchronous state but will, after some unspecified time, eventually return to a synchronous state. This captures temporary link failures, for example. A different perspective on a partially synchronous system is to assume a network with fixed upper bounds on message delays and processing times, where both are unknown a priori. The partially synchronous system model is utilized by many BFT protocols, e.g., PBFT, to circumvent the FLP impossibility [15] and guarantee liveness during the synchronous states of the system, without requiring it at all times. Deterministic BFT protocols guarantee safety, even in the asynchronous state, but require synchronous periods to guarantee liveness.
To detect Byzantine behavior, most BFT protocols utilize timeouts (and signatures). If the happy path of a protocol fails to make progress, a sub-protocol, e.g., a view change protocol, is triggered to recover [20]. To optimize performance, the timeout values should depend on the bounded message delay in the synchronous periods of the network, which plays an important role for deployments [11]. In addition to message delay characteristics, some networks, e.g., wireless networks, might be susceptible to link failures, leading to message omissions or corruptions. These failures are formally captured by the so-called dynamic link failure model [26], where the authors prove that consensus is impossible in a synchronous system with an unbounded number of transmission failures. Schmid et al. [27,28] introduced a hybrid failure model to capture process and communication failures and derived bounds on the number of failures for synchronous networks.

BFT Models
Other modeling techniques to analyze the performance of distributed systems and PBFT have previously been proposed in the literature. The framework HyPerf [17] combines model checking and simulation techniques to evaluate BFT protocols. While model checking usually proves correctness, their framework uses simulations to explore the possible paths in the model checker and evaluate the performance of the protocol. The model is validated against an implementation of PBFT to predict latencies and throughput. A method to model PBFT with Stochastic Reward Nets (SRNs) was proposed in [32]. The authors deployed Hyperledger Fabric v0.6, which implements PBFT, on a cluster of four nodes and compare the collected data to the distributions of their SRNs. Afterwards, the number of nodes in the model is scaled and evaluated regarding the mean time to consensus.
Singh et al. [30] provided a more direct approach to evaluate BFT protocols with the simulation framework BFTSim. The framework utilizes the high-level declarative language P2 [21] to implement three different BFT protocols [10,19,1]. Built upon ns-2 [24], the simulation can explore various network conditions. While the previously listed models and/or simulators offer the possibility to evaluate the performance of BFT protocols, they all require comprehensive implementations of the respective protocol. The model presented in this paper, however, is derived from the communication pattern. Moreover, no simulations or measurements are required to employ our model; all system states can be evaluated with closed-form expressions at low computational cost. Finally, the main focus of our work is to present a model for BFT protocols that captures the impact of unreliable communication and varying message delays, which the other models only considered as a minor aspect.

Link and Crash Failures
In this paper, we analyze the consequences of message omissions in PBFT caused by dynamic link failures, which also covers misconfigured timeouts. Fathollahnejad et al. [14] examined the impact of dynamic link failures on their leader election algorithm in a traffic control system. They assume a constant failure probability and present techniques to calculate the probability for disagreement. As in our paper, the number of received messages of an all-to-all broadcast is modeled with Bernoulli trials. Since their use case does not consider Byzantine failures, their protocol does not require a consecutive collection of message quorums which is, however, implemented in most BFT protocols and thus the main focus of the model presented in this paper.
Xu et al. presented RATCHETA [34], a consensus protocol which was designed for embedded devices in a wireless network that might be prone to dynamic link failures. They included an evaluation with artificially induced packet losses, measuring the number of failing consensus instances. RATCHETA requires a trusted subsystem that prevents a process from casting differing votes during the same consensus instance, eliminating the possibility of equivocations. It therefore yields a 2f + 1 resilience, allowing f Byzantine failures.
In addition, there is a body of literature that covers the theoretical limits of consensus protocols [29,28,5], which are based on a hybrid failure model [27] and therefore also capture link failures. Existing models, however, rarely consider performance aspects resulting from unreliable network conditions such as dynamic crash and link failures. Since all BFT protocols have a built-in protocol to recover from crashed processes, e.g., view changes, their impact on the performance is tied to the frequency of the recovery algorithm execution.

Process Model
A distributed system consists of a fixed number of n processes (we use the term process, node, and replica interchangeably), each with a unique ID. Typically, no more than f processes are allowed to be subject to Byzantine faults. To guarantee safety, the system requires n ≥ 3f + 1 replicas.
In order to capture diverse failure cases, e.g., congestion due to high traffic load, we introduce the term dynamic crash failures. That is, processes can become unavailable in each phase for a short period of time. It is assumed that every crashed process will recover almost immediately, upholding its pre-crash state, and may thus be available in the next phase of the protocol. Since most BFT protocols (including PBFT) are based on consecutive phases, a crashed replica will remain inactive until the protocol-specific recovery algorithm, e.g., view-change protocol for PBFT, has recovered crashed replicas. In this paper, crash failures are assumed to be independent and identically distributed (i.i.d.) random variables for all processes.
Since our model is derived from the communication pattern of the protocol, special roles such as the primary in PBFT which follow a different communication pattern, are incorporated into the model.

Network Model
We assume that each network node has a peer-to-peer connection to all other nodes. The network model in this paper allows for (1) messages to be delayed indefinitely, i.e., past the configured timeout parameter of PBFT, and (2) message omissions as well as corruptions. The former case acknowledges BFT protocols that rely on synchronous periods to guarantee liveness and are based on timeouts to detect process and/or link failures. PBFT, for example, makes use of timeouts to detect if progress is being made and as a consequence to initiate the view-change protocol, which elects a new primary. Messages that arrive after a configured timeout can therefore be considered as message omissions. The same applies to invalid or corrupted messages. The resulting failure model can be described with the dynamic link failure model, introduced in [26]. While in practice many BFT protocols rely on other protocols to guarantee reliable communication, e.g., TCP, they should implement means to handle lost messages due to crashed/malicious processes. We therefore assume unidirectional links, which implies unreliable communication.
If assumptions made regarding the bound of message delays fail, i.e., the timeouts are not configured appropriately, the protocol can be considered to operate in an asynchronous network with unbounded message delays. This does not apply if an attacker is considered to have control over the scheduling of messages, as this could easily lead to stopping a BFT protocol altogether [22]. As with process failures, the link failures are assumed to be i.i.d. for all links.

Modeling PBFT
The model presented in this section offers means to evaluate PBFT in the presence of dynamic link failures and crash failures. In particular, a performance impact assessment becomes possible. For the sake of clarity, we provide an overview of our modeling approach and introduce our notation first. Next, we unroll our model for various failure types step-by-step starting with dynamic crash failures, before we incorporate dynamic link failures.

Overview
In PBFT, the happy path consists of five phases of message exchanges, as depicted in Figure 1. The first and last phase consist of transmissions from and to the client. In the first phase, the leader of the current view will collect and serialize client requests. This is followed by a second phase in which the primary disseminates the requests to all other replicas in a so-called pre-prepare message. If a replica receives and accepts a pre-prepare message, it stores that message and enters the third phase, broadcasting prepare messages. Replicas wait for a quorum of messages, i.e., at least 2f + 1 prepare messages which match the stored pre-prepare message. In the fourth phase replicas broadcast commit messages to all other replicas. Finally, if a replica collects another quorum of commit messages, which match a previously collected quorum of prepare messages, it will commit (and execute) the state transition. In the fifth and last phase of the protocol, replicas reply to the client, confirming that the client's request was executed from the replicated system.
Disregarding the client interactions, PBFT's happy path can be reduced to three phases by omitting the first and last phase. The remaining three phases can be summarized as a broadcast phase and two quorum collection phases. In the following, we assume that the primary is ready to initiate the consensus algorithm. Consequently, only the communication between the replicas is captured in our model.
In each phase of the protocol, the communication between and the availability of replicas is modeled as a combination of Bernoulli trials. More specifically, we model link and crash failures in alternating rounds for each of PBFT's phases, as depicted at the bottom of Figure 1. To this end, we introduce random variables N i and C i to express the success probabilities for the respective failure type in round i. We assume failures to be i.i.d. for all links and processes.
In a first step, only faulty nodes are modeled as crash failures in a series of interdependent Bernoulli trials, i.e., N 1 → N 2 → N 3 . In a second step, we extend the model by incorporating link failures. The communication is modeled along the lines of the three transmission phases C 1 , C 2 , and C 3 . Combined with the node failures, our model yields an interleaving series of dependent system states, i.e., In summary, the system state of all replicas at each protocol phase is captured by a series of probability density functions (PDFs), each constituting the calculation of the following. Please note, that each PDFs allows for precise prediction of the protocol behavior and can be transformed into more common performance metrics, e.g., latency, with statistics or other models that predict the duration of individual phases.

Notation
In Table 1, we summarize relevant probabilities, events, and random variables, which are used in our model. For ease of comprehension, the link and crash failure distributions are now reduced to single probabilities, i.e., p l and p c , respectively. The assumption to have identical link failure probabilities for all links is not an uncommon practice in this field of research [13,30,34]. The impact of arbitrary failure distributions on the model are explained in Section 4.5. The system state of the protocol is modeled by calculating PDFs that describe each replica's state. To this end, the random variables and events listed in Table 1 are indexed according to the different phases in PBFT.
In particular, C 1 , C 2 , and C 3 represent the number of replicas that received a pre-prepare message, received a quorum of prepare messages and received a quorum of commit messages, respectively. Additionally, the number of active replicas after each phase is described with N 1 , N 2 , and N 3 . Due to the nature of the PBFT algorithm, the distributions are dependent on each other, i.e., a replica that crashed or failed to collect the required messages will not be able to complete the happy path. The performance of the protocol can be assessed by calculating the previously mentioned PDFs that describe the states of each replica.
A key building block of our model are Bernoulli trials. Therefore, we use the notation B(n, p, k) = n k · p k · (1 − p) n−k to express the probability to get exactly k successes in a Bernoulli experiment with n trials and a success probability of p. Furthermore, we define B(n, p, as the sum over all Bernoulli trials with at least k and up to l successes. Finally, the notations P X (x) = P (X = x) and P X|Y (x|y) = P (X = x|Y = y) are used to abbreviate (conditional) probabilities. Events C p Indicates a successful reception of a quorum of prepare messages at the current primary.

Random Variables
The number of replicas that have received a pre-prepare message.
The number of replicas, excluding the primary, that did not crash in the pre-prepare phase.
[0, n − 1] The number of replicas, excluding the primary, that received a pre-prepare message as well as collected a quorum of prepare messages.
[0, n − 1] The number of replicas that received a pre-prepare message as well as collected a quorum of prepare messages.
[0, n] The number of replicas that did not crash in the prepare phase.
[0, n] C 3 The number of replicas that have received a pre-prepare message as well as collected a quorum of both, prepare and commit messages.
The number of replicas that have did not crash in the commit phase and successfully executed the algorithm.

Modeling crash failures
We start by modeling one of the most prominent failures, crash failures. In particular, a crash failure implies no participation of the crashed process in the phase in which the crash occurred. Hence, the replica will neither receive nor send any messages. In the following, the three random variables N 1 , N 2 , and N 3 are derived for a crash failure probability p c , assuming reliable communication links. The happy path of PBFT is initiated with the primary broadcasting a pre-prepare message to all other replicas. For the sake of simplicity, it is assumed the primary cannot crash during the pre-prepare phase. Since the probability for a crash is uniform across all nodes, the PDF of the still active replicas N 1 is given by P N1 (n 1 ) = B(n, 1 − p c , n 1 ). The distribution of N 1 describes the number of replicas that will now broadcast prepare messages to all other replicas in the second phase of the protocol.
Following this procedure, the distribution of active nodes in further phases is calculated conditioned on the previous phase, meaning Adding up the values of P (N 3 ≥ 2f + 1) allows to predict the success probability for the happy path of PBFT. As replicas cannot skip a phase in PBFT, a crashed replica will not recover during the happy path rendering dynamic crashes similar to permanent ones.

Modeling crash and link failures
We now extend our model by introducing link failures, i.e., the links are no longer considered reliable and are subject to a link failure probability p l . The three random variables C 1 , C 2 , and C 3 are introduced to model the behavior of the protocol during the three communication phases. Due to the special behavior of the primary in the second phase, C 2 is divided into the event C p and random variable C 2,n to capture the communication of the primary and other replicas, respectively. Assuming the dynamic link failure model, all links are subject to the same failure probability p l and can be, as with crash failures before, described with Bernoulli trials. In the following, we therefore start alternating between C i and N i (cf. Figure 1) to model the success of the message delivery and node availability, respectively.
Calculating C 1 After receiving a request from the client, the first phase is initiated with the primary broadcasting a pre-prepare message to all other replicas. Again, we assume that the primary cannot crash while receiving requests from a client. Since the success probability for each message transmission is equal to 1 − p l and independent of other transmissions, the number of successful transmissions can be calculated with a Bernoulli trial. The PDF of C 1 is given by and describes the number of replicas that have received a pre-preapre message from the primary.
Calculating N 1 Given the distribution of C 1 , some of replicas might crash in this phase. Based on C 1 , the PDF of the remaining active replicas N 1 is Calculating C 2 The communication in the second phase is composed of two cases: (1) whether the primary can collect 2f prepare messages (i.e., C p ), and (2) the number of non-primary replicas that collect at least 2f + 1 prepare messages (i.e., C 2,n ). The primary can only collect at least 2f prepare messages if at least 2f active replicas have received the previous pre-prepare message, i.e., N 1 ≥ 2f . In this case, at least 2f transmissions of prepare messages of the N 1 replicas have to successfully reach the primary. This can be expressed as the sum over all favorable Bernoulli trials, i.e., all trials with at least 2f successes out of N 1 . The conditional probability P (C p | N 1 = n 1 ) for the primary to collect the prepare message is given by For a non-primary node, i.e., a replica, to advance to C 2 , two requirements need to be met: (1) the replica has received a respective pre-prepare message, and (2) the replica has collected a quorum of matching prepare messages. For a quorum, only 2f − 1 prepare messages are required, since a replica's own prepare message and the primary's pre-prepare message count towards the 2f + 1 required messages. The previous requirements translate to 1. there cannot be more replicas that receive 2f − 1 prepare messages than replicas that have previously received a pre-prepare message, i.e., C 2,n ≤ N 1 , and 2. a replica can only receive 2f − 1 prepare messages if at least 2f replicas, including itself, have received a pre-prepare, i.e., N 1 ≥ 2f .
The calculation of C 2,n can thus be divided into the following cases, assuming that n 1 replicas have received a pre-prepare message. First, for n 1 < 2f , no replica will be able to gather the required quorum of prepare messages, thus, the probability for c 2,n = 0 is always one. Second, if c 2,n > n 1 , the probability has to be zero. Finally, for all other cases, of the n 1 replicas that broadcast prepare messages, excluding the primary, the probability for c 2,n replicas to receive 2f − 1 of those messages can be modeled as another Bernoulli trial. The probability of success in that Bernoulli trial is identical to a replica receiving at least 2f − 1 messages of the n 1 − 1 possible. Thus, the conditional PDF of C 2,n for n 1 ≥ 2f and c 2,n ≤ n 1 is given by P C2,n|N1 (c 2,n | n 1 ) = B(n 1 , p 2 (n 1 ), c 2,n ) with p 2 (n 1 ) being the probability that a replica will receive at least 2f − 1 prepare messages, given that n 1 replicas, including the replica itself, are broadcasting that message, which implies they have received the pre-prepare message as well. This can be calculated with another Bernoulli trial to get 2f − 1 receptions from n 1 − 1 messages of the other replicas, Combining (4) and (5) yields the conditional PDF of C 2 . The calculation is split into multiple cases as follows c 2,n = n P C2,n|N1 (c 2,n | n 1 ) · P (C p | N 1 = n 1 ) + P C2,n|N1 (c 2,n − 1 | n 1 ) · P (C p | N 1 = n 1 ), c 2,n ≤ n 1 + 1 0, otherwise.
The final PDF of C 2 is given by applying the law of total probability to (7), which yields Calculating N 2 As with N 1 and (3), the distribution of replicas that are still active, based on C 2 , is Calculating C 3 Now, let us turn to the states C 3 and N 3 . In the third phase, the primary behaves in the same way as every other replica, simplifying many calculations regarding the communication as we do not need to mind so many exceptions. As with C 2 , there are two requirements necessary for a replica to reach C 3 : (1) the replica must be in state C 2 and (2) it must have received at least 2f commit messages, not counting its own. Thus, we can conclude that 1. there cannot be more replicas that have received 2f commit messages than replicas that have reached C 2 , i.e., C 3 ≤ C 2 , and 2. a replica can only receive 2f commit messages if at least 2f + 1 replicas, including itself, have reached state C 2 , i.e., C 2 > 2f .
Deriving C 3 is similar to C 2 with (5), (6), and (7). The conditional probability of C 3 for c 2 > 2f and c 3 ≤ c 2 is accordingly where p 3 (c 2 ) is the probability that a replica will receive at least 2f commit messages if c 2 replicas, including itself, are broadcasting that message, i.e., Applying the law of total probability yields Calculating N 3 Finally, the PDF of all active nodes after the last phase is similar to (3) and (9) Combining (2), (3), (8), (9), (12) and (13) yields the system state at any time during execution of PBFT's happy path. If more than 2f replicas have completed the last phase, i.e. P (N 3 > 2f ), the happy path of PBFT was successful. For the system to provide liveness in regards to the current request, only f + 1 replicas are sufficient.

Generalization
For the sake of simplicity, we so far assumed constant failure probabilities for links and processes, i.e., p l and p c . We also assumed in our calculations, that those probabilities be constant for each phase of PBFT. This is not a requirement and could be expanded to reflect more sophisticated failure models that include time-based correlations, for example, as long as they remain i.i.d. for each phase.
Since the model is derived solely from communication patterns, it can be adapted to other BFT protocols, which exhibit similarities to PBFT. This is facilitated by the modular design of the model, i.e., the expression of communication phases, e.g., broadcast, quorum, as PDFs which can be combined to describe the overall system state. To demonstrate the adaptability, we show the application of the model to BFT-SMaRt, Zyzzyva and SBFT in Appendices A, B, and C, respectively. These adaptations showcase how the model can be applied to a variety of communication patterns, including client interaction and the possibility to branch into a fast or slow path.
We deliberately chose to highlight the model derivation in this section, leaving the formal definition of the modular components for future work.

Model Validation
To verify the correctness of the model, a discrete-event simulator was written in Rust. The codebase of the simulation is publicly available on Github 1 . In a first instance, the simulator implements the happy path of PBFT for single requests without batching. The dynamic link failure model is realized by discarding each message reception event with a configurable probability p l (except the messages from the client). In addition, each node will miss all messages belonging to a certain communication phase with probability p c , simulating a crash failure. The state transitions of all processes are logged, i.e., receiving a pre-prepare, collecting a quorum of prepare and commit messages, as well as any crashes that occurred during each phase. By doing this, we can compare the simulated state with the predictions of our model. The simulation can easily scale to larger numbers of nodes (above 100) since only the state transitions in the happy path are of interest and no actual SMR is implemented, i.e., requests are not executed.
In order to validate our model with an independent source, we also deployed the Java-based public BFT SMR library BFT-SMaRt [4] as a reference implementation. Recent work considers the library as a stable implementation of BFT SMR [9,25,31]. It implements a consensus protocol [8] that bears a high resemblance to PBFT: it utilizes epochs, an equivalent to the views in PBFT, and operates in three phases with respective message types. For simplicity, we stick to PBFT's terminology, when discussing BFT-SMaRt While mostly similar, the communication pattern of BFT-SMaRt differs from PBFT in two details, which required minor model adaptations. Firstly, nodes do not count the primary's pre-prepare message as a prepare message for the second phase. Secondly, nodes are allowed to skip the second phase if a quorum of other nodes was able to complete that phase so that at least 2f +1 commit messages are broadcast in the third phase. We describe the model adaptations in Appendix A. To apply dynamic link and crash failures to BFT-SMaRt, artificial message omission probabilities were implemented into the library. Accordingly, all messages associated with one of the three phases are dropped with the probability p l and each node discards all messages of a whole phase with probability p c . The changes necessary to implement the aforementioned failures affected the class that is responsible for handling incoming messages only and consisted of less than 50 lines of additional code. Since BFT-SMaRt was not implemented to cope with dynamic link failures, the library relies on TCP to handle message omissions. Therefore, the introduced message losses causes the library to halt during the view-change protocol. Consequently, to gather enough data and reliably evaluate the protocol, the protocol is restarted after each request. By doing this, we are still able to log all states and state transitions as before. The library was executed on a single computer and up to 10 replicas and one client were instantiated to execute the requests. Increasing the number of processes while keeping the maximum number of faulty processes constant leads to an increased robustness of both protocols against link and crash failures, because more messages are available to build a quorum while the required quorum size remains equal. We therefore evaluate both protocols for the most interesting scenario n = 3f + 1, i.e., the minimum number of processes required to tolerate f faulty processes.
To validate the model for a larger parameter space, we evaluated PBFT for different numbers of processes, link failure rates, and crash failure rates. Figures 2a to 2c show the probability of a single (representative) process to successfully reach phase N 3 for different n, p l and p c , respectively. The simulation results for 5,000 requests are plotted with 99% confidence intervals and model predictions are depicted as crosses. Increasing the number of processes in the network can have, depending on the number of processes and failure rates, either a stabilizing or destabilizing effect on the performance. A more detailed analysis of this behavior is given in Section 6.3. Increasing the failure rate of either links or processes causes a constant decrease for P (N 3 ).
The comparison between model predictions and experimental results for BFT-SMaRt are shown in Figures 2d to 2f. Since BFT-SMaRt implements actual SMR and the execution was unstable due to the previously mentioned halts during the view-change protocol, we executed 1,000 requests for each parameter combination only (without batching). Figure 2d    6 Evaluation

Protocol stability
The all-to-all broadcast quorum collection phase in BFT protocols, i.e., for 2f + 1 processes to collect 2f out of 3f possible messages (not counting its own), is inherently resilient against link failures. A node cannot collect a quorum if at least f + 1 out of its 3f incoming links are failing. Consequently, even in the worst case, at least f + 1 nodes with at least f + 1 link failures, i.e. (f + 1) 2 overall link failures, are necessary for the quorum collection phase to potentially fail. We can validate this theoretical boundary for PBFT with our model. Since the number of processes that partake in each quorum phase is dependent on previous phases, the boundary for each phase is calculated as with E[N i−1 ] being the expected number of nodes that are still active after the previous phase. Depicted in Figure 3 are the predicted probabilities for P (N 3 ) for increasing link failures ( Figure 3a) and crash failures (Figure 3b). The line labeled "stable" marks the boundary, given by (14), past which the average number of link failures can potentially cause the quorum phase to fail. The linear decrease to the left of the boundary originates from the previous phases of the protocol. In Figure 3a, the number of processes that receive the pre-prepare message in the first phase (N 1 ) limits the overall number of processes that can complete the protocol. Since N 1 decreases linearly with the link failure rate, so too will N 2 and N 3 . Past the boundary, the quorum phase may fail due to the increased number of link failures, resulting in an abrupt decline of P (N 2 ) and P (N 3 ). The same behavior is visible for increasing crash failures in Figure 3b, albeit with an even steeper linear phase. Because processes cannot recover within the happy path of PBFT, each successive phase with crash failures will decrease the number of available nodes for further phases, leading to the steeper decline before the boundary.
The evaluation methodology and the respective results can be used to parametrize the protocol to ensure that the protocol execution remains stable even for a given failure rate. Since most BFT protocols treat delayed messages as link failures, the model can be utilized to fine-tune timeouts. That is, for a known (or assumed) delay distribution, a timeout parameter can be translated to a failure rate. A small timeout leads accordingly to a higher failure rate, but at the same time is able to quickly detect (genuinely) lost messages and make progress. For instance, let us assume that the message delay on all links can be described with a normal distribution of mean µ = 100 ms and standard deviation σ = 10 ms. Further, we assume b stable = 0.1 for some arbitrary protocol. The timeout that keeps the protocol in the stable region is derived by finding an upper bound, where the integrated PDF of the delays is equal to 1 − b stable = 0.9. In our example, the timeout should be > 87.19 ms. To conclude, our model allows to evaluate various failure scenarios and adjust parameters accordingly.

Impact of number of processes, link, and node failures in PBFT
To better demonstrate the predictive capabilities of the model, a contour plot of P (N 3 ) for PBFT is provided in Figure 4, for varying link and crash failure rates. Additionally, the gradient is displayed, derived from the operating points for different p l and p c , as they are predicted by the model. The orientation of the arrows indicates the impact of variations in either failure rate on P (N 3 ). The more pronounced the horizontal component of a vector, the more dominant is the impact of crash failures on P (N 3 ) and the same applies to the vertical component and link failures. The contour plot allows to quickly discern the impact of either failure rate on the protocol performance. For example, for low link failure rates, i.e., p l < 0.05, changes in the link failure rate have mostly a negligible impact compared to changes in the crash failure rate. However, for very low rates of crash failures and a moderate number of link failures (p l > 0.1), the link failure rate dominates the performance of PBFT. Figure 4 also validates the observations made in Figure 3a. While the link failure rate is below the boundary, i.e., the linear slope, the crash failure rate mostly dominates the impact on the performance. For higher values of link failures, their impact increases, correlating to the steeper decline that follows after the boundary.
The influence of process numbers for a given link failure rate on PBFT is plotted in Figure 5a. While it is well known that most BFT protocols do not scale well with the number of processes due to the quadratic message complexity, it generally offers means to increase stability in the presence of dynamic link failures. In Appendix D, we show that the probability to collect a quorum for n → ∞ converges to 0 or 1, depending on p l and the quorum size. We also observe a dip in P (N 3 ), visible for fewer nodes and failure rates between 9%-15%. The dip is caused by two effects: (1) for larger n the variance of the binomial distribution increases, and (2) while the mean of the distribution narrows down on a value depending on the failure rates, the number of required messages to complete the quorum moves towards a discrete value, which is approximately 2 3 . As a consequence, the number of nodes can increase the success probability of the quorum collection phase for failure rates below a certain threshold.

Comparison between PBFT, BFT-SmaRt, Zyzzyva, and SBFT
To showcase the adaptability of our model, we applied it to Zyzzyva [19] and SBFT [16]. The detailed adaptations to the model are listed in Appendices B and C.
An exemplary comparison of all protocols for different crash failure rates is given in Figure 5b. Depicted are the overall success rates, i.e., for the Zyzzyva and SBFT the combination of fast and  slow paths. To better demonstrate the capabilities of the model, the individual success probabilities for the fast and slow path of SBFT for different link failure rates are plotted in Figures 5c and 5d. Since SBFT allows for optional, additional replicas, denoted as c, the model allows to quickly assess the protocol behavior for different failure rates and configurations of c. The plots show that SBFT outperforms PBFT for increasing numbers of c and higher failure rates, while PBFT is more stable if SBFT transitions from the fast path to the slow path.

Conclusion
The probabilistic predictions of the presented model were validated with implementations of PBFT and BFT-SMaRt for various numbers of processes and dynamic link and crash failure rates. It was demonstrated with BFT-SMaRt, Zyzzyva and SBFT, that the model can be adapted with little effort to other communication patterns of BFT protocols. The model gives a prediction of the distribution of process states during execution, allowing prediction of protocol behavior (e.g. how many view changes will occur) and therefore performance evaluation. Additionally, if the message delay statistics are known, the model can be deployed to tune the timeouts for BFT protocols, since most protocols cannot differentiate between a delayed or an omitted message, making them indifferent in their impact on the performance of the algorithm. The model allows to assess the impact of crash and link failures for various operating points of a protocol to identify key boundaries regarding protocol stability.
As was demonstrated with BFT-SMaRt, Zyzzyva and SBFT, the model can be applied to different BFT protocols by modifying the respective equations for the distributions or adding further random variables should the protocol consist of more phases (as is the case with SBFT). Further adaptations are facilitated by the fact that a body of BFT protocols are derived from the core structure of PBFT and consist of interdependent phases.
In further work, we are planning to apply the model to more BFT protocols and evaluate their performance regarding dynamic failures. Furthermore we are exploring possibilities to extend the model to predict more sophisticated key performance indicators, such as throughput and latency. Lastly, we will consider adaptations to our model in order to account for correlated link failures, e.g., as was proposed with a model by Nguyen [23].

A Model adaptations for BFT-SMaRt
In order to accurately capture the communication pattern of BFT-SMaRt, two adaptations to the model, compared to PBFT, are necessary. Firstly, the collection of prepare messages is not optimized to count the primary's pre-prepare as a prepare message. Secondly, in PBFT, the processes can only successfully complete a consensus round, if they have reached all three stages of the protocol, i.e., received a pre-prepare message and collected 2f + 1 of both, prepare and commit messages. Complementary to this, in BFT-SMaRt, a process can complete a consensus round, if it has received a pre-prepare message and collected 2f + 1 commit messages. Since the collection of 2f + 1 commit messages implies that at least f + 1 processes have received 2f + 1 prepare messages, the processes can commit safely.
Applying these differences to the model results in changes to two equations: the calculation of C 2 in (7) and C 3 in (10). Second phase: The replicas send out prepare messages.
Third phase: The replicas send out commit messages.

B Model adaptations for Zyzzyva
Zyzzyva [19] uses a primary to order requests, afterwards, the client communicates directly with the replicas to collect either 3f + 1 (fast path) or two quorums of 2f + 1 (slow path) messages. Due to the direct integration of the client into the communication patterns, the link and crash failure rates are assumed to apply to the client as well. The impact of crash failures, i.e. the calculation N i → C i , is identical for all phases. First phase: the primary broadcasts a prepare to all replicas, identical to PBFT. Second phase: the replicas respond to the client (quorum of 3f + 1 for fast path or at least 2f + 1 for slow path).

C Model adaptations for SBFT
SBFT [16] combines the properties of optimistic execution, i.e. all replicas execute in a fast path, and redundancy, i.e. additional, optional replicas. In SBFT, the network consists of 3f + 2c + 1 replicas, with c being redundant replicas. The algorithm utilizes threshold signatures to reduce the message complexity for collecting the required quorum sizes (3f +c+1 for the fast path and 2f +c+1 for the slow path). SBFT uses a primary to order requests. The impact of crash failures, i.e. the calculation N i → C i , is identical for all phases.
First phase: the primary broadcasts a prepare to all replicas, identical to PBFT. Second phase: the replicas respond to the collectors.
the conditional probability P N4|N1 (n 4 |n 1 ) is calculated in the same manner as (21). Sixth phase: the replicas respond to the collectors (slow path end).

D Convergence of 'binomial quorums'
The probability of a replica to collect a quorum of k messages, if each of the n incoming messages has an independent probability p to be omitted, can be formulated as which, considering the complementary event, can be rewritten as The binomial distribution can be approximated with the central limit theorem, or in this case, the De Moivre-Laplace theorem. The theorem states, that a binomial distribution B(n, p) for p = 0, 1 will converge to a normal distribution as n grows to infinity. The normal distribution has a mean of µ = np and standard deviation of σ = np(1 − p).
The binomial distribution can thus be approximated as This leads to a cumulative distribution function of Applying this formula to ((45)) leads to P (Q > k) = F (x = (n − k)) If n grows to infinity, we get lim n→∞ P (Q > k) = 1 2 1 + erf n − k − np Of interest here are the development of the numerator and denominator in the exponential term. The behavior of the numerator for growing n depends on the value of p and k. Considering that k, the size of the quorum, has to be a value between 1 and n, we can substitute k with qn , with q being the relative size of the quorum compared to n.