1
$\begingroup$

Short backstory...

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.

Variables...

p = probability

a = size of address space

g = number of guesses

n = number of nodes

Here are the questions...

  1. 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)

  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)

  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.

  2. 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!

$\endgroup$
0
$\begingroup$

I do not completely understand some of your questions, but this is how I would interpret them:

  • For 1, I would have thought the probability that a particular node picks some address which is novel to it is $1$ as it knows not to look at addresses it already knows about. Meanwhile $\frac1{a-g-1}$ is the probability it picks a particular one of these addresses

  • For 2, I would again have thought the probability that $n$ nodes each picks some address which is novel to it is $1$, ignoring whether this address is another node or or an address which has already been picked by a different node

If so far after $g$ rounds of each taking a guess they have all picked addresses without a collision of any type (a node picks another node, a node picks an address already picked by another node, or two nodes pick the same address in the same round), the probability they all do so again is $\frac{a-ng-n}{a-g-1} \times \frac{a-ng-n-1}{a-g-1}\times \cdots \times \frac{a-ng-2n+1}{a-g-1} = \frac{(a-ng-n)!}{(a-g-1)^n(a-ng-2n)!}$, and so the probability of no collisions in the first $g$ rounds is $ \frac{\left((a-g-1)!\right)^n (a-n)!}{\left((a-1)!\right)^n(a-ng-n)!} $

  • For 3, I would therefore have thought the probability that there is at least one collision of some type in the $g+1$th round given no previous collisions in the previous $g$ rounds is $1-\frac{(a-ng-n)!}{(a-g-1)^n(a-ng-2n)!}$

  • For 4, I would therefore have thought the probability that there is at least one collision of some type by the $g$th round is $1- \frac{\left((a-g-1)!\right)^n (a-n)!}{\left((a-1)!\right)^n(a-ng-n)!} $

But that only deals with the first collision of some sort. If you want all the nodes to be able to discover each other in some way including through third nodes they have both had collisions with, then the calculation will be more complicated

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.