REDUCTION - METHOD OF PROVING PROPERTIES OF PARALLEL PROGRAMS
REDUCTION - METHOD OF PROVING PROPERTIES OF PARALLEL PROGRAMS
复制标题
DOI：
10.1145/361227.361234
复制
发表时间：
1975-01-01
影响因子：
22.7
通讯作者：
LIPTON, RJ
中科院分区：
文献类型：
--
作者：
LIPTON, RJ
当证明一个并行程序有一个给定的属性时，通常假设一个语句是不可分割的，也就是说，该语句不能与程序的其余部分交织在一起。这里得到的充分条件表明，假设一个语句是不可分的，可以放松，仍然保持性能，如停机。因此，并行系统的正确性证明往往可以大大简化。
When proving that a parallel program has a given property it is often convenient to assume that a statement is indivisible, i.e. that the statement cannot be interleaved with the rest of the program. Here sufficient conditions are obtained to show that the assumption that a statement is indivisible can be relaxed and still preserve properties such as halting. Thus correctness proofs of a parallel system can often be greatly simplified.