Source-linked AI summary
Performance Analysis of the Raft Consensus Algorithm for Private Blockchains
Dongyan Huang, Xiaoli Ma, Shengli Zhang
TL;DR
Network stability in Raft-based private blockchains is studied because packet loss can cause network splits, yet theoretical analysis of this effect is limited. The paper develops a Markov-based analytical model for split probability and validates it with simulation. The model matches simulation results and quantifies how packet loss, election timeout, and network size affect stability and split time.
Problem
The paper addresses limited theoretical analysis of Raft network splits under packet loss, which can make a blockchain network unavailable.
Method
It models follower timeout and candidate transitions analytically, deriving network-split probability from the resulting process.
Results
Analytical results match 10,000-trial simulation results for network-split CDFs across network sizes, timeout values, and packet-loss rates.
Takeaways & Limitations
The model provides reference values for detecting abnormal network conditions and guidance for selecting Raft parameters.
Abstract
from arXiv · showhide
Consensus is one of the key problems in blockchains. There are many articles analyzing the performance of threat models for blockchains. But the network stability seems lack of attention, which in fact affects the blockchain performance. This paper studies the performance of a well adopted consensus algorithm, Raft, in networks with non-negligible packet loss rate. In particular, we propose a simple but accurate analytical model to analyze the distributed network split probability. At a given time, we explicitly present the network split probability as a function of the network size, the packet loss rate, and the election timeout period. To validate our analysis, we implement a Raft simulator and the simulation results coincide with the analytical results. With the proposed model, one can predict the network split time and probability in theory and optimize the parameters in Raft consensus algorithm.
I. INTRODUCTION
Private blockchains favor efficient consensus because participants are verified, while Raft’s network-split behavior under packet loss lacks sufficient theoretical analysis. This paper develops a model relating network-split performance to packet loss, election timeout, and network size.
- Consensus algorithms coordinate distributed nodes and are central to blockchain safety and efficiency.
- Private blockchain participants are whitelisted and contractually bound, making efficient algorithms such as PBFT and Raft appropriate.
- Raft combines high efficiency and simplicity with leader-based consensus, but cannot tolerate malicious nodes.
- A network split occurs when more than half the nodes leave the leader’s control, triggering leader election and stopping new transactions.
- Existing blockchain research lacks theoretical network-split analysis and rarely considers packet-loss effects.
- The paper develops an analytical model, derives normal-network performance, and studies packet loss, election timeout, and network size.
II. REVIEW OF RAFT ALGORITHM
Raft organizes consensus around leader election, heartbeats, and follower state transitions. Election timeouts and randomized timers govern when followers become candidates and help prevent simultaneous candidacies.
- Raft nodes occupy leader, follower, or candidate states, and a candidate becomes leader after receiving votes from a majority.
- In normal operation, one leader sends periodic heartbeats while transactions flow through that leader to followers.
- The election timeout is the wait before a follower becomes a candidate when heartbeats are not received.
- Nodes that do not receive heartbeats time out and start new elections.
- Figure 1 presents Raft’s state-transition model.
- Randomized election timers reduce the probability that several followers become candidates simultaneously.
III. SYSTEM MODEL
The system model considers an odd-sized Raft network with packet-loss-driven communication failures and separates follower-to-candidate transitions from network-level split analysis.
- The analysis assumes a distributed network with N nodes, odd N, heartbeat intervals much shorter than election timeouts, and infrequent node failures.
- A network split means more than half the nodes leave the leader’s control.
- The model treats one follower’s transition to candidate as an absorbing Markov chain and derives network-split probability from it.
- The analysis also derives the expected follower-to-candidate transition time and expected number of received heartbeats.
- Within a term, the initial state follows a successfully received heartbeat that resets the follower’s election counter.
A. Network model
The network model represents heartbeat reception and election-counter expiration as a Markov process. It supports fixed or randomized election timeouts and distinguishes transient states from absorbing candidate states.
- A. Network model: K equals the number of consecutive missed heartbeats required for a follower to become a candidate.K = ⌊Et/h⌋, with timeout values derived from the interval [a, b].
- A. Network model: Packet loss probability p is modeled as constant for a given network, while election timeout K may be uniformly randomized.
- A. Network model: The Markov state tracks timeout stage g(n) and remaining election-counter steps b(n), assuming these processes are independent.
- A. Network model: Heartbeat loss decrements the election counter, heartbeat reception resets it, and reaching zero transitions the follower to candidate.
- A. Network model: Candidate states are absorbing, while all other states are transient in the canonical transition-matrix form.
- A. Network model: For a fixed timeout K, the transition matrix uses K + 1 states; the randomized-timeout case extends the analysis across timeout values.
1) Network split probability:
The paper models network split probability by tracking follower-to-candidate transitions and the resulting number of candidates over time. A split occurs when more than half of the nodes become candidates, and the probability is derived from the transition model.
- A network split occurs when more than half of N nodes become candidates, leaving the leader unqualified.
- The network split probability before step n is the probability that more than half of the followers become candidates by that step.
- The probability that a follower becomes a candidate before step n is represented by an entry of the transition matrix power P^n.
- Assuming independent followers, the number of candidates before step n follows a binomial distribution.
- For sufficiently small per-follower transition probability, the candidate count is approximated by a Poisson random variable.
2) The average number of replies:
The analysis uses the candidate and follower counts to derive the leader’s average number of collected replies at each step.
- The expected number of candidates at step n is derived from the binomial candidate-count model.
- The expected number of followers at step n is derived alongside the expected candidate count.
- The leader’s average number of collected replies at step n is then obtained from the expected follower count.
3) The expected number of received heartbeats for a follower:
The paper derives the expected number of heartbeats a follower receives before becoming a candidate using the fundamental matrix of an absorbing Markov chain.
- Starting from the initial state, n11 is the expected number of received heartbeats before a follower transfers to candidate state.
- Each entry of N gives the expected number of visits to a transient state from a specified starting state.
- Because Q^n approaches zero, the fundamental matrix satisfies N = (I − Q)^−1 = I + Q + Q^2 + ···.
4) Time to transition to candidate:
The paper derives expected heartbeat counts and transition time for a follower moving from the initial state to candidate state, using the absorbing Markov-chain fundamental matrix.
- The expected transition time is obtained by summing the fundamental matrix entries n1j across transient states.Each n1j represents the expected number of visits to transient state sj from the initial state.
- The average interval between received heartbeats is derived for a follower during one term.
IV. SIMULATION RESULTS
Simulation results validate the analytical model and examine how packet loss, election timeout, and network size affect Raft network split behavior and stability.
- Analytical CDF results match Raft simulator results for network split timing across the evaluated settings.Figures 2–3 summarize 10,000 simulated trials for each setting.
- Network split probability decreases as packet loss rate p or election timeout value K increases for a fixed network size.
- Larger networks have lower split probability initially but higher split probability after running time passes a certain point.The transition probability of individual followers increases over time, changing the network-size relationship.
- Larger networks have smaller variance in split time, while their expected split time is very close to that of smaller networks.The paper characterizes this as better stability in terms of network split time.
- At p = 0.1 and N = 5, increasing K from 3 to 4 raises expected split time from about 1,000 to 10,000.At p = 0.3 and N = 5, the corresponding values are about 50 and 110.
- Packet loss strongly affects received-heartbeat intervals, whereas election timeout has an insignificant effect and the interval approaches a constant as timeout increases.
V. CONCLUSION
The paper proposes an analytical model for Raft network-split probability that supports parameter guidance and network-condition monitoring, with simulations matching the analytical results.
- The analytical model estimates Raft network-split probability and guides parameter selection, including election timeout, packet loss rate, and network size.
- Simulation results match the analytical results well, supporting the model’s use for evaluating network performance.
- Increasing election timeout lowers network-split probability caused by packet loss.
- Larger networks have smaller split probability at the beginning of running time and more focused splitting time than smaller networks.
APPENDIX
The appendix establishes convergence properties for the matrix Q and includes figures concerning network-split-time variability and follower heartbeat intervals.
- All absolute eigenvalues of Q are strictly less than 1.
- The appendix applies the Gershgorin circle theorem to analyze eigenvalues of the K × K matrix Q.
- Figures 8 and 9 address network-split-time variance under packet loss and the average follower heartbeat-receipt interval, respectively.
- The matrix entries qij are identified as the (i, j)th elements of Q.
- The appendix states lim n→∞ Q^n = 0 after representing Q through its eigenvalue decomposition.