March 31th question

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 a probability of $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, because of 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{lnN}{N}$, because it is the boundary between the supercritical and the connected regime.
3. $p=\frac{lnN}{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