Electing a leader in a ring with link failures (Q1075046)

We investigate the message complexity of electing a leader in a ring of asynchronous processors. Our work deviates from the previous works on electing a leader in that we consider the effect of link failures. A link is said to fail if some message sent through it never reaches its destination. We distinguish the case where n is known from the case n unknown. Our main result is an O(n log n) algorithm for electing a leader on an n-processor ring (the case n is known).