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)$.
- 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.
- 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$.
- 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)$.
- 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.