Exercises election leader in synchronize ring structure
(Chapter 3 Lynch, Nancy A. (1996-04-16). Distributed Algorithms (The Morgan Kaufmann Series in Data Management Systems) (Kindle Locations 1327-1335). Elsevier Science. Kindle Edition.)
Master student: do (3 to 6) of the following exercise
Research Student: do all of the following exercise
3.2. For the LCR algorithm, (a) Give a UID assignment for which Ω( n2) messages are sent. (b) Give a UID assignment for which only O (n) messages are sent. (c) Show that the average number of messages sent is O (n log n), where this average is taken over all the possible orderings of the processes on the ring, each assumed to be equally likely.
3.3. Modify the LCR algorithm so that it also allows all the non-leader processes to output non-leader, and so that all the processes eventually halt. Present the modified algorithm using the same style of “code” that we used for the LCR algorithm.
3.6. Show that the HS algorithm still works correctly in the version of the synchronous model allowing variable start times (you might have to modify the code slightly).
3.7. Suppose that the HS leader-election algorithm is modified so that successive powers of k are used for path lengths, k>2, instead of successive powers of 2. Analyze the time and communication complexity of the modified algorithm, similarly to the way the original HS algorithm is analyzed in the book. Compare the results to those for the original algorithm.
3.8. Consider modifying the HS algorithm so that the processes only send tokens in one direction rather than both.
(a) Show that the most straightforward modification to the algorithm in the text does not yield O (n log n) communication complexity. What is an upper bound for the communication complexity?
(b) Add a little more cleverness to the algorithm in order to restore the O (n log n) complexity bound.
3.9. Design a unidirectional leader-election algorithm that works with unknown ring size, and only uses O (n log n) messages in the worst case. Your algorithm should manipulate the UIDs using comparisons only.