Counting the nodes in a network in a distributed way

Question

There is a network with $n$ nodes. Each node can contact only the neighbouring nodes (the degree of each node is bounded, if that matters).

One of the nodes, say $s$, wants to know $n$. How can it do this?

Each node has $O(\log n)$ memory bits, so it can hold a counter, but not a list of all nodes.

If the network is a tree, I think the following (inefficient) protocol should work:

1. $s$ sends a "Count" message to itself.

2. When a node $v$ receives a "Count" message from node $u$, it acts in the following way:

   • Send every neighbour except $u$ a "Count" message and wait for the result.
   • Send $u$ a "Result" message containing the sum of all results (0 if there are no neighbours).

The problem with general graphs is that we may not remember which nodes we already counted, so we might count the same node twice. What to do?

Answer 1

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.