Ring based algorithm using MPI

The aim of the assignment is to complete the distributed algorithm of ring-based election algorithm using MPI Goals: Learn about the leader election problem. Understand and implement two algorithms for electing a leader in a ring. Part 1: simple Ring-based election Le Lann-Chang-Roberts Leader Election (basic ring-based): This is perhaps the simplest of all distributed algorithms. However, it has lousy message complexity. It sends around n squared messages in the worst case. The idea of this algorithm is that each process starts by passing its own identifier to its neighbor. Whenever a process receives an identifier from its neighbor, it either: passes it on around the ring, if the id received is greater than its own, discards it, if the id received is less than its own, or declares itself the leader, if the id received matches its own. Notice that the process with the greatest identifier is elected. Create a module that implements this algorithm. Then, instantiate it many times and arrange the communication pattern in a ring in order to test that it works. You'll need to make some provision for initially assigning each instance a unique identifier. Part 2: Improved Ring-based Election Peterson Leader Election Algorithm: This algorithm for leader election in a ring is a bit more involved, but its worst case message complexity is much better. See if you can figure out (on paper) the message complexity of this algorithm. (Hint: notice that at least half of the processors become relays after each round of communication.) The algorithm works as follows: In the first phase, each process sends its identifier two steps clockwise (so each process sees the identifiers of its neighbor and its next-to-last neighbor). Each process P makes a decision based on its own identifier and the identifiers it has recieved. If P's immediate neighbor's identifier is the greatest of the three, then P remains "active" in the algorithm and adopts its neighbor's identifier as its own. Otherwise, P becomes a "relay". Now, each active process sends its identifier to its next two active neighbors, clockwise around the ring. Relay processes simply pass along each message they receive. Steps 2 and 3 continue repeatedly, with more and more processes dropping out as "relays" until a process finds that its own immediate neighbor is itself, in which case everyone else has dropped out and it declares itself the leader. Implement this algorithm as a module. Be sure to think about how you will manage sending a message two steps around the ring of active processes. Also, be sure to print out useful messages from the modules in order to demonstrate that your algorithm is working properly. For example, at each round, active modules should print out the round number, the messages received from the two neighbors, and the decision of whether to remain active or become a relay.