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?