3 ms·
What's interesting here is that this would be the first production implementation of an asynchronous consensus algorithm (QuePaxa). Paxos, Raft, etc. are all pa
by nano_o 3mo ago
What's interesting here is that this would be the first production implementation of an asynchronous consensus algorithm (QuePaxa). Paxos, Raft, etc. are all partially synchronous, meaning they rely on timeouts and only make progress if message delay is sufficiently small compared to timeout durations. QuePaxa doesn't rely on timeouts and makes progress even under wild fluctuations in message delay. The question is whether performance is competitive enough in the normal case, when message delay is small and doesn't vary much, and historically the answer has been "no" and that's why asynchronous protocols weren't used.
- inigyou 3mo agoWasn'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 3mo agoIt'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).