I'm stuck with some problem where I have to design a leader election algorithm for an oriented hypercube. This should be done by using a tournament with a number of rounds equal to the dimension D of the hypercube. In each stage d, with 1 <= d < D two candidate leaders of neighbouring d-dimensional hypercubes should compete to become the single candidate leader of the (d+1)-dimensional hypercube that is the union of their respective hypercubes.
It has been a long time since I studied distributed systems, but I hope this helps a little :)
The problem: Leader election in a network with a hypercube tolopogy. In this topology, every node has exactly D neighbors (where D is the hypercube's dimension). Since the hypercube is oriented, the nodes know which of their links corresponds to every dimension. Also, I assume that all nodes are labeled with some unique id, as typical with this kind of problems.
If I understand well your solution guidelines, the algorithm seems to be simple: a node has exactly D states. In every state 1<=d<=D it communicates with its neighbor along the d axis. This communication consists of sending it the id of the best candidate it is aware of (when d=1 this is simply its own id), and comparing it with the id received by the peer. Now the node knows the best id of the sub-cube of order d (defined by axes 1,2...,d) it belongs to. This way, at step D all nodes are aware of the global best, and the algorithm completes with a consensus.
For example, assume 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 by each node so far.
The first iteration (d=1) works along the horizontal axis, and terminates as follows:
(2) (2)
1-----2
| |
| |
4-----3
(4) (4)
The second (and last) iteration (d=2) works along the vertical axis, and terminates as follows:
(4) (4)
1-----2
| |
| |
4-----3
(4) (4)
The node number 4 has been chosen, as required (highest id).
Message count complexity
For every edge in the hypercube we have exactly 2 messages (one on 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 M=D*2^D messages. In order to compute the complexity as a function of N (the number of nodes), recall that N = 2^D, so M=N*log N.