3 ms·

If the leader fails, the next leader needs to know the values the acceptors have already accepted in order to propagate the previously chosen value, if any. I a

If the leader fails, the next leader needs to know the values the acceptors have already accepted in order to propagate the previously chosen value, if any. I assume this happens in your election phase. Since we only want to talk to a majority of acceptors during the election, we need a way to order the values proposed by different leaders (ballot number). Without that, we'd need to receive responses from possibly all acceptors, which would break liveness. Once the leader has proposed a value at a ballot number, acceptors need to not accept values from older ballots, otherwise the old leader, having woken up from a nap, could just overwrite the chosen value. So in filling in the not specified portions of your algorithm in the simplest way possible to make it work, we've just described paxos. I will have to read the Chang-Maxemchuk paper, I have not heard of that before.

vyodaiken 7y ago
You don't need Paxos at all. In fact, you should read Liskov's paper https://www.yodaiken.com/2018/07/16/practical-uses-of-synchronized-clocks-liskov/ https://www.yodaiken.com/2018/07/16/practical-uses-of-synchr... The key is to decide whether timeouts work in your network. If timeouts don't work and you don't have some reliable message protocol, then nothing works. If timeouts do work, then a completely simple obvious brute force algorithm works. In this algorithm, we have leader/coordinator election. The leader then polls the acceptors for the highest sequence number of a committed message and recovers all missing messages. Then the leader starts sending new messages - increasing the same sequence number. The old leader, if it recovers should know that its lease as leader has timed out, but if it does not it cannot get acks from a majority of acceptors for a new message because a majority have signed on to the new leader. There is no "value" competition - only a competition for the id of the new leader during leader election. We don't need Paxos at all.

vyodaiken 7y ago

You don't need Paxos at all. In fact, you should read Liskov's paper https://www.yodaiken.com/2018/07/16/practical-uses-of-synchronized-clocks-liskov/ https://www.yodaiken.com/2018/07/16/practical-uses-of-synchr... The key is to decide whether timeouts work in your network. If timeouts don't work and you don't have some reliable message protocol, then nothing works. If timeouts do work, then a completely simple obvious brute force algorithm works. In this algorithm, we have leader/coordinator election. The leader then polls the acceptors for the highest sequence number of a committed message and recovers all missing messages. Then the leader starts sending new messages - increasing the same sequence number. The old leader, if it recovers should know that its lease as leader has timed out, but if it does not it cannot get acks from a majority of acceptors for a new message because a majority have signed on to the new leader. There is no "value" competition - only a competition for the id of the new leader during leader election. We don't need Paxos at all.