2023-205

Suppose that we are trying to project a distributed system with random architecture. Every time a new computer $i$ tries to ingress, for each existing machine $j$ in the network, a connection $(i,j)$ may be created with probability $p$.

For this architecture, it is desired that any computer must be reachable from any node, however a few exceptions are tolerable. Also,$p$ cannot be too big for cost reasons.

Which one of these options presents a reasonable choice for the value of$p$? Assume that$N$ is the number of expected computers in the network, and it is large enough to apply the law of large numbers.

1. $p=\frac{1}{N}$, because it is the critical point.
2. $p=\frac{\ln N}{N}$, because it is the boundary between the supercritical and the connected regime.
3. $p=\frac{\ln N}{\ln ⟨k⟩}$, because it is the boundary between the supercritical and the connected regime.
4. $p=\frac{⟨k⟩}{N}$, because it is the critical point.
5. None of the above

Original idea by: Christian Konishi