Last active
June 1, 2018 15:52
Probability of a peer in memberlist not receiving a message
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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)) | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment