Hints for Question 3

In the first round only the processors located at one of the ends of the network (left side of the mesh, right side of the mesh, top of the mesh, or bottom of the mesh) send messages.

In the first part of the algorithm, processor ID's are compared as messages travel along the network toward the opposite end of the network (opposite end depends on which end started sending messages). So at the end of the first part of the algorithm the largest ID in each row or column (depending on in which direction messages travelled) will be known by which processors? These processors are in the same row or column of the mesh. They then determine which the largest ID is (using a similar algorithm as for question 2).

After the largest ID is determined, during the second part of the algorithm the largest ID is sent back along the network (this time each processor might need to send 2 messages and not only one as for question 2) so each processor will know who the leader is and all processor can change their status to the proper value.

Try to solve the problem with the above hint. If you really do not see how to design the algorithm, here is are additional hints.