Assignment 4: Leader Election

1. What are the basic requirements for a solution to the leader election problem? why are they required?

2. How will you change the Lelann-Chang-Robert algorithm for the following modified/stronger model: Synchronous, reliable, unidirectional ring, unique ids. Write your modified the Algorithm and explain the advantages over the basic version.

3. Use an example to demonstrate the functionality of the TTL (time-to-live) field in Hirschberg-Sinclair Algorithm?

4. How can you modify the FloodMax algorithm for leader election, when the diameter of the network is not known but the number of nodes are known, so that it will still be able to elect the leader? What will be its complexity in that case?

5. Understand the new models: uniform and non-uniform, anonymous and non-anonymous.

6. Understand the functionality of the TTL (time-to-live) field in Hirschberg-Sinclair Algorithm.

7. Explain the message complexity of FloodMax algorithm for leader election in an arbitrary network.

8. Any comparison-based leader election algorithm in a ring requires Ώ(nlgn) messages – why?

9. Explain why synchronous, non-uniform leader election protocol for anonymous rings is not possible.

10. Explain using an example the workings of the LeLann's and Chang-Robert's Algorithm.

11. Can the LeLann's and Chang-Robert's Algorithm work on bidirectional rings?

12. Why replies are always forwarded in the Hirschberg-Sinclair algorithm?

13. Explain how many the number of rounds can be in Hirschberg-Sinclair algorithm?

14. Explain the message complexity of Hirschberg-Sinclair algorithm.

15. What can be done if you do not have a ring topology, i.e., the network is arbitrary.