Early-Delivery Dynamic Atomic Broadcast
Early-Delivery Dynamic Atomic Broadcast
复制标题
早期交付动态原子广播
DOI：
10.1007/3-540-36108-1_1
复制
发表时间：
2002
期刊：
影响因子：
--
通讯作者：
N. Lynch
中科院分区：
文献类型：
--
作者：
Z. Bar;I. Keidar;N. Lynch
我们考虑一个原子广播的问题，在一个动态的设置过程中可能加入，自愿离开，或失败（停止）在计算过程中。我们提供了一个正式的定义的动态原子广播问题，并提出和分析了一个新的算法，其解决方案的一个变种的同步模型，其中进程有近似同步的clocks.Our算法表现出恒定的消息传递延迟的情况下，失败，即使在期间，当参与者加入或离开。据我们所知，这是第一个算法完全有序的多播在动态设置，以实现恒定的延迟界限，在加入和离开的存在。当失败发生时，延迟界限与实际失败的数量成线性关系。我们的算法使用一个解决方案的标准分布式共识问题的变化，其中参与者不知道先验的其他参与者是谁。我们定义了新的问题，我们称之为共识与不确定的参与者，并给出了一个早期决策算法来解决它。
We consider a problem of atomic broadcast in a dynamic setting where processes may join, leave voluntarily, or fail (by stopping) during the course of computation. We provide a formal definition of the Dynamic Atomic Broadcast problem and present and analyze a new algorithm for its solution in a variant of a synchronous model, where processes have approximately synchronized clocks.Our algorithm exhibits constant message delivery latency in the absence of failures, even during periods when participants join or leave. To the best of our knowledge, this is the first algorithm for totally ordered multicast in a dynamic setting to achieve constant latency bounds in the presence of joins and leaves. When failures occur, the latency bound is linear in the number of actual failures. Our algorithm uses a solution to a variation on the standard distributed consensus problem, in which participants do not know a priori who the other participants are. We define the new problem, which we call Consensus with Uncertain Participants, and give an early-deciding algorithm to solve it.