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?
Improve this question
$\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
    Dec 15, 2021 at 13:17
  • $\begingroup$ Is this coming from a homework assignment or take-home exam? $\endgroup$
    – Vectorizer
    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$
    – leslie-wung
    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
    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$
    – leslie-wung
    Dec 15, 2021 at 14:14

0

Reset to default

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.

Browse other questions tagged or ask your own question.