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 and a modified version. 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.

  • $\begingroup$ Could you elaborate on Assumption 2? What does it mean for a node to have the most current timestamp? $\endgroup$ – Peter May 8 '14 at 1:57
  • $\begingroup$ @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. $\endgroup$ – dirkk May 8 '14 at 7:31
  • $\begingroup$ 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? $\endgroup$ – Marzio De Biasi May 12 '14 at 16:15
  • $\begingroup$ @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. $\endgroup$ – dirkk May 12 '14 at 17:29
  • $\begingroup$ 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. $\endgroup$ – dirkk May 12 '14 at 17:30

Your Answer

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

Browse other questions tagged or ask your own question.