How to Choose a Timing Model?
Idit Keidar and
In the 37th IEEE/IFIP Int'l
Conf. on Dependable Systems and Networks (DSN),
pages 389-398, June 2007.
Full version in IEEE Transactions
on Parallel and Distributed Systems (TPDS)
19(10), pages 1367-1380, October 2008.
Earlier version: Technical Report CCIT 586,
Technion Department of Electrical Engineering, December 2006.
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.
Preprint of DSN paper:
Preprint of TPDS paper:
Technical Report CCIT 586, Technion Department
of Electrical Engineering, December 2006: