With the serial and task decomposition algorithms, each character got to pass over the entire collection of books. If, after running through the shelf, Duncan realized that he did not perform any exchanges, he set a flag. All the other characters eventually checked the flag and knew that their work was done. Under the data decomposition model, since no character sees the entire collection of data, I need to implement some way for each character to know whether any other character performed an exchange.

One method would be for each character to send a signal that all others can hear if they had performed at least one exchange. Since sound carries well underwater and through the hull of a submarine, I imagine placing a hammer at the end of each book shelf section. If an exchange was made, whenever a character reached the end of their section, they would strike the hull to let everyone know. If the signal is heard, all characters go back to the start of their book section and start another pass. If no signal is heard, then it is known that all characters had no exchanges and the data is in sorted order.

If you've been paying even a slight amount of attention as you read this, you can probably see the small complication with my signal scheme. How long do characters wait for the signal before they declare the whole bookshelf sorted and stop working? If there is one character slower than all others (or, worse, if characters are unpredictably afflicted with slower sorting from one pass to another), is the lack of signal due to the fact that the slow character hasn't reached the end of her section or that there were no exchanges across the entire shelf? Clearly, implementing this signal scheme will require some additional coordination to be sure that each character has completed a full pass through their section before listening for the hammer ping signal, or lack thereof.

One other facet to this problem we can consider is that the higher indexed elements of the array are settled after each complete pass through the data. As the sort proceeds, those characters in the latter sections will soon be passing through their books but not doing any local exchanges and there will be no new books to create the possibility of new exchanges. Could I develop a way to redraw and redistribute the sections as the algorithm goes on such that I keep the most characters doing some useful sorting of books? Probably. However, that's something I will leave to you the reader to pursue if you're interested.

The next post will have my implementation of a data decomposition version of Bubblesort. Between now and then, ponder how to coordinate threads to know when all others have completed a pass through their assigned sections.