There are $M$ interconnected nodes in a peer-to-peer network. Initially, each node numbers itself with any integer from $1$ to $N$, $N \leq M$.
Each node counts the most occurrences of neighboring nodes, including itself, and modifies its number to that value. If all the numbers occur equally, a non-self number is randomly selected and changed to that number. Each node notifies its neighbors when initialization is complete or when the numbering is updated.
My question is this:
- Can this rule achieve final agreement on the numbering of all nodes?
- If so, what is the expected time to reach agreement?