Probability of a peer in memberlist not receiving a message

memberlist.go

// Modeled on
// https://github.com/hashicorp/memberlist/blob/0b981/state.go#L478-L501
package main

import (
	"fmt"
	"math"
	"math/rand"
)

func main() {
	retransmits := 3
	k := 3
	nodes := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	filterFn := func(n int) bool {
		if n == 0 {
			return true
		}

		return false
	}
	var partial int
	total := 600000
	// map[numReturned]occurrences
	resMap := make(map[int]int)
	for i := 0; i < total; i++ {
		res := kRandomNodes(k, nodes, filterFn)
		if len(res) < len(nodes)-1 {
			partial++
		}
		// Zero value is 0
		resMap[len(res)] = resMap[len(res)] + 1
	}

	fmt.Printf("percentage not returning all peers: %.4f\n", float64(partial)/float64(total)*100.0)
	var pTotal float64
	for numFound, occurrences := range resMap {
		// numFound is the number of nodes picked, but a message will
		// only be sent `retransmits` times, so we take the smaller of
		// the two.
		numSent := math.Min(float64(numFound), float64(retransmits))

		// Calculuate the probability of a message being missed
		// - numSent/len(nodes)-1 is p(receiving a message)
		// - 1-p(receiving a message) is p(not receiving a message)
		p := 1.0 - (numSent / float64(len(nodes)-1))

		// how many times this was observed to happen in the trials run.
		p *= float64(occurrences) / float64(total)
		pTotal += p
		fmt.Printf("%d nodes sending (happened %dx): probability of not receiving a message %.4f\n", numFound, occurrences, p*100.0)
	}

	// pTotal has the probability of a single node not receiving a message
	// from another node.
	// pTotal ^ (nodes.len - 1) is the probability of a node not receiving
	// the message from any other node.
	fmt.Printf("probability of not receiving a message (1 sender): %.4f\n", pTotal*100.0)
	senders := len(nodes) - 1
	fmt.Printf("probability of not receiving a message (%d senders): %.4f\n", senders, math.Pow(pTotal, float64(senders))*100.0)
}

func kRandomNodes(k int, nodes []int, filterFn func(int) bool) []int {
	n := len(nodes)
	kNodes := make([]int, 0, k)
OUTER:
	// Probe up to 3*n times, with large n this is not necessary
	// since k << n, but with small n we want search to be
	// exhaustive
	for i := 0; i < 3*n && len(kNodes) < k; i++ {
		// Get random node
		idx := randomOffset(n)
		node := nodes[idx]

		// Give the filter a shot at it.
		if filterFn != nil && filterFn(node) {
			continue OUTER
		}

		// Check if we have this node already
		for j := 0; j < len(kNodes); j++ {
			if node == kNodes[j] {
				continue OUTER
			}
		}

		// Append the node
		kNodes = append(kNodes, node)
	}
	return kNodes
}

func randomOffset(n int) int {
	if n == 0 {
		return 0
	}
	return int(rand.Uint32() % uint32(n))
}