António Casimiro

Timeout Adaptive Consensus: Improving Performance through Adaptation

Mônica Dixit and Henrique Moniz and António Casimiro

Technical Report DI/FCUL TR-10-06, Department of Informatics, University of Lisboa, November 2010


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.

BibTeX

@TechReport{di-fcul-tr-10-06,
    author = {Mônica Dixit and Henrique Moniz and António Casimiro},
    title = {Timeout Adaptive Consensus: Improving Performance through Adaptation},
    institution = {Department of Informatics, University of Lisbon},
    month = {November},
    year = {2010},
    type = {DI/FCUL TR},
    number = {10--06},
    url = {http://hdl.handle.net/10455/6686}
}

Technical report

Download technical report