@inproceedings{dutta2005how,
author = {Dutta, Partha and Guerraoui, Rachid and Lamport, Leslie},
title = {How Fast Can Eventual Synchrony Lead to Consensus?},
booktitle = {Proceedings of the International Conference on Dependable Systems and Networks (DSN 2005)},
year = {2005},
month = {June},
abstract = {During a visit I made to the EPFL in March 2004, Dutta and Guerraoui explained a problem they were working on. Asynchronous consensus algorithms like Paxos [122] maintain safety despite asynchrony, but are guaranteed to make progress only when the system becomes synchronous--meaning that messages are delivered in a bounded length of time. Dutta and Guerraoui were looking for an algorithm that always reaches agreement within a constant number of message delays after the system becomes synchronous. This is a hard problem only if messages sent before the system becomes synchronous can be delivered arbitrarily far in the future. I took the solution they had come up with and combined it with Paxos to obtain the algorithm described is this paper. It's a nice solution to a mildly interesting theoretical problem with no apparent practical application. As I recall, I wanted to include a sentence in the paper saying this, but my co-authors sensibly pointed out that doing so would ensure the paper's rejection. (My co-authors don't remember this.) Computer scientists in this field must keep up the pretense that everything they do is practical.},
url = {http://approjects.co.za/?big=en-us/research/publication/how-fast-can-eventual-synchrony-lead-to-consensus/},
edition = {Proceedings of the International Conference on Dependable Systems and Networks (DSN 2005)},
}