<p>One simple way would be something like this:</p>

<pre><code>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 &gt; myLeader  
         3.1.2.1 myLeader = leader_i
   3.2 Write to all neighbours: (myID, myLeader) 
</code></pre>

<p>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.</p>

<p>Of course you can bound the number of iterations by <code>a + b + 1</code> (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.</p>

<p>This algorithm is also <a href="https://en.wikipedia.org/wiki/Self-stabilization" rel="nofollow">self-stabilizing</a> 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).<br>
* 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.</p>

CC BY-SA 3.0
2015-01-15T10:23:30.310Z
2015-01-15T10:23:30.310Z
Ramzi Kahil
<p>I have to write a leader election algorithm in an unoriented mesh (a grid a*b), with many initiators.</p>

<p>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.</p>

CC BY-SA 3.0
2015-01-15T13:30:41.277Z
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.
András Salamon
<graph-algorithms>
Leader election algorithm in a grid
Army
# Leader election algorithm in a grid

(Asked by: username_0 on 2015-01-14)

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.

**Tags:** graph-algorithms

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2015-01-15. Score: 0

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  
         3.1.2.1 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.


---

