How Fast Can Eventual Synchrony Lead to Consensus?

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.