When Consensus Meets Self-stabilization
When Consensus Meets Self-stabilization
复制标题
当共识遇见自我稳定
DOI：
--
复制
发表时间：
2006
期刊：
影响因子：
--
通讯作者：
E. Schiller
中科院分区：
文献类型：
--
作者：
S. Dolev;Ronen I. Kat;E. Schiller
本文提出了一种共享内存自稳定故障检测器、异步一致性和复制状态机算法套件，其组件可以在任意状态下启动并收敛以充当虚拟状态机。自稳定算法可以科普瞬时故障。瞬时故障可以将系统状态改变为任意状态，从而导致暂时违反共识的安全属性。在一个任意的状态开始，长寿命的，内存限制和自稳定的故障检测器，异步共识，并复制状态机套件，在该文件中，恢复，以满足最终的安全性和最终的活性要求。介绍了几种新的技术和范例。有界内存故障检测器使用有界心跳计数器结合平衡-不平衡机制抽象出同步假设。在自稳定的范围内引入了实际无限范式，其中，例如，2^6^4个连续步骤的执行被认为是（实际上）无限的。最后，我们提出了第一个自稳定无等待重置机制，确保最终的安全性，并可用于实现高效的自稳定时间戳是独立的利益。
This paper presents a shared-memory self-stabilizing failure detector, asynchronous consensus and replicated state-machine algorithm suite, the components of which can be started in an arbitrary state and converge to act as a virtual state-machine. Self-stabilizing algorithms can cope with transient faults. Transient faults can alter the system state to an arbitrary state and hence, cause a temporary violation of the safety property of the consensus. Started in an arbitrary state, the long lived, memory bounded and self-stabilizing failure detector, asynchronous consensus, and replicated state-machine suite, presented in the paper, recovers to satisfy eventual safety and eventual liveness requirements. Several new techniques and paradigms are introduced. The bounded memory failure detector abstracts away synchronization assumptions using bounded heartbeat counters combined with a balance-unbalance mechanism. The practically infinite paradigm is introduced in the scope of self-stabilization, where an execution of, say, 2^6^4 sequential steps is regarded as (practically) infinite. Finally, we present the first self-stabilizing wait-free reset mechanism that ensures eventual safety and can be used to implement efficient self-stabilizing timestamps that are of independent interest.