Parallel Algorithms
Showing that a program P has some property is a simple process if the actions inside the program are uninterruptible. However, when the action is interruptible, Lipton showed that through a type of reduction and analysis, it can be shown that the reduced program has that property if and only if the original program has the property. If the reduction is done by treating interruptible operations as one large uninterruptible action, even with these relaxed conditions properties can be proven for a program P. Thus, correctness proofs of a parallel system can often be greatly simplified.
Read more about this topic: Richard J. Lipton
Famous quotes containing the word parallel:
“The parallel between antifeminism and race prejudice is striking. The same underlying motives appear to be at work, namely fear, jealousy, feelings of insecurity, fear of economic competition, guilt feelings, and the like. Many of the leaders of the feminist movement in the nineteenth-century United States clearly understood the similarity of the motives at work in antifeminism and race discrimination and associated themselves with the anti slavery movement.”
—Ashley Montagu (b. 1905)