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