Reduction: A New Method of Proving Properties of Systems of Processes

Abstract

When proving that a system of processes has a given property it is often convenient to assume that a routine is uninterruptible, i.e. that the routine cannot be interleaved with the rest of the system. Here sufficient conditions are obtained to show that the assumption that a routine is uninterruptible can be relaxed and still preserve basic properties such as halting and determinacy. Thus correctness proofs of a system of processes can often be greatly simplified. This technique - called reduction - is viewed as the replacement of an interruptible routine by an uninterruptible one.