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:
“As I look at the human story I see two stories. They run parallel and never meet. One is of people who live, as they can or must, the events that arrive; the other is of people who live, as they intend, the events they create.”
—Margaret Anderson (1886–1973)