“Timeout Adaptive Consensus: Improving Performance through Adaptation”
University of Lisbon, DI-FCUL, Tech. Rep. TR-2010-06, Nov. 2010.http://hdl.handle.net/10455/6686.
Abstract: Algorithms for solving distributed system problems, such as consensus, often use timeouts as a mean to achieve progress, even if encapsulated in failure detection services. They are designed in a way that safety is always preserved despite timeouts being too small or too large. A “reasonable” timeout value is usually selected, such that the run-time performance is acceptable in the normal case. In this paper we transform a fixed timeout consensus protocol into a timeout adaptive protocol, showing how this can be done in a structured way and demonstrating the performance improvements that we achieve. Our results are particularly significant in networking environments subject to uncertain or varying end-to-end delays, such as wireless environments with several nodes contending for medium access. With the timeout adaptive solution the number of transmitted broadcasts per consensus execution is always kept small, despite the number of involved processes. In addition, the overall protocol latency is also improved when comparing to the static version.
Research line(s): Timeliness and Adaptation in Dependable Systems (TADS)