123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214 |
- 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;
- }
- }
- }
|