How to Choose a Timing Model?

	This Article
	Subscribers, please Login Purchase article: $19 PDF IEEE Xplore Subscribers RSS feed
	Share
	Email this Article to a friend
	Bibliographic References
	ASCII Text BibTex RefWorks Procite/RefMan
	Add to:
	Digg Furl Spurl Blink Simpy Google Del.icio.us Y!MyWeb
	Search
	Similar Articles Articles by Idit Keidar Articles by Alexander Shraer

37th Annual IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'07)

How to Choose a Timing Model?

Edinburgh, UK

June 25-June 28

ISBN: 0-7695-2855-4

	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

DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/DSN.2007.55

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

Peer Review Notice | Give Us Feedback

Usage of this product signifies your acceptance of the Terms of Use.