How to Choose a Timing Model
作者： Idit Keidar Alexander Shraer , I Keidar , None
DOI: 10.1109/DSN.2007.55
关键词:
摘要: When employing a consensus algorithm for state machine replication, should one optimize the case that all communication links are usually timely, or fewer timely links? Does optimizing protocol better message complexity hamper time complexity? In this paper, we investigate these types of questions using mathematical analysis as well experiments over PlanetLab (WAN) and LAN. We present new efficient leader-based has O(n) stable-state (in system with n processes) requires only to be at stable times. compare several previously suggested protocols. Our results show can achieve performance, even if it sends messages.
computer.org
sci-hub.se 参考文章(28)
Ulrich Schmid, Failure Model Coverage under Transient Link Failures ,(2008)
N.A. Lynch, M.R. Tuttle, An introduction to input/output automata CWI quarterly. ,vol. 2, pp. 219- 246 ,(1989)
Marcos K. Aguilera, Carole Delporte-Gallet, Hugues Fauconnier, Sam Toueg, Stable Leader Election international symposium on distributed computing. pp. 108- 122 ,(2001) , 10.1007/3-540-45414-4_8
Danny Dolev, Tal Anker, Ilya Shnayderman, Gregory Greenman, Evaluating Total Order Algorithms in WAN ,(2003)
P Dutta, R Guerraoui, I Keidar, None, The Overhead of Indulgent Failure Recovery Distributed Computing. ,(2006)
Rachid Guerraoui, Revistiting the Relationship Between Non-Blocking Atomic Commitment and Consensus international workshop on distributed algorithms. pp. 87- 100 ,(1995) , 10.1007/BFB0022140
Partha Dutta, Rachid Guerraoui, Fast Indulgent Consensus with Zero Degradation european dependable computing conference. pp. 191- 208 ,(2002) , 10.1007/3-540-36080-8_18
Cynthia Dwork, Nancy Lynch, Larry Stockmeyer, Consensus in the presence of partial synchrony Journal of the ACM. ,vol. 35, pp. 288- 323 ,(1988) , 10.1145/42282.42283
Herman Chernoff, A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations Annals of Mathematical Statistics. ,vol. 23, pp. 493- 507 ,(1952) , 10.1214/AOMS/1177729330
Leslie Lamport, The implementation of reliable distributed multiprocess systems Computer Networks. ,vol. 2, pp. 95- 114 ,(1978) , 10.1016/0376-5075(78)90045-4