Performance comparison of a rotating coordinator and a leader based consensus algorithm
Performance comparison of a rotating coordinator and a leader based consensus algorithm
复制标题
DOI：
10.1109/reldis.2004.1352999
复制
发表时间：
2004-03
期刊：
影响因子：
--
通讯作者：
P. Urbán;Naohiro Hayashibara;A. Schiper;T. Katayama
中科院分区：
文献类型：
--
作者：
P. Urbán;Naohiro Hayashibara;A. Schiper;T. Katayama
解决协议问题的协议是容错分布式系统的重要构建块。虽然已经发布了许多协议，但很少有人分析它们的性能，尤其是其容错机制的性能。在本文中，我们比较了两种著名的异步共识算法。在这两种算法中，一个领导者进程尝试强加一个决定，如果领导者失败，另一个领导者会重试。这些算法以不同的方式选举领导者：Chandra-Toueg 算法有一个轮换领导者，而 Paxos 算法中的进程直接选举领导者。我们研究了这种差异对性能的影响。在所研究的系统中，进程相互发送原子广播。共识用于决定消息的传递顺序。我们评估了（1）既没有崩溃也没有怀疑的运行，（2）有崩溃的运行和（3）没有崩溃的运行（其中正确的进程被错误地怀疑崩溃）的稳态延迟，以及（4）一次崩溃和（5）多次相关崩溃后的瞬态延迟。结果表明，Paxos 算法能够更好地容忍频繁的错误怀疑 (3) 和相关崩溃 (5)，而在所有其他场景中性能相当。
Protocols that solve agreement problems are essential building blocks for fault tolerant distributed systems. While many protocols have been published, little has been done to analyze their performance, especially the performance of their fault tolerance mechanisms. In this paper, we compare two well-known asynchronous consensus algorithms. In both algorithms, a leader process tries to impose a decision, and another leader retries if the leader fails doing so. The algorithms elect leaders differently: the Chandra-Toueg algorithm has a rotating leader, whereas processes in the Paxos algorithm elect leaders directly. We investigate the performance implications of this difference. In the system under study, processes send atomic broadcasts to each other. Consensus is used to decide the delivery order of messages. We evaluate the steady state latency in (1) runs with neither crashes nor suspicions, (2) runs with crashes and (3) runs with no crashes in which correct processes are wrongly suspected to have crashed, as well as the transient latency after (4) one crash and (5) multiple correlated crashes. The results show that the Paxos algorithm tolerates frequent wrong suspicions (3) and correlated crashes (5) better, while the performance is comparable in all other scenarios.