median_descendants_chain_length_to_meet_threshold.rs

Overview

This file provides the implementation of the BlockStatistics struct, which maintains a sliding window of numeric statistics representing descendants chain lengths in a blockchain context. It dynamically computes and updates the median value of these chain lengths to meet a certain threshold. This median is used as a parameter (denoted as (\beta)) which adjusts over time based on incoming data. The primary functionality centers on maintaining and updating these statistics efficiently, including resizing the window and recalculating the median after new data is incorporated.

The file handles the storage, update, and median calculation of a fixed-size window of unsigned integer statistics, facilitating adaptive thresholding for descendant chain lengths within the system.

BlockStatistics Struct

Description

BlockStatistics is a data structure designed to track a rolling set of statistics (usize values) over a fixed-size window. It stores values related to descendants chain lengths and allows dynamic adjustment of the window size and recalculation of the median value of the stored statistics.

Fields

Traits Implemented

• Clone

• Serialize and Deserialize (from serde crate for serialization support)

• PartialEq

• Debug

Methods

zero

pub fn zero(
    initial_window_size: NonZeroUsize,
    preset_median_descendants_chain_length_to_meet_threshold: NonZeroUsize,
) -> Self

Description

Creates a new BlockStatistics instance with an initialized window filled with a preset median value. The window size is specified by initial_window_size. The median threshold is initialized to the provided preset value.

Parameters

• initial_window_size: NonZeroUsize — The size of the initial window for statistics storage. Must be non-zero.

• preset_median_descendants_chain_length_to_meet_threshold: NonZeroUsize — The initial median threshold value to fill the window.

Returns

• Self — A new BlockStatistics instance with stats initialized to the preset median value repeated initial_window_size times.

Usage Example

use std::num::NonZeroUsize;

let initial_size = NonZeroUsize::new(10).unwrap();
let preset_median = NonZeroUsize::new(5).unwrap();

let block_stats = BlockStatistics::zero(initial_size, preset_median);

median_descendants_chain_length_to_meet_threshold

pub fn median_descendants_chain_length_to_meet_threshold(&self) -> usize

Description

Returns the current median threshold value representing the median descendants chain length.

Parameters

• None

Returns

• usize — The median descendants chain length threshold.

Usage Example

let median = block_stats.median_descendants_chain_length_to_meet_threshold();
println!("Median threshold: {}", median);

next

pub fn next(
    mut self,
    finalization_distances_sorted_by_seq_no: &[usize],
    new_window_size: Option<usize>,
) -> Self

Description

Consumes the existing BlockStatistics instance and returns an updated instance after incorporating new finalization distances. This method updates the stats vector with new data, optionally resizes the sliding window, recalculates the median of the stored values, and updates the median threshold accordingly.

The window size can be dynamically changed via the new_window_size optional parameter. Resizing truncates or extends the stats vector, filling new entries with the current median threshold.

Parameters

• self: Consumed instance of BlockStatistics.

• finalization_distances_sorted_by_seq_no: &[usize] — A slice of new descendants chain length values, sorted by sequence number.

• new_window_size: Option<usize> — Optional new size for the sliding window. If None, the existing size is retained.

Returns

• Self — Updated BlockStatistics instance with incorporated data and recalculated median.

Important Details

• Window resizing does not preserve the oldest data correctly; it may remove random chunks. There is a TODO note indicating the need to implement correct aging behavior by removing the oldest entries relative to cursor.

• The median is calculated using select_nth_unstable for efficiency, selecting the middle element in the sorted order.

• The median threshold is always set to at least 1 to avoid zero values.

Usage Example

let updated_block_stats = block_stats.next(&[3, 4, 2, 5], Some(15));
println!("Updated median: {}", updated_block_stats.median_descendants_chain_length_to_meet_threshold());

Implementation Details and Algorithms

• Sliding Window Buffer: The stats vector acts as a fixed-size circular buffer, with cursor tracking the insertion point. New values overwrite old ones in a wrap-around fashion.

• Median Calculation: Uses Rust's select_nth_unstable method to efficiently find the median element (middle value) without fully sorting the vector.

• Dynamic Window Resizing: The vector can be resized dynamically to a new window size. Newly added elements during an increase are initialized to the current median value.

• Minimum Median Threshold: Ensures the median threshold is never zero by setting a minimum value of 1.

Interaction with Other System Components

This file likely interacts with components responsible for:

• Receiving or calculating finalization distances sorted by sequence number, which represent blockchain descendants chain lengths.

• Managing thresholds for block validation, finalization, or other consensus-related mechanisms that require dynamic adjustment of parameters based on observed chain lengths.

• Serialization and deserialization processes, as the struct supports these traits for persistence or network transmission.

The BlockStatistics struct may be used within consensus modules, data aggregation layers, or parameter tuning subsystems where descendant chain lengths inform adaptive thresholding.

Mermaid Diagram

classDiagram
class BlockStatistics {
-stats: Vec<usize>
-cursor: usize
-median_descendants_chain_length_to_meet_threshold: usize
+zero()
+median_descendants_chain_length_to_meet_threshold()
+next()
}

This diagram shows the BlockStatistics class with its internal fields and public methods, illustrating the encapsulated state and operations for managing the descendants chain length statistics and median threshold.