How to Choose a Timing Model?

Authors: Idit Keidar and Alex Shraer.

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.

Abstract:

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.

Download:

Preprint of DSN paper: ps, ps.gz, pdf, pdf.gz.
Preprint of TPDS paper: pdf, pdf.gz.
Technical Report CCIT 586, Technion Department of Electrical Engineering, December 2006: pdf.