I don't actually have a solution in mind for these, but it seemed puzzly enough to bring to the table. Seems as though someone must have come up with this before, but if so, I couldn't find it when I looked (or perhaps recognize it when I found it ^_^). Despite my language in framing the problem, I'm hoping for physics/biology-inspired solutions, so simpler methods and low 'memory' use are preferred over low-cycle-count-at-any-cost.
A finite network has an unknown number of identically programmed deterministic nodes (so no unique id to lead a D/BFS, and RNG can't break symmetry). Each cycle, a node can transmit a single number, received only by its immediate neighbors. How efficiently (if at all) can every node be informed of the total number of nodes in the network? Presumably all nodes initially broadcast '1', and therefore learn how many neighbors each has...?
1A. The same number is broadcast to all neighbors, and a node only receives the sum of all signals from its neighbors.
1B. Still broadcasting, but now each node knows the multiset of numbers transmitted by its neighbors, but not which sent which.
1C. Still broadcasting, but now each node can distinguish which neighbor sent which signal.
2ABC. As above, but now nodes can send different signals to different neighbors.