CODEWITHSUNDEEP
algorithmdistributed-computinghandshakepaxosconsensus
Witness Protection ID 44583292
Witness Protection ID 44583292

Reputation: 1120

How does a consensus algorithm guarantee consistency?

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?

Upvotes: 6

Views: 1296

Answers (3)

Darsh Gondalia
Darsh Gondalia

Reputation: 36

This is my understanding of the question: You are generalising 2 general problem as a base for N general problem.

Here is the problem with that: 2, 3 general problems are proven to never reach a proper solution. This is because each of them have no way of verifying who is right. However, this changes when the number of generals in question is 4 or more. As long as the number of honest nodes is greater than faulty, the honest nodes will be able to reach consensus. The above condition is a very important property that makes a consensus algorithm successful.

Paxos or any other algorithm will have freedom from inconsistency if # of honest nodes > faulty.

When there are only 3 nodes in the network, it does not matter whether there are 2 honest nodes (which is greater than 1), the network would not be able to reach consensus until every node is honest.

I am unsure about what you are asking for in the secondary question pertaining to the pseudocode but if you want to know how a 4 node network with 3 honest nodes would verify consistency of data and reach a consensus I can elaborate on this.

Either way, an algorithm would only be able to have "freedom from inconsistency" if there are strictly more than 3 nodes in the network AND if # of honest nodes > # of faulty nodes. Satoshi mentions this in his paper on Bitcoin network.

Upvotes: 0

kjw0188
kjw0188

Reputation: 3685

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.

Upvotes: 1

Keith Randall
Keith Randall

Reputation: 23265

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.

Upvotes: 3

Related Questions