Necessary and Sufficient Conditions for 1-adaptivity
Necessary and Sufficient Conditions for 1-adaptivity
复制标题
1-适应性的充分必要条件
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
S. Haddad
中科院分区：
文献类型：
--
作者：
J. Beauquier;S. Delaët;S. Haddad
1-自适应自稳定系统是一种自稳定系统，它可以在一个计算步骤中纠正单个进程的任何内存损坏。1-自适应性意味着如果在合法状态下单个进程的存储器被破坏，则下一个系统转换将导致合法状态，并且系统将恢复正确的行为。因此，1-自适应自稳定算法保证了非常强的属性，即一个单一的故障立即纠正，因此，它不能传播。我们的目标是研究获得该性质的必要和充分条件，以便设计这样的算法。特别是，我们表明，即使在分布式恶魔，它也可以应用于概率算法，这个属性可以得到。我们提供了两个自稳定的1-自适应算法，演示了我们在这里提出的条件可以用来设计和证明1-自适应算法。
A 1-adaptive self-stabilizing system is a self-stabilizing system that can correct any memory corruption of a single process in one computation step. 1-adaptivity means that if in a legitimate state the memory of a single process is corrupted, then the next system transition will lead to a legitimate state and the system will recover a correct behavior. Thus 1-adaptive self-stabilizing algorithms guarantee the very strong property that a single fault is corrected immediately and consequently that it cannot be propagated. Our aim here is to study necessary and sufficient conditions to obtain that property in order to design such algorithms. In particular we show that this property can be obtained even under the distributed demon and that it can also be applied to probabilistic algorithms. We provide two self-stabilizing 1-adaptive algorithms that demonstrate how the conditions we present here can be used to design and prove 1-adaptive algorithms.