Since the processes can only receive message from their adjacent neighbors, we could first have the all the processes propagate the maximum values through the grid in downward direction in parallel. Similar to a one dimensional array in which we have to find the maximum value. But here, we do that in parallel for n columns of processes.
After this, the last row would contain the maximum values of each column. Then, we could have the last row propagate the maximum value in the right direction so that the (n,n)th element contains the maximum value from this row. Since this row contained the maximum values from each column, (n,n)th element will essentially possess the maximum value from the entire grid.
We could then choose to propagate this value through the grid in parallel backwards till all the nodes know about this maximum value.
Complexity will be O(n) and there will be 4n hops of message passing through this proposed scheme.
Edit: Here's A pseudo-code. Disclaimer: not tested, might contain bugs
findMaxAllThreads(){
int maxVal;
// At the start, each element's max value will exactly be its value itself.
maxVal = procId.val;
// If this is the first element in the column, simply send the current
// max value to the next element within the column.
if(procId.row == 1)
sendMessage(procId.row + 1, procId.col, maxVal);
// For any other element in a particular column, except the last one,
// compare the received value with the current max value and send the
// updated value to the next element.
else if(procId.row < n)
{
// wait for the message from the previous element in the column.
recvMessage(procId.row - 1, procId.col, val);
// update the max value till this node.
if(val > maxVal)
maxVal = val;
// send the updated max value to the next element in the column.
sendMessage(procId.row + 1, procId.col, maxVal);
}
// If we reach the last element in the column, we need to propagate the
// values rightwards to the next element within the last row.
else
{
// Receive the message from the (n-1)th element in the column.
recvMessage(procId.row - 1, procId.col, val);
// update the max value. Note that this will be the maximum value of
// this particular column.
if(val > maxVal)
maxVal = val;
// If this is the (n,1)th element in the whole grid (bottom left), then
// simply propagate the max value to the next element rightwards in the
// row.
if(procId.col == 1)
sendMessage(procId.row, procId.col + 1, maxVal);
else
{
// Wait for the value from the previous element in this row.
recvMessage(procId.row, procId.col - 1, val);
// Update the max value till now.
if(val > maxVal)
maxVal = val;
// If this is not the (n,n)th element in the grid, propagate the
// value to the right.
if(procId.col != n)
{
// Propagate the max value to the right.
sendMessage(procId.row, procId.col + 1, maxVal);
}
// if this is the bottom-right (n,n)th element in the grid, wait
// for the final value arriving from the (n, n-1)th element from
// the left.
else
{
// Receive the message from the (n-1)the element in the nth row.
recvMessage(procId.row, procId.col - 1, val);
// Update the value. Note that this is also the maximum value
// in the entire grid.
if(val > maxVal)
maxVal = val;
// Now maxVal contains the maximum value from all the processes.
// We could choose to report it or if we want, we could
// propagate it all the way back to the first node, so that
// it's known globally as the max value.
}
}
}
}