I have to write a leader election algorithm in an unoriented mesh (a grid a*b), with many initiators.

Someone give me an indication to wake up each node and then make an election in the exterior ring between the 4 corners. But I don't found anything on the web :/ For the wake-up process I think I can use a wake flood algorithm, but for the leader election, I'm out... Thank's.

  • $\begingroup$ What are you trying to achieve with the algorithm, and why is this research level? As it stands the question sounds like a standard textbook exercise. $\endgroup$ – András Salamon Jan 15 '15 at 13:30

One simple way would be something like this:

For each processor:
1. myID = Some unique ID
2. myLeader = myID
3. Loop forever:  
   3.1 For each neighbour:  
      3.1.1 Read (id_i, leader_i)  
      3.1.2 If leader_i > myLeader   myLeader = leader_i
   3.2 Write to all neighbours: (myID, myLeader) 

The idea is that you use some property (Say IP address, MAC address, anything that is serialised by the manufacturer), and chose the maximum number as the leader.

Of course you can bound the number of iterations by a + b + 1 (if you have a synchronized way to make each one work on it's turn) since this is the maximum "jumps" an ID has to make is from one corner to the corner on the other side of the board.

This algorithm is also self-stabilizing which is a good property to have. There are also versions of this algorithm where there is not unique identifier, there you let each processor chose a number at random, and then do the same, while making sure no two processors have selected the same random number (and if so, have some tie breaking).
* Self-stabilization is good if you consider a senario where nodes maybe turned off at any time, and get turned back on after any amount of down time.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.