simulations/cuckoo_simulation/src/bin/old-main.rs

use std::env;
use std::process;
use rand_core::SeedableRng;
use rand_core::RngCore;
use rand_xoshiro::SplitMix64;

type NodeCount = usize;
type RegionCount = usize;
type TimeCount = usize;

#[derive(Debug, Clone, Copy)]
struct Region {
    num_honest: NodeCount,
    num_malicious: NodeCount,
    last_join: TimeCount,
}

#[derive(Debug, Clone, Copy)]
struct Quorum {
    tot_honest: NodeCount,
    tot_malicious: NodeCount,
    tot_last_join: TimeCount,
}

#[derive(Debug, Clone, Copy, Default)]
struct CurrentStats {
    dirty: bool,
    min_tot_nodes: NodeCount,
    min_tot_nodes_quorum: RegionCount,
    max_tot_nodes: NodeCount,
    max_tot_nodes_quorum: RegionCount,
    min_tot_honest: NodeCount,
    min_tot_honest_quorum: RegionCount,
    max_tot_honest: NodeCount,
    max_tot_honest_quorum: RegionCount,
    min_tot_malicious: NodeCount,
    min_tot_malicious_quorum: RegionCount,
    max_tot_malicious: NodeCount,
    max_tot_malicious_quorum: RegionCount,
    min_tot_last_join: TimeCount,
    min_tot_last_join_quorum: RegionCount,
    max_tot_last_join: TimeCount,
    max_tot_last_join_quorum: RegionCount,
    min_epsilon: f64,
    min_epsilon_quorum: RegionCount,
    max_epsilon: f64,
    max_epsilon_quorum: RegionCount,
}

impl CurrentStats {
    fn update(&mut self, i: RegionCount, q: &Quorum, force: bool) {
        if self.dirty == false && (
                self.min_tot_nodes_quorum == i ||
                self.max_tot_nodes_quorum == i ||
                self.min_tot_honest_quorum == i ||
                self.max_tot_honest_quorum == i ||
                self.min_tot_malicious_quorum == i ||
                self.max_tot_malicious_quorum == i ||
                self.min_tot_last_join_quorum == i ||
                self.max_tot_last_join_quorum == i ||
                self.min_epsilon_quorum == i ||
                self.max_epsilon_quorum == i) {
            self.dirty = true;
        }
        let nodes = q.tot_honest + q.tot_malicious;
        if force || nodes < self.min_tot_nodes {
            self.min_tot_nodes = nodes;
            self.min_tot_nodes_quorum = i;
        }
        if force || nodes > self.max_tot_nodes {
            self.max_tot_nodes = nodes;
            self.max_tot_nodes_quorum = i;
        }
        if force || q.tot_honest < self.min_tot_honest {
            self.min_tot_honest = q.tot_honest;
            self.min_tot_honest_quorum = i;
        }
        if force || q.tot_honest > self.max_tot_honest {
            self.max_tot_honest = q.tot_honest;
            self.max_tot_honest_quorum = i;
        }
        if force || q.tot_malicious < self.min_tot_malicious {
            self.min_tot_malicious = q.tot_malicious;
            self.min_tot_malicious_quorum = i;
        }
        if force || q.tot_malicious > self.max_tot_malicious {
            self.max_tot_malicious = q.tot_malicious;
            self.max_tot_malicious_quorum = i;
        }
        if force || q.tot_last_join < self.min_tot_last_join {
            self.min_tot_last_join = q.tot_last_join;
            self.min_tot_last_join_quorum = i;
        }
        if force || q.tot_last_join > self.max_tot_last_join {
            self.max_tot_last_join = q.tot_last_join;
            self.max_tot_last_join_quorum = i;
        }
        let epsilon : 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
        };
        if force || epsilon < self.min_epsilon {
            self.min_epsilon = epsilon;
            self.min_epsilon_quorum = i;
        }
        if force || epsilon > self.max_epsilon {
            self.max_epsilon = epsilon;
            self.max_epsilon_quorum = i;
        }
    }

    #[allow(dead_code)]
    fn print(&self) {
        print!("nodes {} ({}) {} ({}) ", self.min_tot_nodes, self.min_tot_nodes_quorum, self.max_tot_nodes, self.max_tot_nodes_quorum);
        print!("honest {} ({}) {} ({}) ", self.min_tot_honest, self.min_tot_honest_quorum, self.max_tot_honest, self.max_tot_honest_quorum);
        print!("malicious {} ({}) {} ({}) ", self.min_tot_malicious, self.min_tot_malicious_quorum, self.max_tot_malicious, self.max_tot_malicious_quorum);
        print!("lastjoin {} ({}) {} ({}) ", self.min_tot_last_join, self.min_tot_last_join_quorum, self.max_tot_last_join, self.max_tot_last_join_quorum);
        println!("epsilon {} ({}) {} ({})", self.min_epsilon, self.min_epsilon_quorum, self.max_epsilon, self.max_epsilon_quorum);
    }
}

#[derive(Debug, Clone, Copy, Default)]
struct CumulativeStats {
    min_tot_honest: NodeCount,
    max_tot_honest: NodeCount,
    min_tot_malicious: NodeCount,
    max_tot_malicious: NodeCount,
    min_tot_nodes: NodeCount,
    max_tot_nodes: NodeCount,
    min_age: TimeCount,
    max_age: TimeCount,
    min_epsilon: f64,
    max_epsilon: f64,
}

impl CumulativeStats {
    #[allow(dead_code)]
    fn print(&self) {
        print!("nodes {} {} ", self.min_tot_nodes, self.max_tot_nodes);
        print!("honest {} {} ", self.min_tot_honest, self.max_tot_honest);
        print!("malicious {} {} ", self.min_tot_malicious, self.max_tot_malicious);
        print!("age {} {} ", self.min_age, self.max_age);
        println!("epsilon {} {}", self.min_epsilon, self.max_epsilon);
    }
}

struct Simulation {
    done_init: bool,
    now: TimeCount,
    rand: SplitMix64,
    lg_regions_per_quorum: u8,
    num_region_mask: RegionCount,
    regions: Vec<Region>,
    quorums: Vec<Quorum>,
    cur_stats: CurrentStats,
    cum_stats: CumulativeStats,
}

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

    // Insert a new node into a random region in the DHT.
    fn insert(&mut self, is_malicious: bool) {
        let insregion = self.rand_region();
        let quorum = insregion >> self.lg_regions_per_quorum;
        if is_malicious {
            self.regions[insregion].num_malicious += 1;
            self.quorums[quorum].tot_malicious += 1;
        } else {
            self.regions[insregion].num_honest += 1;
            self.quorums[quorum].tot_honest += 1;
        }
        if self.done_init {
            self.cur_stats.update(quorum, &self.quorums[quorum], false);
        }
    }

    // Insert a new node into a random region in the DHT, then
    // evict all the other nodes in that region into random
    // regions in the DHT (but don't evict nodes from the regions
    // _those_ nodes land in).
    fn cuckoo_insert(&mut self, is_malicious: bool) {
        // Pick a random region to put the new node into. Also get the quorum for that region.
        let insregion = self.rand_region();
        let quorum = insregion >> self.lg_regions_per_quorum;
        // Kick out all nodes in that region
        // (subtract honest, malicious counts for that region from the quorum totals).
        let num_malicious = self.regions[insregion].num_malicious;
        let num_honest = self.regions[insregion].num_honest;
        self.quorums[quorum].tot_malicious -= num_malicious;
        self.quorums[quorum].tot_honest -= num_honest;
        // Insert the new node into that region.
        // Also update honest/malicious counts for region + quorum.
        if is_malicious {
            self.regions[insregion].num_malicious = 1;
            self.quorums[quorum].tot_malicious += 1;
            self.regions[insregion].num_honest = 0;
        } else {
            self.regions[insregion].num_malicious = 0;
            self.regions[insregion].num_honest = 1;
            self.quorums[quorum].tot_honest += 1;
        }
        // Re-insert each node that was kicked out earlier, into new k-regions, while maintaining
        // honest/malicious status.
        for _ in 0..num_honest {
            self.insert(false);
        }
        for _ in 0..num_malicious {
            self.insert(true);
        }
        // Update the age of the region that was emptied out.
        let last_join = self.regions[insregion].last_join;
        self.regions[insregion].last_join = self.now;
        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);
        }
    }

    fn init(&mut self, num_honest : NodeCount, num_malicious : NodeCount) {
        for _ in 0..num_honest {
            self.cuckoo_insert(false);
        }
        for _ in 0..num_malicious {
            self.cuckoo_insert(true);
        }
        self.done_init = true;
        self.cur_stats.dirty = true;
        self.collect_stats();
        self.update_cumstats(true);
    }

    fn move_malicious(&mut self) {
        // Remove an existing malicious node
        // For now, just randomly
        loop {
            let region = self.rand_region();
            let quorum = region >> self.lg_regions_per_quorum;
            if self.regions[region].num_malicious > 0 {
                self.regions[region].num_malicious -= 1;
                self.quorums[quorum].tot_malicious -= 1;
                self.cur_stats.update(quorum, &self.quorums[quorum], false);
                break;
            }
        }
        // Insert it back into the DHT
        self.cuckoo_insert(true);
    }

    #[allow(dead_code)]
    fn count_nodes(&mut self) {
        let mut num_honest : NodeCount = 0;
        let mut num_malicious : NodeCount = 0;
        let mut last_join : TimeCount = 0;
        for r in self.regions.iter() {
            num_honest += r.num_honest;
            num_malicious += r.num_malicious;
            last_join += r.last_join;
        }
        print!("regions h={} m={} l={} ", num_honest, num_malicious, last_join);
        let mut tot_honest : NodeCount = 0;
        let mut tot_malicious : NodeCount = 0;
        let mut tot_last_join : TimeCount = 0;
        for q in self.quorums.iter() {
            tot_honest += q.tot_honest;
            tot_malicious += q.tot_malicious;
            tot_last_join += q.tot_last_join;
        }
        println!("quorums h={} m={} l={}", tot_honest, tot_malicious, tot_last_join);
    }

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

    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_epsilon < self.cum_stats.min_epsilon {
            self.cum_stats.min_epsilon = stat.min_epsilon;
        }
        if force || stat.max_epsilon > self.cum_stats.max_epsilon {
            self.cum_stats.max_epsilon = stat.max_epsilon;
        }
    }
}

fn usage(cmd: &String) {
    eprintln!("Usage: {} h m lg_r lg_c iters seed", cmd);
    eprintln!("h:     number of honest nodes");
    eprintln!("m:     number of malicious nodes");
    eprintln!("lg_r:  log_2 of the number of regions");
    eprintln!("lg_c:  log_2 of the number of regions per quorum");
    eprintln!("iters: number of iterations after initialization");
    eprintln!("seed:  random seed");
}

fn main() {
    let args: Vec<String> = env::args().collect();

    if args.len() != 7 {
        usage(&args[0]);
        process::exit(1);
    }

    let arg_h = args[1].parse::<NodeCount>();
    let arg_m = args[2].parse::<NodeCount>();
    let arg_lg_r = args[3].parse::<u8>();
    let arg_lg_c = args[4].parse::<u8>();
    let arg_iters = args[5].parse::<TimeCount>();
    let arg_seed = args[6].parse::<u64>();

    if arg_h.is_err() || arg_m.is_err() || arg_lg_r.is_err() ||
            arg_lg_c.is_err() || arg_iters.is_err() || arg_seed.is_err() {
        usage(&args[0]);
        process::exit(1);
    }

    // Number of honest nodes
    let h : NodeCount = arg_h.unwrap();
    // Number of malicious nodes
    let m : NodeCount = arg_m.unwrap();
    // TODO: In the cuckoo-rule, we don't care about each region.
    //  We only care about a k-region at a time.
    //   In commensal-cuckooing, we only care about the quorum that is being joined to.
    // log_2 of number of regions
    let lg_r : u8 = arg_lg_r.unwrap();
    // log_2 of number of regions per quorum (must be smaller than r)
    let lg_c : u8 = arg_lg_c.unwrap();
    // Number of iterations after initialization
    let iters : TimeCount = arg_iters.unwrap();
    // 64-bit random seed
    let seed : u64 = arg_seed.unwrap();

    if lg_c > lg_r {
        usage(&args[0]);
        process::exit(1);
    }

    let blankregion = Region {
        num_honest: 0,
        num_malicious: 0,
        last_join: 0
    };
    let blankquorum = Quorum {
        tot_honest: 0,
        tot_malicious: 0,
        tot_last_join: 0,
    };
    let mut sim = Simulation {
        done_init: false,
        now: 0,
        rand: SplitMix64::seed_from_u64(seed),
        lg_regions_per_quorum: lg_c,
        num_region_mask: (1<<lg_r)-1,
        regions: Vec::new(),
        quorums: Vec::new(),
        cur_stats: CurrentStats::default(),
        cum_stats: CumulativeStats::default(),
    };
    sim.regions.resize(1<<lg_r, blankregion);
    sim.quorums.resize(1<<(lg_r-lg_c), blankquorum);

    eprintln!("Starting simulation h={} m={} r={} C={} seed={}",
            h, m, 1<<lg_r, 1<<lg_c, seed);

    sim.init(h, m);
    for iter in 0..iters {
        sim.move_malicious();
        if iter % 100000 == 0 {
            eprintln!("iter {}", iter);
        }
    }

    print!("{} {} {} {} {} {} ", h, m, lg_r, lg_c, iters, seed);
    sim.cum_stats.print();
}