123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284 |
- 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;
- use rand::seq::SliceRandom;
- 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
- }
- pub fn random_shuffle_regions(&mut self, n:usize) -> Vec<u32> {
- let mut vec: Vec<u32> = (0..n as u32).collect();
- vec.shuffle(&mut self.rand);
- vec
- }
- // 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) -> (bool, usize) {
- // This func will always be called after at least 1 malicious node is inserted into the quorum.
- // TODO Check: We only want to chuck out k*g'/g nodes out of the *existing* nodes in the quorum.
- // So effectively, the no. of malicious nodes is decremented by 1 here.
- let num_malicious = self.regions[region].num_malicious - 1;
- let current_region_size = num_malicious + self.regions[region].num_honest;
- let number_to_kick_out : usize = (self.k as f64 * current_region_size as f64/ self.g as f64).round() as usize;
- // println!(
- // "KICKING OUT: ***Region {}*** had {} honest {} malicious nodes = total of {} nodes.",
- // region,
- // self.regions[region].num_honest,
- // num_malicious,
- // current_region_size
- // );
- let quorum = region >> self.lg_regions_per_quorum;
- if number_to_kick_out > 0
- {
- let num_malicious_to_kick_out = self.pick_honest_malicious_nodes_to_kick_out(number_to_kick_out, current_region_size, num_malicious);
- let num_honest_to_kick_out = number_to_kick_out - num_malicious_to_kick_out;
- // println!("KICKING OUT: We choose to kick out {} honest {} malicious nodes = total of {} nodes.",
- // num_honest_to_kick_out,
- // num_malicious_to_kick_out,
- // number_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 _ctr in 0..num_honest_to_kick_out {
- let secondary_join_region = self.rand_region();
- // Don't need to check the return value as it'll continue to be true (only honest nodes were inserted)
- self.insert(false, secondary_join_region, false);
- // println!(
- // "KICKING OUT: honest node {} to region {}",
- // ctr, secondary_join_region
- // );
- }
- for ctr in 0..num_malicious_to_kick_out {
- let secondary_join_region = self.rand_region();
- let below_bmax = self.insert(true, secondary_join_region, false);
- if !below_bmax
- {
- return (below_bmax, ctr + 1);
- }
- // println!(
- // "KICKING OUT: malicious node {} to region {}",
- // ctr, secondary_join_region
- // );
- }
- return (true, num_malicious_to_kick_out)
- }
- (true, 0)
- }
- // Insert a new node into a given region in the DHT.
- fn insert(&mut self, is_malicious: bool, region: RegionCount, is_primary_join: bool) -> 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.regions[region].num_nodes_since_last_primary_join = 0
- } else {
- self.regions[region].num_nodes_since_last_primary_join += 1
- }
- if self.done_init {
- return self.cur_stats.update(quorum, &self.quorums[quorum], false);
- // if broke_b_max {
- // print!("FAILED INVARIANT b_0 < 1/3 while re-inserting cuckoo-ed out nodes");
- // }
- }
- true
- }
- pub fn init(&mut self, num_honest: NodeCount, num_malicious: NodeCount) -> (usize, bool, bool, bool, usize) {
- for _ in 0..num_honest {
- // The original honest nodes are simply "mapped" to random locations -
- let target_region = self.rand_region();
- // Don't need to check the return value as it'll always be true (b_0 max won't be broken as only honest nodes were inserted)
- self.insert(false, target_region, false);
- }
- for ctr in 0..num_malicious {
- let (inserted, inserted_below_bmax, rejoined_below_bmax, number_rejoined) = self.cuckoo_insert();
- if !inserted || !inserted_below_bmax || !rejoined_below_bmax {
- return (ctr, inserted, inserted_below_bmax, rejoined_below_bmax, number_rejoined );
- }
- }
- self.done_init = true;
- self.cur_stats.dirty = true;
- self.collect_stats();
- self.update_cumstats(true);
- (num_malicious, true, true, true, 0)
- }
- // 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) -> (bool, bool, bool, usize) {
- let regions_ordering = self.random_shuffle_regions(self.regions.len());
- // println!("Random permutation of target regions: {:?}", regions_ordering);
- for ctr in 0..regions_ordering.len() {
- // Pick a random region to put the new node into. Also get the quorum for that region.
- let region = regions_ordering[ctr] as usize;
- // println!(
- // "TRYING CUCKOO INSERT: target region {} quorum {} no. of nodes since last 1ary join {} k {}",
- // region, quorum, self.regions[region].num_nodes_since_last_primary_join, self.k
- // );
- if self.regions[region].num_nodes_since_last_primary_join >= self.k - 1 {
- // println!("------ SUCCESSFUL CUCKOO INSERT: target region {}", region);
- let below_bmax_insert_own = self.insert(true, region, true); // True for primary join
- let (below_bmax_insert_kicked_out, no_of_malicious_kicked_out) = self.kick_out_nodes(region);
- // 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 {
- // as it's being updated in the collect_stats call essentially.
- // self.cur_stats.update(quorum, &self.quorums[quorum], false);
- self.collect_stats();
- self.update_cumstats(false);
- }
- return (true, below_bmax_insert_own, below_bmax_insert_kicked_out, no_of_malicious_kicked_out)
- }
- }
- (false, true, true, 0)
- }
- // Remove an existing malicious node from the quorum that has the lowest fraction of faulty nodes
- pub fn move_malicious(&mut self) -> (bool, bool, bool, usize) {
- let find_min_b_0_region = || {
- let compute_b_0 = |r: Region| {
- (r.num_malicious as f64) / (r.num_honest as f64 + r.num_malicious as f64)
- };
- let b_0_array: Vec<f64> = self.regions.iter().map(|&q| compute_b_0(q)).collect();
- // eprintln!("b_0 array for");
- // let mut ctr: i8 = 0;
- // for &b_0 in &b_0_array {
- // print!("{} {},", ctr, b_0);
- // ctr = ctr + 1;
- // }
- // println!("\n");
- let (min_b_0_region, _) = b_0_array.iter().enumerate().fold((0, 1.0), |(min_index, min_val), (index, &val)| if val < min_val && val > 0.0 {
- // eprintln!(
- // "Replacing {} index {} with current val {} index {}",
- // min_val, min_index, val, index
- // );
- (index, val)
- } else {
- (min_index, min_val)
- });
- min_b_0_region
- };
- // Pick quorum with least fraction of byz nodes
- let min_b_0_region = find_min_b_0_region();
- let min_b_0_quorum = min_b_0_region >> self.lg_regions_per_quorum;
- // eprintln!(
- // "MOVE MALICIOUS out of region {} which has {} honest {} malicious nodes",
- // min_b_0_region,
- // self.regions[min_b_0_region].num_honest,
- // self.regions[min_b_0_region].num_malicious
- // );
- self.regions[min_b_0_region].num_malicious -= 1;
- self.quorums[min_b_0_quorum].tot_malicious -= 1;
- // Don't need to check return value as b_0 for min_b_0_quorum decreases.
- self.cur_stats
- .update(min_b_0_quorum, &self.quorums[min_b_0_quorum], false);
- // Insert it back into the DHT
- return 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;
- }
- }
- }
|