dueling_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 ~90% chance of dueling candidates?
# Answer: 36ish
# Based on:
# https://codecalamity.com/the-birthday-paradox-the-proof-is-in-the-python/
from random import randint
import matplotlib.pyplot as plt
from multiprocessing import Pool, cpu_count
from bisect import bisect
import matplotlib.pyplot as plt

WAIT_MIN = 1
WAIT_MAX = 10
MAX_NODES = 60    # Almost 100% chance

def random_timeouts(nodes):
    return [randint(WAIT_MIN, WAIT_MAX) for _ in range(nodes)]

def determine_probability(nodes, run_amount=10000):
    duplicate_minimum_found_cnt = 0
    for _ in range(run_amount):
        timeouts = random_timeouts(nodes)
        duplicates = set(x for x in timeouts if timeouts.count(x) > 1)
        if len(duplicates) > 0 and min(duplicates) == min(timeouts):
            # There is (at least) a duplicate
            # and (the smallest duplicate) is the smallest timeout
            duplicate_minimum_found_cnt += 1

    # 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=90):
    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("dueling_candidates.png")

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