Progressive state transfer for BFT with larger-than-memory state

• Introduces a novel checkpoint algorithm for divisible states, possibly larger-than-memory, named Progressive State Transfer, that partitions states into smaller components for faster, efficient fault recovery in large persistent systems. • Defines divisible state and state partition formally, proposing a generalized methodology and differential checkpoint algorithm for key-value stores, enabling customizable part sizes, and allowing distributing the recovery effort across all replicas. • Separates transfer process from checkpoint creation, allowing the development of application-specific partitioning methods using the proposed state transfer method for generic parts. • Analyzes and compares our algorithm experimentally with a nondivisible, i.e., the traditional approach, state algorithm, highlighting advantages, disadvantages, and suitable scenarios for each. Efficient recovery of replicas is a key but often overlooked practical requirement to make Byzantine Fault Tolerant State Machine Replication (BFT-SMR) systems viable for real world use. The state transfer part of recovery consists of transferring a checkpoint of the state and a log of operations executed after the checkpoint was created. Unlike the log, which is efficient to record, and often bounded, checkpoints grow according to the state size. Consequently, the transfer and creation of checkpoints can have increasingly negative impacts on system performance. In this paper, we introduce Progressive State Transfer, a checkpoint state transfer algorithm that is designed for divisible state applications. Along with this algorithm, we explore the concept of divisible state, presenting a differential checkpoint creation method that builds partitioned incremental checkpoints. Progressive state transfer receives small parts rather than a complete state, which allows us to reduce the amount of information transferred from other replicas. Moreover, it allows a recovering replica to gather parts in parallel from different replicas, further reducing recovery time and balancing effort across replicas. We also present a differential checkpoint algorithm, that only updates the parts of the state that changed since the last checkpoint; this enables checkpoints to be performed incrementally and thus can vastly reduce checkpoint times in sizable states, consequently minimizing the impact of checkpointing on overall throughput. In our analysis, we compare our approach to a traditional non-divisible checkpoint algorithm, examining the differences in performance. The findings indicate that progressive state transfer can lead to a significant reduction in state transfer time, achieving up to twelve times faster transfers under similar conditions. Additionally, the implementation of differential checkpoints shows improved performance, maintaining similar levels of performance in less optimal scenarios.