Avalanche Snow consensus in javascript

snow-consensus.js

class Validator {
    constructor(id, preference) {
        this.id = id;
        this.preference = preference;
        this.decided = false;
    }
}

const describeValidators = (validators) => {
    const preferences = {};
    for (const validator of validators) {
        const preference = validator.preference;
        preferences[preference] = (preferences[preference] || 0) + 1;
    }
    const numValidators = validators.length;
    let maxPrefererenceCount = 0;
    let maxPreference = null;
    for (const [preference, count] of Object.entries(preferences)) {
        if (count >= maxPrefererenceCount) {
            maxPrefererenceCount = count;
            maxPreference = preference;
        }
    }
    return {numValidators, preferences, maxPreference};
}

const randomPreference = (numPreferences) => {
    return String.fromCharCode(Math.floor(Math.random() * numPreferences) + 65);
}

const createValidators = (numValidators, numPreferences) => {
    return new Array(numValidators).fill(null).map((_, i) => 
        new Validator(i, randomPreference(numPreferences)));
}

/**
 * Sample a subset of validators from the group of validators
 * @param {*} arr - The group of validators
 * @param {*} k - the number of validators to select
 */
const sample = (arr, k, self) => {
    const result = [];
    const used = new Set();
    let i = 0;
    while (i < k) {
        const index = Math.floor(Math.random() * arr.length);
        const validator = arr[index];
        if (index === self) continue;
        if (used.has(validator.id)) continue;
        used.add(validator.id);
        result.push(validator);
        ++i;
    }
    return result;
}

/**
 * 
 * @param {*} validators - The group of validators trying to achieve consensus
 * @param {*} sampleSize - The sample size of validators to query of the subset of validators
 * @param {*} quorumSize - quorum size - between 1 and k, 14, 
 *      the number of validators who must agree to change the preference
 * @param {*} decisionThreshold - The number of times where a quorum of validators must be reached to acheive consenus
 */
const getConsensus = (validators, sampleSize = 20, quorumSize = 14, decisionThreshold = 20) => {
    // Make a copy of the validators
    let iterations = 0;
    validators = validators.map(v => { return {...v}; });
    let undecidedValidators = validators.filter(person => !person.decided);
    let consecutiveSuccesses = 0;
    while (undecidedValidators.length > 0) {
        for (const person of undecidedValidators) {
            const sampleValidators = sample(validators, sampleSize, person.id);
            // Get number of validators who prefer a given preference
            const preferenceCount = {};
            for (const sampleValidator of sampleValidators) {
                const preference = sampleValidator.preference;
                preferenceCount[preference] = (preferenceCount[preference] || 0) + 1;
            }
            let maxPreference = null;
            let maxCount = 0;
            for (const [preference, count] of Object.entries(preferenceCount)) {
                if (count >= maxCount) {
                    maxPreference = preference;
                    maxCount = count;
                }
            }
            if (maxCount >= quorumSize) {
                const oldPreference = person.preference;
                person.preference = maxPreference;
                validators.splice(person.id, 1, person);
                if (oldPreference === maxPreference) {
                    ++consecutiveSuccesses;
                } else {
                    consecutiveSuccesses = 1;
                }
            } else {
                consecutiveSuccesses = 0;
            }
            if (consecutiveSuccesses >= decisionThreshold) {
                person.decided = true;
            }
        }
        undecidedValidators = validators.filter(person => !person.decided);
    }
    return validators;
};

const iterations = 10;
let timesConsensusCorrect = 0;
let timesConsensusIncorrect = 0;

const NUM_VALIDATORS = 1203;
const NUM_PREFERENCES = 2;

console.log(`Testing the SNOW consensus algorithm ${iterations} times`);
for(let i = 0; i < iterations; i++) {
    const validators = createValidators(NUM_VALIDATORS, NUM_PREFERENCES);
    const maxPreference = describeValidators(validators).maxPreference;
    const consensus = getConsensus(validators);
    const afterConsensusPreference = describeValidators(consensus).maxPreference;
    if (maxPreference === afterConsensusPreference) {
        ++timesConsensusCorrect;
    } else {
        ++timesConsensusIncorrect;
        console.log("Incorrect consensus: ");
        console.log(describeValidators(validators));
        console.log(describeValidators(consensus));
    }
}

console.log(`Times Consensus correct: ${timesConsensusCorrect}`);
console.log(`Times Consensus incorrect: ${timesConsensusIncorrect}`);
console.log(`Percentage Consensus correct: ${(timesConsensusCorrect / iterations) * 100}%`);

// console.log(validators);