Is there a non-deterministic leader election algorithm?

I was wondering whether a non-deterministic leader election algorithm exists (in a one directional ring) that ensures termination. I cannot think of one nor can I find one that is non-deterministic. Some that I've found are:

• Select the node with the highest process ID to be the leader (deterministic) and terminates.

• Randomly decide whether a node wants to be a leader, if in the ring there is another node that wants to be a leade, restart the whole process. This one does not terminate, but has a probability of termination.

Can someone either give me some hints on how to create a distributed non-deteministic leade election algorithm? And maybe explain it in layman terms.

Thanks for everything!

There exists no probabilistic (anonymous) leader election algorithm with both, a guaranteed termination and a guaranteed correctness (only one leader). If I remember right, you will find a proof in N. Lynch's book on Distributed Systems.

However, there exists algorithms with a probability limit of zero for non-termination for a sufficient long runtime of the algorithm. In addition, the expected runtime is rather short (AFIR, in the order of ln(k) for k initiators).

The main idea for such an algorithm follows your second approach. However, do not simple restart the process in case of several leaders, but only allow the winners of the last round to become candidates in the next round.

EDIT 1-3:

If you asking for a non-anonymous leader election, there are several probabilistic algorithms that guarantees termination. E.g., take a normal ring algorithm and delay messages with with a certain probability, as smaller the ID as greater the chance for delay. In this way, messages with low chance of winning are erased earlier, resulting in less overall messages.

If you want to have a different outcome for non-anonymous members, you can e.g. use a two phase algorithm:

1. Perform a classical leader election => a nodes A with the highest ID wins
2. Let A roll a dice to determine the actual leader.

The element of fortuity could also be distributed:

1. Any nodes knows the set of identities (S) (if not, use a flooding algorithm to tell)
2. All nodes select by chance an ID of ouf S and send it to any other node
3. The ID that is named most often, wins. If there is more than one such ID, select one of them in a deterministic way, e.g., the median.

Termination and a non-deterministic outcome are granted for both alogrithm. However, the first has a lower average message complexity (n log n vs. n² ; the worst case complexity is the same) and is more fair (i.e., the probability that a ID wins is equaly distributed, what is not true for the second algorithm). I'm pretty sure, that at least the last disadvantage can eliminated by a more sophisticated algorithm, but the question here was for the general existence of such an algorithm.