<p>I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows:</p>

<ol>
<li>Messages are sent unreliably with an at-most-once sending</li>
<li>Nodes are only eligible if they are available and have the most current timestamp of all available nodes within the set. Each node has a timestamp, representing the last update operation.</li>
<li>Each node has a weight, each weight is unique (= the nodes are strictly ordered in terms of the weight).</li>
<li>The eligible node with the highest weight should win the election.</li>
<li>My system uses timeouts to detect failures.</li>
<li>Each node knows the weight of each other node in the set.</li>
</ol>

<p>I had a look especially at Bully algorithms, originally <a href="http://python.6.x6.nabble.com/attachment/2790883/0/Elections%20in%20a%20Distributed%20Computing%20System.pdf" rel="nofollow">given by Garcia-Molina</a> and a <a href="http://umdrive.memphis.edu/smmasum/www/Research%20Papers/Proceedings/Modified%20Bully%20Algorithm%20for%20Electing%20Coordinator%20in%20Distributed%20Systems.pdf" rel="nofollow">modified version</a>. I have no problem adapting them to the unreliable message sending using ACKs. However, I struggle as I have one assumption which is quite different: I do have timestamps at each node, which are not known to every node. </p>

CC BY-SA 3.0
2014-05-08T01:57:55.853Z
Could you elaborate on Assumption 2? What does it mean for a node to have the most current timestamp?
Peter
CC BY-SA 3.0
2014-05-08T07:31:59.923Z
@Peter I just updated my question. Basically, the system should be used to replicate data (the leader election is to elect the Primary, i.e. the node where all updates are applied) and the timestamps represent when the last update operation occurred.
dirkk
CC BY-SA 3.0
2014-05-12T16:15:23.887Z
A clarification (I'm not an expert): why can't you do a two phase election: the first phase is used to elect the coordinator (standard election); in the second (coordinated) phase the nodes send their timestamps to the coordinator and the coordinator forces a new coordinator if it has a higher timestamp. Furthermore: suppose that there is only one node with the most current timestamp and it fails. What should happen?
Marzio De Biasi
CC BY-SA 3.0
2014-05-12T17:29:37.637Z
@MarzioDeBiasi First, because this would be quite complicated in terms of the protocol (after the first phase it couldn't be a real coordinator, because then updates could be applied to the node and change timestamps), but this would me manageable. But it is very inefficient, even in the average case the algorithm would be executed n/2 times.
dirkk
CC BY-SA 3.0
2014-05-12T17:30:49.143Z
Another problem would be, I suppose, what you mentioned: What if there is a node with a more current timestamp and it fails after telling everyone it has the most current timestamp and should be the leader.
dirkk
CC BY-SA 3.0
2014-05-12T17:32:29.863Z
What should happen: The most current timestamp is determined by the _available_ nodes within the set, i.e. a failing node is not considered in an election (it can't be eligible). I clarified that in the question.
dirkk
<ds.algorithms><dc.distributed-comp>
Election algorithm with unreliable messages and a certain timestamp
dirkk
# Election algorithm with unreliable messages and a certain timestamp

(Asked by: username_0 on 2014-05-07)

I am struggling to get a correct algorithm for a leader election algorithm in a distributed system. My assumptions are as follows:

1. Messages are sent unreliably with an at-most-once sending
2. Nodes are only eligible if they are available and have the most current timestamp of all available nodes within the set. Each node has a timestamp, representing the last update operation.
3. Each node has a weight, each weight is unique (= the nodes are strictly ordered in terms of the weight).
4. The eligible node with the highest weight should win the election.
5. My system uses timeouts to detect failures.
6. Each node knows the weight of each other node in the set.

I had a look especially at Bully algorithms, originally [given by Garcia-Molina](http://python.6.x6.nabble.com/attachment/2790883/0/Elections%20in%20a%20Distributed%20Computing%20System.pdf) and a [modified version](http://umdrive.memphis.edu/smmasum/www/Research%20Papers/Proceedings/Modified%20Bully%20Algorithm%20for%20Electing%20Coordinator%20in%20Distributed%20Systems.pdf). I have no problem adapting them to the unreliable message sending using ACKs. However, I struggle as I have one assumption which is quite different: I do have timestamps at each node, which are not known to every node.

**Tags:** ds.algorithms, dc.distributed-comp
> **Comments:**
> **username_1**: Could you elaborate on Assumption 2? What does it mean for a node to have the most current timestamp?  
> **username_0**: @Peter I just updated my question. Basically, the system should be used to replicate data (the leader election is to elect the Primary, i.e. the node where all updates are applied) and the timestamps represent when the last update operation occurred.  
> **username_2**: A clarification (I'm not an expert): why can't you do a two phase election: the first phase is used to elect the coordinator (standard election); in the second (coordinated) phase the nodes send their timestamps to the coordinator and the coordinator forces a new coordinator if it has a higher timestamp. Furthermore: suppose that there is only one node with the most current timestamp and it fails. What should happen?  
> **username_0**: @MarzioDeBiasi First, because this would be quite complicated in terms of the protocol (after the first phase it couldn't be a real coordinator, because then updates could be applied to the node and change timestamps), but this would me manageable. But it is very inefficient, even in the average case the algorithm would be executed n/2 times.  
> **username_0**: Another problem would be, I suppose, what you mentioned: What if there is a node with a more current timestamp and it fails after telling everyone it has the most current timestamp and should be the leader.  
> **username_0**: What should happen: The most current timestamp is determined by the _available_ nodes within the set, i.e. a failing node is not considered in an election (it can't be eligible). I clarified that in the question.  

---

## 0 answers

