Leader Election Algorithm - Comparison functions are not allowed

Question

Suppose a network graph as a synchronous directed ring and some nodes over this network. I am trying to construct an algorithm that solves the Leader Election problem, but this without using any comparison except the equals(==) and non-equals(!=) functions.

After a bunch of thoughts crossing my mind i wonder if there is no solution at all.

So is there any possible way of designing an algorithm with the above principles, or if not how could i prove that this is not possible?

Thank you all in advance

Answer 1

methinks you could use symmetric-ness arguments.

if nodes A and B are contending for leadership, both A and B will come up with the same answers for (A == B), and for (A != B).

Answer 2

I think it is possible. My idea (assuming that size of the network n is known to all nodes):

Leader(i, n):
    p := 1/n
    id[i] := Random identifier of node i
    p[i] := Choose 1 with probability p, 0 otherwise.
    If p[i]==1, send message (id[i]) to the next node.

    // p[i]==1 means i-th node pretends to be the leader

    For next n rounds:
        If received message (X), X!=id[i]:
            p[i] := 0
            Send message (X) to the next node.

    // now after n rounds at most 1 node pretends to be the leader
    // Chosen[i] will represent whether i-th node knows if there is a leader.

    Chosen[i] := p[i];

    If p[i]==1, send message (id[i]) to the next node.

    For next n rounds:
        If received message (X):
            Chosen[i] := 1
            Send message (X) to the next node.

    // now every node knows whether the election went successfully

    If Chosen[i]==0, then repeat from scratch.

And if you don't know the size of network:

Size(i):
    Send message (id[i], 1) to the next node.
    For each following round:
        If received message (X, Y), X!=id[i]:
            Send message (X, Y+1) to the next node.
        If received message (X, Y), X==id[i]:
            Size of the ring is Y.
            Stop.

Size() takes n rounds and n² messages, Leader() takes 2n*e rounds on average for large n (if I recall this part of math correctly).