# Can this algorithm achieve eventual consistency?

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?
• So in each round, a node $x$ updates its value to $\text{argmax} \{ v(y) \mid y \in N[x] \}$ where $N[x]$ is the set of $x$'s neighbors including itself? Commented Dec 15, 2021 at 13:17
• Is this coming from a homework assignment or take-home exam? Commented Dec 15, 2021 at 13:20
• @PålGD Simply put, a node always makes its number consistent with the number of most of the surrounding nodes (including itself) Commented Dec 15, 2021 at 13:28
• This algorithm may not terminate: take a cycle with an even number of nodes Commented Dec 15, 2021 at 14:11
• @nirshahar Notice " If all the numbers occur equally, a non-self number is randomly selected and changed to that number." This causes the numbering to be unevenly distributed Commented Dec 15, 2021 at 14:14