Raft dueling candidates with power distribution

candidates.py

# What if n nodes are assigned a random tick wait (of 1 to 10)
# to wait to become candidates when the previous leader is down?
# What is the chance of 2 candidates having the same random
# wait (birthday paradox) AND this wait to be the shortest wait.
# What's the amount of nodes with ~XX% chance of dueling candidates?
# Based on:
# https://codecalamity.com/the-birthday-paradox-the-proof-is-in-the-python/
#
# For power distribution
#
#   For [1,10]
#   Shape    50%
#     1       13     (uniform)
#     2       64
#     3      138
#     4      235
#     5      295
#
from random import randint
import matplotlib.pyplot as plt
from multiprocessing import Pool, cpu_count
from bisect import bisect
import matplotlib.pyplot as plt
import numpy as np

WAIT_MIN = 1
WAIT_MAX = 10
MAX_NODES = 250      # Make it close to 100% chance
PERC_THRESHOLD = 50  # Find 50% chance of dueling
SHAPE_PARAM = 4      # Power distribution shape

rng = np.random.default_rng(12345)

def random_timeouts(nodes):
    return (np.random.power(SHAPE_PARAM, nodes) * WAIT_MAX + 1).astype(int)

def determine_probability(nodes, run_amount=10000):
    duplicate_minimum_found_cnt = 0
    for _ in range(run_amount):
        timeouts = random_timeouts(nodes)
        # minimum value is repeated
        try:
            duplicate_minimum_found_cnt += (np.count_nonzero(timeouts == timeouts.min()) > 1)
        except ValueError:
            # empty
            pass

    # return node number for sorting all subprocess results
    return nodes, duplicate_minimum_found_cnt/run_amount * 100

def plot_candidate_probabilities(max_nodes, perc_threshold=PERC_THRESHOLD):
    with Pool(processes=cpu_count()) as p:
        percent_chances = p.map(determine_probability, range(max_nodes))

    res = sorted(percent_chances, key=lambda x: x[0]) # results by x
    res_y = [z[1] for z in res]  # y values (discard x, now implicit)

    plt.plot(res_y)              # plot it
    plt.xlabel("Number of nodes")
    plt.ylabel('Chance of dueling candidates (Percentage)')

    idx_threshold = bisect(res_y, perc_threshold)
    if max_nodes > idx_threshold:
        print(f"{perc_threshold}% cutoff is {idx_threshold}: {res_y[idx_threshold]}%")
        plt.axvline(x=idx_threshold, color='red')
        plt.text(idx_threshold, 0, str(idx_threshold), color='red')
    else:
        print("all below 90%, try again")

    plt.savefig(f"dueling_candidates_power_{SHAPE_PARAM}.png")

if __name__ == '__main__':
    plot_candidate_probabilities(MAX_NODES)

Shape 1 (uniform):

Shape 2:

Shape 3:

Shape 4:

Shape 5: