As a part of my Distributed Systems course I am required to provide an algorithm that is able to elect a leader in a synchronous bidirectional ring, where every message that is sent may be lost (lets say with a probability p). Furthermore, every node/process only knows its own ID, not the ring size nor its neighbors.

I have found that is problem is unsolvable in asynchronous rings:

Theorem A. There is no distributed algorithm for electing a leader in a ring, when the only local input in processor P~ is its identity (IDi).

Electing a leader in a ring with link failures, Goldreich, O. & Shrira, L. Acta Informatica (1987) 24: 79. https://doi.org/10.1007/BF00290707

Is it possible in synchronous rings? If not, may he want a Randomized algorithm as solution?

I was thinking to implement a modification of HS algorithm where every message needs an ACK reply, and it's being resent until an ACK arrives. But I think that this would result in some processes to proceed to the next phase whereas other processes are still waiting for an ACK reply.


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.