A data decomposition solution would be to consider the entire set of exams as a large data collection, divide up the exams among the assistants, and have each grader repeatedly take an exam and grade the entire thing. How the work gets distributed can be done many different ways. For example, the collection of exams can be divided into equal piles, one per student assistant, or they can be left in a large stack in the middle of the table and whenever an assistant needs a new exam to grade, they simply pull the top one off the stack. Any scheme like this will just be a detail of implementation, but could affect the time needed to complete the exam grading.

(If you're wondering how to design the exam-grading algorithm for both a task and data decomposition and still come up with the same implementation, consider the second exam distribution example in the previous paragraph. If we define a task to be grading all questions on a single exam, we might set up all the ungraded exams into a stack in the middle of a table. Then, we simply add the step of pulling the top exam off the stack to the whole task of grading an exam. This describes the shared stack data decomposition algorithm outlined above.)

So, what does a data decomposition of Bubblesort look like? The large collection of data is going to be the array of values that is to be sorted. I guess we simply divide that into some number of non-overlapping sections and assign a thread to run Bubblesort on the values in an assigned section. I can illustrate how this would work by returning to the "Shakespeare characters sorting books on a long shelf on a submarine" metaphor I've used in the past, but with two changes. First, none of the sorting characters will be roaming beyond their assigned section of books. They will be able to reach over into a succeeding section for that one book that must be swapped for the last book in their section, though. This could require some coordination between characters in adjoining sections. Second, since none of the sorters will be moving between sections, there are no doors that need to be opened. We can simply use the bulkheads where the door would have been to signify the boundaries between discrete sections.

From this arrangement, the biggest question that springs to my mind is: How do the sorters know when the sort has completed? Banquo and Duncan can only see the section of books they have been assigned to sort. One easy answer to my question would be for each sorter to run one pass for each element in the full data set. This will ensure that the worst-case scenario, for Bubblesort, (i.e., the lowest-keyed item is initially located in the final position, [N], of the unsorted data) is handled properly. It will require N passes to move that lowest-keyed item to its final sorted position. Thus, if each sorter runs N passes through their portion of the bookshelf (assuming proper coordination at the bulkhead boundaries), then the data will be guaranteed to be sorted, right? Not quite.

What if Banquo precedes Duncan in the order of two sorters assigned and Banquo also sorts slower than Duncan (perhaps Banquo is distracted by the colorful cover each time he looks at a book or maybe he just walks slower than Duncan)? If there are 100 books divided between the two characters and Duncan is 10 times faster at sorting than Banquo, then Duncan will have passed through his 50 titles the required 100 times in the time that Banquo needs to complete 10 passes. If the original list was in reverse sorted order, there will be at least 40 books in Banquo's section that must be in Duncan's section and no way for Duncan to handle any of them since he believes that his work is done.

Alternately, could I devise a method to use the lack of exchanges to determine when the sorting process has completed? We saw that this was possible to do with the serial algorithm and with the task decomposition parallel solution. Unfortunately, Banquo can only see his assigned section of books. Just because there are no local exchanges for Banquo, it doesn't mean that Duncan isn't performing exchanges within his assigned section. Consequently, there is no way for Banquo to know if some book might be working its way up or down the shelf and eventually enter his section to create exchanges.