How does a consistent algorithm guarantee consistency?
How does a consensus algorithm like Paxos guarantee security (freedom from inconsistency) "when two generals argue that design algorithms cannot be aligned?"
When I consider the simplest case where two servers can either (1) reliably exchange a number (i.e. both servers end up knowing that the other definitely got a number) or (2) both servers end up with the exchange refused , and do not change their state, it would seem that (like with two generals) a message failure can always occur in such a way as to leave an inconsistency (that is, one server thinks that the other has finished the exchange, but it is not).
So how does Paxos (or whatever) really guarantee "inconsistency freedom"? Is there an explanation in plain language? What is the simplest pseudocode for two servers that make a guaranteed exchange, or completely abandon the exchange on failure?
source to share
The bottom line is Paxos' speculation:
Liveness (C; L): If a value for C was suggested, then eventually student L will learn some value ( if sufficient processors remain unreproducible ).
A bad case for the two-general problem is when messengers are constantly intercepted. “If enough processors remain faulty,” this excludes this possibility.
In other words, if messages are continually dropped, then Paxos is not required (and will not) terminate.
source to share
Paxos doesn't actually solve the 2 generals problem. As stated in the wikipedia article:
In general, the consensus algorithm can make progress using 2F + 1 processors despite the concurrent failure of any F processors.
In a 2 generals problem, 1 node failover means you will need 2*1 + 1 = 3
nodes to handle many failures. The impossibility of the 2-generals problem does not generalize to N generals.
One way to solve the 2 generals problem in the real world is fencing .
source to share
Paxos is a peer-to-peer collaboration algorithm. As noted in other answers, it needs nodes 2F+1
to keep accepting writes on errors F
, which means the cluster sizes 3, 5, 7
can survive failures 1, 2, 3
. Byzantine_Generalstalks about the need for more nodes for cross-validation to weed out misinformation. With standard paxos, you assume that the nodes are not lying or have errors, they all run the same good code, and there are trouble with alarms, or discarded or unreadable messages (like transmission noise) or messages with delay or reordering (like , flickering network links). It works without a global clock because it uses a peer-to-peer method to increment the counter transmitted between nodes.
Initially, you have no leader. Nodes must hear a positive response from most of the nodes listed in the cluster configuration (or DNS) in order to lead. So while you load most of the nodes, they will all chat, but none of them will. When there are enough nodes up, one will time out at random and propose(N)
where N
is an attempt to set the next number in the global sequence and become the leader. All nodes that have not yet heard the higher N
one respond positively (ack). The nodes that hear the highest number will respond in the negative (nack) and go through the highest number they heard. This allows nodes to break the currently highest valueN
... You don't want many nodes to go down at the same time and fight to be the leader, as they just punch it endlessly by making higher bids N
. So getting a leader is a delicate time. Nodes must wait for a random timeout before they offer themselves and retreat if they hear about another potential leader with a large number.
Really numbers, each node uses alternation. For example, it could be N=C*100+X
where C
is the counter and X<100
is the node number. If any node sees another one higher N
than the one it sent to the last one, it can cancel the computation C
, increase it, and then create a new maximum N
. This means that N
it is not sequential (has spaces <100), but is unique for each node and everything N
can be ordered to see the highest.
When a node hears most of the voices, it knows that it is now the leader. We now have the problem of uncommitted work of any previous leader. The previous leader may have just lost the network after hearing that most of the nodes took their last value when they sent commit messages when the network was hanging. There is no evidence that he is dead. Anytime he captures messages, they can arrive and race and beat new messages with the new leader. Therefore, the new leader does not try to ignore or overwrite the work of the last leader: he collaborates and gets the job done. Cooperation and safety of recording racing messages is done using numbersN
and promises. The promise is that the node that accepts the offer will reject all messages with a lower one N
.
When nodes receive any new proposal from a new leader, they respond to the remaining work Vold
from the previous leaders, indicating Nold,Vold
where the Nold
old leader proposal was for the job Vold
. The nodes only need to inform the new manager of any uncommitted work with the highest N
due to a promise to reject lower values. The new leader becomes aware of the highest uncommitted work any node has seen and decides to commit as their first action Vmax
. It first sends this message into a message accept(N,V)
. When most nodes respond to accepted(N)
(unless they have made new promises), the leader knows the job is done. He can then tell all nodes what N
, and they can communicateV
... As soon as it completes any work-in-progress left by the last leader, it will start new work with the client, sending these new values and waiting for confirmation from the majority before informing the client that the work is done. The work will be saved if the leader fails, as the next leader will do the work to complete the commit with any nodes that have not yet mastered the value.
Some of the terminology in this answer may be ambiguous and lead to more questions. I cannot hope that it is enough to convince anyone who immediately understands the complete algorithm. I hope this is enough to make the reader curious about the elegance at the heart of Paxo; peer-to-peer collaboration. The mathematics and formal proof that it really is solid is complex; but the intuition is that if the nodes help each other, it should all become easy eventually. I recommend blogging-blogging as a good source for more details.
source to share