4 ms·

Page 7 talks about the conditions under which a liveness condition can be satisfied. What about that is wrong? If you mean paxos is wrong because it can't guara

Page 7 talks about the conditions under which a liveness condition can be satisfied. What about that is wrong? If you mean paxos is wrong because it can't guarantee progress, then sure it's wrong (and because of FLP, all consensus algorithms are)

vyodaiken 7y ago
Paxos livelocks (doesn’t work). So Lamport suggests electing a coordinator via timeouts(since flp is a joke). But if you can elect via timeouts you don’t need paxos at all. QED The really annoying thing is that "Paxos Made Simple" begins by outlining the algorithm as a solution for a completely async network (unlike real networks) but then towards the end, just blows that off and falls back on timeouts. But if you have timeouts there are far simpler and more efficient solutions. FWIW: FLP is a silly "theorem" that says "if you can't tell the difference between a system that has crashed and one that is slow - why then you can't tell the difference."
- ahelwer 7y ago
  Paxos livelocks in a very unstable state which requires multiple independent nodes to sent specific messages at specific times. If you add random intervals between retries, the probability of staying in a livelocked state quickly grows astonishingly low.
  - vyodaiken 7y ago
    I wrote a little simulation. Paxos rarely gets stuck with a small number of proposers/acceptors, but jams up solid once you get to, I forget, 10 or 20. Here it is: https://www.yodaiken.com/wp-content/uploads/2016/10/paxos.ptpx_.ppxt_.png https://www.yodaiken.com/wp-content/uploads/2016/10/paxos.pt... Embarrassingly badly written Lua code for the simulator https://github.com/yodaikenv/consensus https://github.com/yodaikenv/consensus The key to me is that once you accept the need for leader election, you have much simpler alternatives and can toss away the rest of paxos.
    - ahelwer 7y ago
      This is authentically a very interesting simulation and I would be interesting to see a writeup if you have one. I will say that you only have multiple proposers if the proposers cannot talk to one another, as otherwise they would be silenced by any simple leader election protocol (heartbeats + node rank, etc.) It's true that the leader election protocol is not part of paxos per se but all implementations will have one, and the protocol livelocks in the unusual case where there's an enduring network partition and the multiple proposers are sending messages with specific timing. Edit: I took a look at your post[0] and it is interesting. I'll take a look at CM. [0] https://www.yodaiken.com/papers-and-talks/distributed-consensus-paxos-raft-etc/ https://www.yodaiken.com/papers-and-talks/distributed-consen...
- grogers 7y ago
  What is the simpler and more efficient solution than paxos for consensus that uses timeouts?
  - vyodaiken 7y ago
    stage 1: elect a single coordinator (which you have to do with paxos anyways) stage 2: the coordinator sends each message over and over until it has accepts from 51% of acceptors or it times out and starts a reformulation of the acceptor set If an acceptor does not receive a message from the coordinator over a sufficient period,it times out and tries to trigger a new coordinator election Coordinator election: try for t time units to get a majority of acceptors to accept your proposal to be coordinator. give up on timeout or notification that there is a running coordinator. This is the simplest method and not the most efficienct, but it is both live and safe. Chang/Maxemchuk propose to make stage 2 more efficient that acceptors be arranged in a cycle and messages from the coordinator be numbered sequentially. Then each acceptor takes a turn to broadcast its accept but only does it if it has seen all prior (lower numbered) messages and their accept message responses. on each cycle completion, the coordinator can commit the first message in the cycle.
    - grogers 7y ago
      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

vyodaiken 7y ago

Paxos livelocks (doesn’t work). So Lamport suggests electing a coordinator via timeouts(since flp is a joke). But if you can elect via timeouts you don’t need paxos at all. QED The really annoying thing is that "Paxos Made Simple" begins by outlining the algorithm as a solution for a completely async network (unlike real networks) but then towards the end, just blows that off and falls back on timeouts. But if you have timeouts there are far simpler and more efficient solutions. FWIW: FLP is a silly "theorem" that says "if you can't tell the difference between a system that has crashed and one that is slow - why then you can't tell the difference."

ahelwer 7y ago
Paxos livelocks in a very unstable state which requires multiple independent nodes to sent specific messages at specific times. If you add random intervals between retries, the probability of staying in a livelocked state quickly grows astonishingly low.
- vyodaiken 7y ago
  I wrote a little simulation. Paxos rarely gets stuck with a small number of proposers/acceptors, but jams up solid once you get to, I forget, 10 or 20. Here it is: https://www.yodaiken.com/wp-content/uploads/2016/10/paxos.ptpx_.ppxt_.png https://www.yodaiken.com/wp-content/uploads/2016/10/paxos.pt... Embarrassingly badly written Lua code for the simulator https://github.com/yodaikenv/consensus https://github.com/yodaikenv/consensus The key to me is that once you accept the need for leader election, you have much simpler alternatives and can toss away the rest of paxos.
  - ahelwer 7y ago
    This is authentically a very interesting simulation and I would be interesting to see a writeup if you have one. I will say that you only have multiple proposers if the proposers cannot talk to one another, as otherwise they would be silenced by any simple leader election protocol (heartbeats + node rank, etc.) It's true that the leader election protocol is not part of paxos per se but all implementations will have one, and the protocol livelocks in the unusual case where there's an enduring network partition and the multiple proposers are sending messages with specific timing. Edit: I took a look at your post[0] and it is interesting. I'll take a look at CM. [0] https://www.yodaiken.com/papers-and-talks/distributed-consensus-paxos-raft-etc/ https://www.yodaiken.com/papers-and-talks/distributed-consen...
grogers 7y ago
What is the simpler and more efficient solution than paxos for consensus that uses timeouts?
- vyodaiken 7y ago
  stage 1: elect a single coordinator (which you have to do with paxos anyways) stage 2: the coordinator sends each message over and over until it has accepts from 51% of acceptors or it times out and starts a reformulation of the acceptor set If an acceptor does not receive a message from the coordinator over a sufficient period,it times out and tries to trigger a new coordinator election Coordinator election: try for t time units to get a majority of acceptors to accept your proposal to be coordinator. give up on timeout or notification that there is a running coordinator. This is the simplest method and not the most efficienct, but it is both live and safe. Chang/Maxemchuk propose to make stage 2 more efficient that acceptors be arranged in a cycle and messages from the coordinator be numbered sequentially. Then each acceptor takes a turn to broadcast its accept but only does it if it has seen all prior (lower numbered) messages and their accept message responses. on each cycle completion, the coordinator can commit the first message in the cycle.
  - grogers 7y ago
    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