simulations/cuckoo_simulation/src/sim.rs

use crate::types::*;
// use rand_xoshiro::{SplitMix64, rand_core::RngCore};
use crate::stats::{CumulativeStats, CurrentStats};
use reservoir_sampling::unweighted::core::l;
use rand_pcg::Pcg64;
use rand::RngCore;

pub struct Simulation {
    pub done_init: bool,
    pub now: TimeCount,
    pub quorums: Vec<Quorum>,
    pub regions: Vec<Region>,
    pub rand: Pcg64,
    pub lg_regions_per_quorum: RegionCount,
    pub num_region_mask: RegionCount,
    pub cur_stats: CurrentStats,
    pub cum_stats: CumulativeStats,
    pub k: NodeCount,
    pub g: NodeCount,
}

impl Simulation {
    fn rand_region(&mut self) -> RegionCount {
        (self.rand.next_u64() as RegionCount) & self.num_region_mask
    }

    // Reservoir-sampling to pick which nodes to kick out for CCR
    fn pick_honest_malicious_nodes_to_kick_out(&mut self, m: NodeCount, n: NodeCount, n_bad: NodeCount) -> NodeCount {
        let mut selected_indices: Vec<usize> = vec![0usize; m as usize];
        // Picks m indices out of 0..n using the optimized L reservoir sampling algo.
        l(0usize..n, selected_indices.as_mut_slice(), &mut self.rand);
        // First 0..n_bad - 1 indices out of total are treated as malicious
        let num_bad = selected_indices.iter().fold(0, |bad_count, &index| if index < n_bad { bad_count + 1 } else { bad_count });
        num_bad
    }

    // Kick-out nodes as per CCR.
    fn kick_out_nodes(&mut self, region: RegionCount) {
        let quorum = region >> self.lg_regions_per_quorum;
        let current_region_size = self.regions[region].num_malicious + self.regions[region].num_honest;
        let number_to_kick_out : usize = ((self.k * current_region_size / self.g ) as f64).round() as usize;
        let num_malicious_to_kick_out = self.pick_honest_malicious_nodes_to_kick_out(number_to_kick_out, current_region_size, self.regions[region].num_malicious);
        let num_honest_to_kick_out = number_to_kick_out - num_malicious_to_kick_out;

        self.regions[region].num_malicious -= num_malicious_to_kick_out;
        self.regions[region].num_honest -= num_honest_to_kick_out;
        self.quorums[quorum].tot_malicious -= num_malicious_to_kick_out;
        self.quorums[quorum].tot_honest -= num_honest_to_kick_out;

        // Re-insert each node that was kicked out earlier, into new quorums, while maintaining
        // honest/malicious status.
        for _ in 0..num_honest_to_kick_out {
            let secondary_join_region = self.rand_region();
            self.insert(false, secondary_join_region, false);
        }
        for _ in 0..num_malicious_to_kick_out {
            let secondary_join_region = self.rand_region();
            self.insert(true, secondary_join_region, false);
        }
    }

    // Insert a new node into a given region in the DHT.
    fn insert(&mut self, is_malicious: bool, region: RegionCount, is_primary_join: bool) {
        let quorum = region >> self.lg_regions_per_quorum;

        // Insert the new node into that region.
        // Also update honest/malicious counts for region + quorum.
        if is_malicious {
            self.regions[region].num_malicious += 1;
            self.quorums[quorum].tot_malicious += 1;
        } else {
            self.regions[region].num_honest += 1;
            self.quorums[quorum].tot_honest += 1;
        }
        if is_primary_join {
            self.quorums[quorum].num_nodes_since_last_primary_join = 0
        } else {
            self.quorums[quorum].num_nodes_since_last_primary_join += 1
        }
        if self.done_init {
            self.cur_stats.update(quorum, &self.quorums[quorum], false);
        }
    }

    pub fn init(&mut self, num_honest: NodeCount, num_malicious: NodeCount) {
        for _ in 0..num_honest {
            // The original honest nodes are simply "mapped" to random locations -
            let target_region = self.rand_region();
            self.insert(false, target_region, false);
        }
        for _ in 0..num_malicious {
            self.cuckoo_insert();
        }
        self.done_init = true;
        self.cur_stats.dirty = true;
        self.collect_stats();
        self.update_cumstats(true);
    }

    // Insert a new node into a random region in the DHT, then
    // evict a fraction of nodes in that region into random
    // regions in the DHT (but don't evict nodes from the regions
    // _those_ nodes land in).
    pub fn cuckoo_insert(&mut self) {
        loop {
            // Pick a random region to put the new node into. Also get the quorum for that region.
            let region = self.rand_region();
            let quorum = region >> self.lg_regions_per_quorum;

            if self.quorums[quorum].num_nodes_since_last_primary_join >= self.k - 1 {
                self.kick_out_nodes(region);
                self.insert(true, region, true); // True for primary join

                // Update the age of the region that was emptied out.
                // self.quorums[quorum].tot_last_join += self.now - last_join;
                self.now += 1;
                // Cuckoo-ing after initialization: update stats for the quorum with the cuckood-out region
                if self.done_init {
                    self.cur_stats.update(quorum, &self.quorums[quorum], false);
                    self.collect_stats();
                    self.update_cumstats(false);
                }
                break;
            }
        }
    }

    // Remove an existing malicious node from the quorum that has the lowest fraction of faulty nodes
    pub fn move_malicious(&mut self) {
        let find_min_b_0_quorum = || {
            let compute_b_0 = |q: Quorum| {
                let b_0: f64 = if q.tot_honest > 0 {
                    (q.tot_malicious as f64) /
                        (q.tot_honest as f64)
                } else if q.tot_malicious > 0 {
                    1000000.0
                } else {
                    0.0
                };
                b_0
            };

            let b_0_array: Vec<f64> = self.quorums.iter().map(|&q| compute_b_0(q)).collect();
            let (min_b_0_quorum, _) = b_0_array.iter().enumerate().fold((0, 0.0), |(min_index, min_val), (index, &val)| if val < min_val {
                (index, val)
            } else {
                (min_index, min_val)
            });

            min_b_0_quorum
        };

        // Pick quorum with least fraction of byz nodes
        let min_b_0_quorum = find_min_b_0_quorum();
        if self.quorums[min_b_0_quorum].tot_malicious > 0 {
            self.quorums[min_b_0_quorum].tot_malicious -= 1;
            self.cur_stats.update(min_b_0_quorum, &self.quorums[min_b_0_quorum], false);

            // Insert it back into the DHT
            self.cuckoo_insert();
        }
    }

    pub fn collect_stats(&mut self) {
        if self.cur_stats.dirty {
            for (i, q) in self.quorums.iter().enumerate() {
                self.cur_stats.update(i, q, i==0);
            }
            self.cur_stats.dirty = false;
        }
    }

    pub fn update_cumstats(&mut self, force: bool) {
        let stat = &self.cur_stats;
        if force || stat.min_tot_nodes < self.cum_stats.min_tot_nodes {
            self.cum_stats.min_tot_nodes = stat.min_tot_nodes;
        }
        if force || stat.max_tot_nodes > self.cum_stats.max_tot_nodes {
            self.cum_stats.max_tot_nodes = stat.max_tot_nodes;
        }
        if force || stat.min_tot_honest < self.cum_stats.min_tot_honest {
            self.cum_stats.min_tot_honest = stat.min_tot_honest;
        }
        if force || stat.max_tot_honest > self.cum_stats.max_tot_honest {
            self.cum_stats.max_tot_honest = stat.max_tot_honest;
        }
        if force || stat.min_tot_malicious < self.cum_stats.min_tot_malicious {
            self.cum_stats.min_tot_malicious = stat.min_tot_malicious;
        }
        if force || stat.max_tot_malicious > self.cum_stats.max_tot_malicious {
            self.cum_stats.max_tot_malicious = stat.max_tot_malicious;
        }
/*        let min_age = (self.now<<self.lg_regions_per_quorum) - stat.max_tot_last_join;
        let max_age = (self.now<<self.lg_regions_per_quorum) - stat.min_tot_last_join;
        if force || min_age < self.cum_stats.min_age {
            self.cum_stats.min_age = min_age;
        }
        if force || max_age > self.cum_stats.max_age {
            self.cum_stats.max_age = max_age;
        }
*/        if force || stat.min_b_0 < self.cum_stats.min_b_0 {
            self.cum_stats.min_b_0 = stat.min_b_0;
        }
        if force || stat.max_b_0 > self.cum_stats.max_b_0 {
            self.cum_stats.max_b_0 = stat.max_b_0;

        }
    }




}