分布式计算中稳定性质的等价类划分

AN EQUIVALENCE PARTITION OF STABLE PROPERTIES IN DISTRIBUTED COMPUTATIONS

分布式计算中的稳定性质是那些在计算中一旦成立将保持成立的性质，如分布式死锁、分布式终止和分布式废码等．稳定性质检测是分布式计算中的重要问题，常通过构造一致全局系统状态来检测稳定性质．本文研究可以在任意系统状态上计算的稳定性质，基于相关事件的概念，定义了强稳定性质和局部稳定性质，证明了局部稳定性质是强稳定性质，存在不是局部稳定性质的强稳定性质和不是强稳定性质的稳定性质．证明了分布式废码是强稳定性质，修正了以前的结论．第一次给出了稳定性质的等价类分类，定义了在任意系统状态上稳定性质的语义．给出了检测强稳定性质的局部算法和控制算法，本文结论的理论意义在于揭示了稳定性质间的共性和异性，其实践意义在于可由一类稳定性质的检测算法得到另一类稳定性质的检测算法．

Stable properties are those that once true, will keep true in a distributedcomputation, such as distributed deadlock, distributed termination and distributedgarbage. Stable properties detection is fundamental for distributed computations.We often compute stable properties by constructing consistent global system states.This paper is about computing stable properties on any system states. Based on theconcept of relative events, two special stable properties named strong stable proper-ty and locally stable property are formally defined. It is proved that a locally stableproperty is a strong one, but not vice versa. There exist strong stable propertieswhich are not locally stable ones and stable properties which are not strong stableones. It is showed that distributed garbage is a strong stable property, which revis-es the former result. The equivalence partition of stable properties is further pre-sented, which has been an open problem. A formal semantics for stable propertieson any system states is given. The local algorithm and monitoring algorithm for str-ong stable properties detection are developed which are more efficient than tradi-tional algorithms. Our results reveal common characteristics and differentiae of var-ious stable properties and suggest us to derive algorithms for one sort of stableproperties from algorithms for another sort of stable properties.