loading...
How to Choose a Timing Model?
Edinburgh, UK June 25-June 28
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DSN.2007.5537th Annual IEEE/IFIP International C ...
 This Article 
 
Buy PURCHASE ARTICLE: $19
PDF
HTML
Buy IEEE Xplore Subscribers
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
ASCII Text
x 
 
Idit Keidar, Alexander Shraer, "How to Choose a Timing Model?," Dependable Systems and Networks, International Conference on, pp. 389-398, 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'07), 2007.
 
 
BibTex
x
 
@article{ 10.1109/DSN.2007.55,
author = {Idit Keidar and Alexander Shraer},
title = {How to Choose a Timing Model?},
journal ={Dependable Systems and Networks, International Conference on},
volume = {0},
year = {2007},
isbn = {0-7695-2855-4},
pages = {389-398},
doi = {http://doi.ieeecomputersociety.org/10.1109/DSN.2007.55},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
}
 
 
RefWorks Procite/RefMan/Endnote
x 
 
TY - CONF
JO - Dependable Systems and Networks, International Conference on
TI - How to Choose a Timing Model?
SN - 0-7695-2855-4
SP389
EP398
A1 - Idit Keidar,
A1 - Alexander Shraer,
PY - 2007
KW - synchrony assumptions
KW - eventual synchrony
KW - failure detectors
KW - consensus algorithms
KW - FT Middleware.
VL - 0
JA - Dependable Systems and Networks, International Conference on
ER -
 
Idit Keidar, Technion, Israel
Alexander Shraer, Technion, Israel
When employing a consensus algorithm for state machine replication, should one optimize for the case that all communication links are usually timely, or for fewer timely links? Does optimizing a protocol for better message complexity hamper the time complexity? In this paper, we investigate these types of questions using mathematical analysis as well as experiments over PlanetLab (WAN) and a LAN. We present a new and efficient leader-based consensus protocol that has O(n) stable-state message complexity (in a system with n processes) and requires only O(n) links to be timely at stable times. We compare this protocol with several previously suggested protocols. Our results show that a protocol that requires fewer timely links can achieve better performance, even if it sends fewer messages.
Index Terms:
synchrony assumptions, eventual synchrony, failure detectors, consensus algorithms, FT Middleware.
Citation:
Idit Keidar, Alexander Shraer, "How to Choose a Timing Model?," dsn, pp.389-398, 37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'07), 2007
Usage of this product signifies your acceptance of the Terms of Use.