[Solved]: Counting the nodes in a network in a distributed way

For constant node degrees, the following simple algorithm seems to work: The source node $s$ can initiate a BFS tree construction and then we simply accumulate the count upwards along the tree edges starting from the leafs and ending at $s$. Each node locally keeps track of its parent/children in the tree; note that we can do this using $O(log n)$ space as the degree is constant and therefore each node knows if it is a leaf. For arbitrary degree, there’s also a slightly more complicated randomized distributed algorithm that gives a constant factor approximation of the number of nodes in a synchronous network where computation proceeds in synchronous rounds. (In each round, every node can reliably exchange $O(log n)$ bits with each of its neighbors.) Suppose that I have a network $G$ with diameter $Diam(G)$.

1. Each node $u$ generates a random value $x_u$ according to the exponential distribution with rate 1; we round $x_u$ to $Theta(log n)$ bits.
2. Node $u$ also has a local variable $minval_u$ where it keeps track of the minimum value encountered so far. Initially, $minval_u = x_u$.
3. For the next $Diam(G)$ many rounds, node $u$ sends $minval_u$ to its neighbors. Also, upon receiving $minval_v$ from some neighbor $v$, node $u$ sets $minval_u = min(minval_u,minval_v)$.
4. After round $Diam(G)$, node $u$ computes its estimate of the number of nodes as $1/minval_u$.

Why does this algorithm work? Our algorithm exploits the following nice property of the exponential distribution (see here): If we have $n$ exponential random variables $X_1,dots,X_n$ each of rate $1$, then the random variable $X = min(X_1,dots,X_n)$ is also exponentially distributed of rate $n$ and therefore has expected value $1/n$. At the end of the algorithm, the $minval_u$ variable corresponds to a sample of this random variable $X$. Therefore, to get the sought value $n$ (i.e. the number of nodes), we simply compute $1/minval_u$. To get a high probability bound, we can repeat the above $Theta(log n)$ many times and take the average of the produced estimates.