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 \( \left( i, j \right) \) 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{ln\ N}{N} \), because it is the boundary between the supercritical and the connected regime.
3. \( p = \frac{ln\ N}{ln\ \langle k \rangle} \), because it is the boundary between the supercritical and the connected regime.
4. \( p = \frac{\langle k \rangle}{N} \), because it is the critical point.
5. None of the above

Original idea by: Christian Konishi