3 ms·

> It says that the probability is not zero. That is a very important distinction for some people I'm not a mathematician, but I'm pretty sure it doesn't even s

> It says that the probability is not zero. That is a very important distinction for some people I'm not a mathematician, but I'm pretty sure it doesn't even say the probability of failed consensus must be nonzero. For example, the cantor set shows that it is possible to have a set with infinite elements, but zero length. That is equivalent to an infinite number of interleavings where consensus doesn't occur, but the probability of hitting any of them is zero. Sure in real world systems, the probability would always be nonzero, but when it's still so close to zero, it practically doesn't matter. Which is why in the real world, people do build very reliable distributed systems out of unreliable components.

frankmcsherry 9y ago
FLP says that any deterministic algorithm satisfying agreement and validity must have non-terminating executions. If you are allowed to pick the distribution over the sequence of events in the system I'm sure that the probability of non-termination is quickly zero. If FLP are allowed to pick the distribution, the probability of non-termination can be one. Getting into a quantitative evaluation of the likelihood of consensus is beyond my ken, but different people have different beliefs about what constitute "in real systems", and different interpretations of "practically doesn't matter". For example, the fact that you are talking about data centers rather than satellites suggests (to me) that your beliefs about the scarcity and transience of partitions may not generalize. We can afford to be clear about what is true and what isn't, especially when trying to build reliable distributed systems. Note: Ben-Or's consensus algorithm uses randomization to drive the probability of termination to zero, but still has non-zero probability associated with any length of execution.

frankmcsherry 9y ago

FLP says that any deterministic algorithm satisfying agreement and validity must have non-terminating executions. If you are allowed to pick the distribution over the sequence of events in the system I'm sure that the probability of non-termination is quickly zero. If FLP are allowed to pick the distribution, the probability of non-termination can be one. Getting into a quantitative evaluation of the likelihood of consensus is beyond my ken, but different people have different beliefs about what constitute "in real systems", and different interpretations of "practically doesn't matter". For example, the fact that you are talking about data centers rather than satellites suggests (to me) that your beliefs about the scarcity and transience of partitions may not generalize. We can afford to be clear about what is true and what isn't, especially when trying to build reliable distributed systems. Note: Ben-Or's consensus algorithm uses randomization to drive the probability of termination to zero, but still has non-zero probability associated with any length of execution.