2
$\begingroup$

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.

$\endgroup$

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.