I recently found out that to access a distributed network you need to contact bootstrap nodes in order to get onto the network. This troubled me; it's not truly distributed. For two days I've been trying to figure out a way to bootstrap a distributed network without having to access bootstrap nodes. I came to the conclusion that if nodes on a network broadcasted themselves over the network then eventually nodes will find each other. You don't find the network, the network finds you!
Each node starting a search from the bottom of an address space would be redundant, so I thought that nodes could randomly choose addresses, each node not using the same address twice, though multiple nodes could inadvertently choose nodes others have already chosen (since they aren't synchronized, keeping track of what other nodes have chosen).
So of course I needed to know the equations of probability that govern this system. I know this may constitute multiple equations and thus demand separate questions, but I assure you they are all connected. So, here we go.
p = probability
a = size of address space
g = number of guesses
n = number of nodes
Here are the questions...
- For a single node in the address space, what is the probability of finding a novel address, not choosing itself or the same way twice? For this I have;
p = 1/(a-g-1)
- For n nodes on the network, what is the probability of nodes finding a novel address, each node not choosing itself or the same address twice, though separate nodes may inadvertently choose the same nodes? For this I have;
p = n/(a-g-1)
For n nodes on a network, what is the probability of separate nodes picking an address that another node has already picked (a random collision), each node not picking itself or the same address twice, where separate nodes may pick the same address twice (a random collision)? I do not have an equation for this.
Finally, for n nodes in the address space, what is the probability of nodes finding each other in the address space, not choosing themselves or the same address twice, though nodes can inadvertently choose addresses that other nodes have chosen (they do not communicate with each other to organize their search; they are unsynchronized, or truly random). I do not have an equation for this.
Feel free to help me edit this question for clarity, structure, and simplicity!