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 \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