4
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Welcome to Puzzling SE! Hope you stay! $\endgroup$
    – NL628
    Apr 7, 2018 at 7:05
  • $\begingroup$ Sounds like an interesting problem, but I wonder about each node being programmed identically or at least not having a unique idenfier tag - could we allow each node to have a different identifier number and yet be programmed in the same way - I see you discount it in the problem. Without some uniqueness I worry about how a node can effectively receive a message back from itself without being confused by 'noise' from other nodes.---- If this makes the problem too easy then maybe each node can have a non-sequential identifier like 3, 129, 75, etc $\endgroup$
    – tom
    Apr 7, 2018 at 9:12
  • $\begingroup$ . -- or maybe the solution is to have some way of building sequential unique identifiers. $\endgroup$
    – tom
    Apr 7, 2018 at 9:16
  • 1
    $\begingroup$ Thanks for the welcome! I chose puzzling over math (or CS) due to the whimsical nature of the constraints. In any pragmatically-designed system, it'd be silly for the engineers not to build in capacity for unique ID and Goedel-numbering (as already-mentioned below), but I'm hoping for something like a reaction-diffusion mechanism that would allow (say) unusually clever bacteria to know the size of their colony asymptotically exactly. $\endgroup$
    – Zomulgustar
    Apr 7, 2018 at 13:25
  • 1
    $\begingroup$ 1A sounds a lot like how biological neural networks work. As a whole, (assuming sufficient connectivity and node count) such a network can of course gain almost any knowledge by achieving sentience; I'm not certain it's the number one most efficient approach though :-) $\endgroup$
    – Bass
    Apr 8, 2018 at 21:19

2 Answers 2

Reset to default
7
$\begingroup$

The following applies to questions 1ABC:

I do not think it is possible. Consider cycle graphs, i.e. nodes connected in a long loop, so each node has two neighbours. Suppose you have two such graphs, of different sizes. At each stage, the nodes in both graphs will all send the same number, and then receive the same number(s), because they are locally all exactly the same. They all have the same inputs, so will produce the same outputs, and at no point will the node be able to determine in which cycle graph it lies.

Remark that may help for questions 2ABC:

Being able to send only one number is not a restriction. By using Gödel encoding you can essentially send any list of numbers, and so encode any amount of information in the message you want.

I'm not so sure about the setup however. Can each node distinguish between neighbours only once they have received different replies? For example in a cycle graph, can the nodes send different messages to their neighbours in the very first step, and if so, which message goes in which direction? If they can only send different messages in response to having received different messages, then the argument in #1 applies here too, and it is not possible.

Improve this answer
$\endgroup$
7
  • $\begingroup$ I would wonder about binary encoding, which seems less complicated than the (interesting) Goedel encoding $\endgroup$
    – tom
    Apr 7, 2018 at 9:08
  • $\begingroup$ @tom Sure, binary encoding (e.g. ASCII or BCD) works fine here too. You just need a fixed alphabet so that you know how many bits each letter takes up, or more generally you can use a base $n$ encoding for an alphabet of $n$ symbols. To send more than one word, you need to include a separator symbol (a 'space') in the alphabet too. Gödel encoding's alphabet is infinitely large - any number is encoded as one symbol, without the need for a separator. I think Gödel also needed certain arithmetic properties for his encoding which we don't here. $\endgroup$
    – Jaap Scherphuis
    Apr 7, 2018 at 9:42
  • $\begingroup$ Suppose, after the initial 'ping', that every node hears the 'direction' that different otherwise-identical transmissions come from well enough $\endgroup$
    – Zomulgustar
    Apr 7, 2018 at 13:30
  • $\begingroup$ So apparently comments can only be edited for 5 minutes :p Suppose, after the initial 'ping', that every node hears the 'direction' that different otherwise-identical transmissions come from relative to some 'true north' exactly well enough to receive and transmit ordered tuples rather than multisets. (So they recognize a 'first neighbor', 'second neighbor', etc. but can't 'transmit the angle between the previous two neighbors'. $\endgroup$
    – Zomulgustar
    Apr 7, 2018 at 13:36
  • $\begingroup$ You're quite right about Goedel numbers of course..I was just hoping to avoid their ilk. .I'm not entirely convinced that the broadcasting problems are impossible in principle, but your argument clearly demonstrates the necessity of such 'tricks'. No time to flesh out the idea now (or see if it falls to your argument, just tossing it out before i forget ) but an aperiodic sequence passed + summed might make different patterns going around cycles of different lengths... $\endgroup$
    – Zomulgustar
    Apr 7, 2018 at 13:42
3
$\begingroup$

Some additional thoughts:

Even for the case 2ABC, any approaches based on symmetry breaking are doomed to fail for complete graphs (and similar symmetric graphs), since the reduction of neighbor differentiation to ordered lists allows for the situation that the structure of each node is exactly the same and thus necessarily also their behavior.

For example take the cycle graph mentioned in the other answer: If all nodes are drawn in a circle and each nodes first neighbor is the clockwise one, they are completely indistinguishable and no symmetry breaking approach can result in differing behavior.

On the other hand, case 1C is equivalent to case 2ABC, using a suitable encoding of the messages: Assume that nodes first ping each other to find out their number and order of neighbors. In the second round, each node sends message “i“ to the ith neighbor. In any subsequent round, it can prefix its message to a certain neighbor by that neighbor's number and concatenate them (including a unique separator). This new message is then broadcasted to all neighbors. Thus any node can find out which part of an incoming message is meant for it, even though all neighbors received the same message.

Example: Node A has three neighbors B, C, D, in that order. In the second round (first round is pings), it sends 1 to B, 2 to C and 3 to D. From then on, if it wants to send X to B, Y to C and Z to D, it sends (in a binary encoding) “1:X;2:Y;3:Z“ to all neighbors. Due to the second round, B knows to process part 1 (“X“), C part 2 and so on.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.