Leader selection algorithm for oriented hypercube
I am stuck with some problem where I need to develop a leader selection algorithm for an oriented hypercube. This must be done using a tournament with the number of rounds equal to the size D of the hypercube. At each stage d with 1 <= d <D, two candidate candidates of neighboring d-dimensional hypercubes must compete to become the only candidate leader of the (d + 1) -dimensional hypercube, which is the union of their respective hypercubes.
a source to share
It's been a long time since I learned about distributed systems, but I hope this helps a little :)
Problem: Online leadership elections with hypercube tolopogy. In this topology, each node has exactly D neighbors (where D is the size of the hypercube). Since the hypercube is oriented, the nodes know which of their links corresponds to each size. Also, I am assuming that all nodes are tagged with some sort of unique identifier, typical of such problems.
If I understand your solution recommendations well, the algorithm seems simple: a node has exactly D states. In each state 1 <= d <= D, it binds to its neighbor along the d axis. This message consists of sending him the ID of the best candidate he knows (when d = 1 is just his own ID) and comparing it to the ID received by the peer. The node now knows the best id of the subcube of order d (defined by the 1,2 ..., d axes) to which it belongs. Thus, in stage D, all nodes are aware of the global best, and the algorithm ends with consensus.
For example, suppose the following topology (D = 2) and id values:
(1) (2)
1-----2
| |
| |
4-----3
(4) (3)
The IDs in parentheses indicate the best IDs known to each node.
The first iteration (d = 1) works along the horizontal axis and ends like this:
(2) (2)
1-----2
| |
| |
4-----3
(4) (4)
The second (and final) iteration (d = 2) runs along the vertical axis and ends like this:
(4) (4)
1-----2
| |
| |
4-----3
(4) (4)
If necessary, node number 4 (highest id) is selected.
Complexity of messages
For each edge in the hypercube, we have exactly 2 messages (one in each direction). Since the formula for the number of edges in a hypercube of dimension D is E = D * 2 ^ (D-1), we have exactly messages M = D * 2 ^ D. To compute complexity as a function of N (number of nodes), recall that N = 2 ^ D, so M = N * log N.
a source to share