Purchase Solution

Election Algorithm

Not what you're looking for?

Ask Custom Question

Derive an election algorithm for bidirectional rings that is more efficient than the ring algorithm:

The ring algorithm assumes that the links are unidirectional and that each process sends its message to the neighbor on the right. The main data structure used by the algorithm is the active list, a list that contains the priority numbers of all active processes in the system when the algorithm ends; each process maintains its own active list. The algorithm works as follows:

1. If process Pi detects a coordinator failure, it creates a new active list that is initially empty. It then sends a message "elect(i)" to its right neighbor and adds the number i to its active list.

2. If Pi receives a message "elect(i)" from the process on the left, it must respond in one of three ways:
a) If this is the first 'elect' message it has seen or sent, Pi creates a new active list with the numbers i and j. It then sends the message 'elect(i)', followed by the message 'elect(i)'.
b) If i does not equal j - that is, the message received does not contain Pi's number - then Pi adds j to its active list and forwards the message to its right neighbor.
c) If i = j - that is, Pi receives the message 'elect(i)' - then the active list for Pi now contains the numbers of all the active processes in the system. Process Pi can now determine the largest number in the active list to identify the new coordinator process.

How many messages are needed for n processes?
(There is no need to program the algorithm, but explain the algorithm idea with words.)

Additional info on Election algorithm:
Many distributed algorithms employ a coordinator process that performs functions needed by the other processes in the system. These functions include enforcing mutual exclusion, maintaining a global wait-for graph for deadlock detection, replacing a lost token, and controlling an input or output device in the system. If the coordinator process fails due to the failure of the site at which it resides, the system can continue execution only by restarting a new copy of the coordinator on some other site. The algorithms that determine where a new copy of the coordinator should be restarted are called election algorithms.
Election algorithms assume that a unique priority number is associated with each active process in the system, For ease of notation, we assume the priority of process Pi is i. To simplify the discussion, we assume a one-to-one correspondence between processes and sites and thus refer to both as processes, The coordinator is always the process with the largest priority number. Hence, when a coordinator fails, the algorithm must elect that active process with the largest priority number. This number must be sent to each active process in the system. In addition, the algorithm must provide a mechanism for a recovered process to identify the current coordinator.

The answer can be an existing algorithm on bi-directional ring election algorithm, it just has to be explained how it works.

Purchase this Solution

Solution Summary

Election algorithms are examined.

Solution Preview

Most of the text is actually about the unidirectional ring election algorithm, in which I changed notations and "imagery", as compared to that web page, to make it easier to explain and understand (I hope).

After that, the extension ...

Purchase this Solution


Free BrainMass Quizzes
Word 2010: Tables

Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.

Excel Introductory Quiz

This quiz tests your knowledge of basics of MS-Excel.

Javscript Basics

Quiz on basics of javascript programming language.

Basic Computer Terms

We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.