11/25 Discussion for: Leslie Lamport, “Paxos Made Simple” (2001)

[katelynstone13]

Scribes: @andavid0 @ap9272 @Rajhi1988m @ravina-gelda @esmaeil-mirvakili

[andavid0]

@lkuper Our first draft is ready for review.

[lkuper]

Q1: Looks good. This one is mostly a matter of individual interpretation, but I think you called out some of the key things (no diagrams, confusing extended analogy, etc.).

Q2:

• "The knowledge of disjoint sets should be known in advance." -- I would rephrase this as "The knowledge of the mechanism used to keep the sets disjoint should be known in advance."
• "they must be a “less than” operation" -- it's not that proposal IDs must be a less-than operation, it's that a less-than operation must be defined on them. Given any two proposal IDs, we need to be able to compare them and see which is "bigger". If we were writing Java and defining a class for proposal IDs, we'd say that we need it to implement the Comparable interface. In math terms, we'd need the set of proposal IDs to be a totally ordered set.
• I'd honestly leave out the prime number example because it's a little too complicated. The other examples are fine.

Q3: Several issues here...

• "If the learner fails to learn a decision" is kind of a funny way to put it, because the failure may not be the learner's fault. Also, how would the learner know that there has been a decision that it hasn't learned about? All the learner can do is have a timeout periodically expire, and at that point, try to force a decision / query for a previous decision by putting in its own proposal.
• "This would increase the latency because the majority has not accepted the value" -- still confused here; are we talking about a situation where a decision has been made and the learner just hasn't found out yet, or a situation where a decision hasn't been made?
• "However, the probability of one particular process determining the majority of the processes should not be that high" -- Not sure what this means. Determining what?
• "If a machine fails" -- I think this should say "If an acceptor fails"
• "In the case of 3 acceptors, if one fails, then a proposer’s proposal can’t get accepted by a majority of the acceptors." -- Why not? 2 of 3 is still a majority.
• "Until consensus is reached, the algorithm cannot proceed" -- not sure what "proceed" means here. As we've seen, the algorithm can keep running forever in a "dueling proposers" scenario, even though consensus is never reached.
• "It is harder to achieve a majority with failed systems." -- what does "failed systems" mean here, specifically?

The main point I'm hoping you reflect on with this question is just that, no matter what, strong consistency will sometimes be relatively slow for clients.

Also, I realized that something in the paper might not be clear. The quote from the paper says:

failure of an acceptor could make it impossible to know whether or not a majority had accepted a particular proposal I think what this means is that failure of a particular acceptor in a majority that accepted a proposal (say, if we have acceptors A, B, and C, proposal number 5 was accepted by A and B, and thenn A fails) then we can't learn that the majority acccepted proposal 5. However, at that point B and C are still up, so someone can still issue a new proposal with a higher number and have it accepted by a majority.

[andavid0]

@lkuper The edited version is now posted on the Wiki