Ask Operating System Expert

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

The ring algorithm supposes that the links are unidirectional and that every procedure sends its message to the neighbor on the right. The main data structure used through 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.

Operating System, Computer Science

  • Category:- Operating System
  • Reference No.:- M9314998

Have any Question?


Related Questions in Operating System

Research types of operating systems that are currently

Research types of operating systems that are currently available and provide a scenario in which the operating system you chose would be appropriate to be used in this situation. Explain why you think the choice you made ...

Question research hex editors available for mac os and

Question : Research hex editors available for Mac OS and Linux. Based on the documentation, how easy would validating these tools be? Select at least two hex editors for each OS, and discuss what you would do to validate ...

Foundation of information technologyresearch types of

Foundation of Information Technology Research types of operating systems that are currently available and provide a scenario in which the operating system you chose would be appropriate to be used in this situation. Expl ...

Assignment -building a multi-threaded web server using c

Assignment - Building a multi-threaded web server using C and p threads, following the model from the lecture. Your program will have one thread acting as a dispatcher thread, listening fornetwork connections with reques ...

Question you are a security administrator responsible for

Question: You are a security administrator responsible for providing secure configuration requirements for new laptop deployments. After reading Module 2 of Certified Secure Computer User v2exercises, apply the configura ...

Question what do you see as the major differences between

Question : What do you see as the major differences between UNIX/Linux and other operating systems, such as Windows and Mac OS X? The response must be typed, single spaced, must be in times new roman font (size 12) and m ...

Question description of lasa in this assignment you will

Question: Description of LASA: In this assignment, you will select a real-world operating system (can be for a PC, server, tablet, handheld, or embedded device). You will introduce the operating system and its components ...

Discussion question this research assignment will give

Discussion Question : This research assignment will give further information on the nature and workings of multi-tasking and multi-processing operating systems. All information reported in this assignment is to be in the ...

Taskyour job in this assignment is to create two virtual

Task Your job in this assignment is to create two Virtual machines each running a different but the latest distribution of Linux e.g. Ubuntu Server and CentOS. Each of these VM's is to offer services to a user base. The ...

State the required answer precisely and then provide proper

State the required answer precisely and then provide proper explanation. It is not enough to provide one- word or one-line answers. Briefly describe the following concepts and indicate how they are related in the context ...

  • 4,153,160 Questions Asked
  • 13,132 Experts
  • 2,558,936 Questions Answered

Ask Experts for help!!

Looking for Assignment Help?

Start excelling in your Courses, Get help with Assignment

Write us your full requirement for evaluation and you will receive response within 20 minutes turnaround time.

Ask Now Help with Problems, Get a Best Answer

Why might a bank avoid the use of interest rate swaps even

Why might a bank avoid the use of interest rate swaps, even when the institution is exposed to significant interest rate

Describe the difference between zero coupon bonds and

Describe the difference between zero coupon bonds and coupon bonds. Under what conditions will a coupon bond sell at a p

Compute the present value of an annuity of 880 per year

Compute the present value of an annuity of $ 880 per year for 16 years, given a discount rate of 6 percent per annum. As

Compute the present value of an 1150 payment made in ten

Compute the present value of an $1,150 payment made in ten years when the discount rate is 12 percent. (Do not round int

Compute the present value of an annuity of 699 per year

Compute the present value of an annuity of $ 699 per year for 19 years, given a discount rate of 6 percent per annum. As