[inigyou]

Wasn't there an impossibility proof for consensus without timeouts? At the boundary between a consensus failure and success, there must be a certain message that, if you delay it enough, causes a consensus failure, and that implies either you wait forever for that message (deadlock) or you eventually give up waiting (timeout).

[nano_o]

It's impossible to do it deterministically (that's the famous FLP impossibility result), but if you accept to have liveness only with probability 1 then it's possible (for example, an early randomized asynchronous protocol is Ben-Or's protocol from 1983).