How does a consensus algorithm guarantee consistency?

Question

How does a consensus algorithm like Paxos "guarantee safety (freedom from inconsistency)" when two generals prove the "impossibility of designing algorithms to safely agree"?

When I consider the simplest case of getting two servers to either (1) reliably exchange a number (ie, both servers end up knowing the other definitely received the number) or (2) both servers end up knowing the exchange failed and don't change their state, it would seem that (like the two generals) message failure could always happen in a way that left an inconsistency (ie, one server thinks the other finished the exchange, but it didn't).

So how does Paxos (or anything else) really guarantee "freedom from inconsistency"? Is there an explanation in simple language? What's the simplest pseudo-code demonstrating two servers doing a guaranteed exchange, or completely abandoning the exchange on failure?

Answer 1

The crux is this assumption by Paxos:

Liveness(C;L): If value C has been proposed, then eventually learner L will learn some value (if sufficient processors remain non-faulty).

The bad case for the two generals problem are when messengers are continuously intercepted. The "if sufficient processors remain non-faulty" part eliminates that possibility.

In other words, if messages are continuously dropped then Paxos is not required to (and won't) finish.

Answer 2

Paxos doesn't actually solve the 2 generals problem. As quoted from the wikipedia article:

In general, a consensus algorithm can make progress using 2F+1 processors despite the simultaneous failure of any F processors.

In the 2 generals problem, handling a failure of 1 node would mean that you would need 2*1 + 1 = 3 nodes to handle that many failures. The impossibility of the 2 generals problem is not generalized to N generals.

One way people solve the 2 generals problem in the real world is fencing.