Efficient atomic broadcast using deterministic merge
Efficient atomic broadcast using deterministic merge
复制标题
DOI：
10.1145/343477.343620
复制
发表时间：
2000-07
期刊：
影响因子：
--
通讯作者：
M. Aguilera;R. Strom
中科院分区：
文献类型：
--
作者：
M. Aguilera;R. Strom
我们提出了一种合并来自分布在网络上的生产者的消息流的方法，使用独立于系统的任何不确定性的确定性算法，例如消息被网络延迟的时间量或其到达顺序。因此，如果在多个“合并”中复制该算法，则每次合并将以完全相同的方式合并消息流。因此，该技术是原子广播和全局原子多播的解决方案[12]。我们假设每个生产者都可以访问（大约）同步的时钟，并且可以估计所有生产者的预期消息速率。我们提出了一种算法，称为偏差算法。为了测量偏差算法的性能，我们假设消息是由以已知消息速率运行的无记忆进程生成的，并且我们测量给定时间 L 的预期总合并延迟。对于两个生产者进程的情况，我们在此度量中给出最佳算法，并表明当 L ⇒ ∞ 时，最佳算法收敛到我们的偏差算法。我们使用动态规划理论重新确认了我们的最优性结果，并使用模拟来验证该最优性结果在更现实的条件下的稳健性。
We present an approach for merging message streams from producers distributed over a network, using a deterministic algorithm that is independent of any nondeterminism of the system, such as the amount of time the messages are delayed by the network, or their arrival order. Thus, if this algorithm is replicated at multiple “mergers”, then each merger will merge the message streams in exactly the same way. The technique is therefore a solution to atomic broadcast and global atomic multicast [12]. We assume that each producer has access to (approximately) synchronized clocks and can estimate the expected message rates of all producers. We propose an algorithm, called the Bias Algorithm. To measure the performance of the Bias Algorithm, we assume that messages are generated by memoryless processes operating at known message rates, and we measure the expected total merge delay at a given time L. For the case of two producer processes, we give optimal algorithms in this metric, and show that the optimal algorithm converges to our Bias algorithm when L ⇒ ∞. We reconfirm our optimality result using Dynamic Programming theory, and we use simulations to validate the robustness of this optimality result under more realistic conditions.