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 beginnings of altruism can be seen in children as early as the age of two. How then can we be so concerned that they count by the age of three, read by four, and walk with their hands across the overhead parallel bars by five, and not be concerned that they act with kindness to others?”
—Neil Kurshan (20th century)