Français | English
EPFL > infoscience > How to solve consensus in the smallest window of synchrony
|
Alistarh, Dan ; Gilbert, Seth ; Guerraoui, Rachid ; Travers, Corentin Presented at: 22nd International Symposium on Distributed Computing, Arcachon, France, September 22-24, 2008. In: Proceedings of the 22nd International Symposium on Distributed Computing, 2008 Date: 2008 This paper addresses the following question: what is the minimum-sized synchronous window needed to solve consensus in an otherwise asynchronous system? In answer to this question, we present the first optimally-resilient algorithm ASAP that solves consensus as soon as possible in an eventually synchronous system, i.e., a system that from some time GST onwards, delivers messages in a timely fashion. ASAP guarantees that, in an execution with at most f failures, every process decides no later than round GST + f + 2, which is optimal. Keyword(s): distributed computing, consensus, eventual synchrony, optimally resilient Reference: LPD-CONF-2008-032 |
|
|
Record created on 2008-08-08, modified on 2010-03-13 |
|
Download fulltext
smallest_wi[...]..pdf