More Hints for Question 2
Each processor checks how many neigbours they have. The first processor has
only a neighbour on the right, the last processor has only one neighbour on the
left, and all other processors have 2 neighbours.
Suppose the you decide that the first processor will send a message during the first round.
Since the same algorithm is executed by all the processors, the algorithm must
check if the processor executing it is the first one; if so the message is
buffered, otherwise the buffer is kept empty.
During the first part of the algorithm, in each round the message is sent to
the right, the message is received and
processed by the next processor p, which also creates a message to be
sent in the next round. If p is not the last processor, then the
message that it creates will travel to the right, otherwise it will travel to
the left ending the first part of the algorithm.
In the second part of the algorithm the messages travel to the left
(a processor knows in which direction the messages are traveling by looking
in the message at the address of the processor that sent it the message).
After a processor
receives a message traveling to the left, the processor will forward it in
the next round (if it has a left neighbour) and then what should it do?