0
$\begingroup$

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?
$\endgroup$
7
  • $\begingroup$ 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? $\endgroup$
    – Pål GD
    Commented Dec 15, 2021 at 13:17
  • $\begingroup$ Is this coming from a homework assignment or take-home exam? $\endgroup$
    – Vectorizer
    Commented Dec 15, 2021 at 13:20
  • $\begingroup$ @PålGD Simply put, a node always makes its number consistent with the number of most of the surrounding nodes (including itself) $\endgroup$ Commented Dec 15, 2021 at 13:28
  • 1
    $\begingroup$ This algorithm may not terminate: take a cycle with an even number of nodes $\endgroup$
    – nir shahar
    Commented Dec 15, 2021 at 14:11
  • $\begingroup$ @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 $\endgroup$ Commented Dec 15, 2021 at 14:14

0

Your Answer

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

Browse other questions tagged or ask your own question.