How to solve consensus in the smallest window of synchrony

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.


Published in:
Proceedings of the 22nd International Symposium on Distributed Computing
Presented at:
22nd International Symposium on Distributed Computing, Arcachon, France, September 22-24, 2008
Year:
2008
Keywords:
Laboratories:




 Record created 2008-08-08, last modified 2018-10-07

n/a:
Download fulltextPDF
External link:
Download fulltextURL
Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)