4 ms·

Your view that Paxos is an algorithm for read-modify-write is a really deep insight. Once you adopt this point of view, things like Raft are just RMW updates o

Your view that Paxos is an algorithm for read-modify-write is a really deep insight. Once you adopt this point of view, things like Raft are just RMW updates of a log. (I like to think of Paxos as the fault-tolerant version of the load-linked/store-conditional pair of instructions.) However, there is a difficulty in expressing exactly what RMW-Paxos does, because it may end up "modifying" a value that was never "committed". For example, assume that I have three acceptors storing a replicated counter. The proposer executes phase-1, increments the value received from the acceptor with the highest ballot, and sends the value to all acceptors in phase-2. Consider now an execution where all acceptors initially hold 0. The proposer manages to store a new value 1 in one acceptor, and then crashes. Thus, 1 was not committed and a reader may conclude that the consensus value is still 0. Now a new proposer arrives, receives (1, 0, 0) from the three acceptors, chooses 1 as the newest value, and writes (2, 2, 2) to all acceptors. Thus "2" is now committed, and the commit of the "2" retroactively commits the "1". Thus, the condition for being committed is no longer "there exists a phase-2 quorum ...", but it is more complicated and depends on future history. I have verified with TLA+ that this algorithm does indeed implement an atomic read-modify-write operation, but only under a complicated notion of being "committed" that boils down to either having a phase-2 quorum, or one of the successor operations having a phase-2 quorum. Did you ever figure out a simpler way to say this?

iambvk 5y ago
Instead of Read-Modify-Write, I like to think of it as Read/Determine/Write cycle. A note worthy point is that, Paxos actually expects proposers to drop their value and carry-forward someone-else's value to complete the consensus. This is typically not an intended behavior from client's point of view, but proposers role is to form the consensus, not push their value. Read phase is basically understanding if there is any value that could've been chosen when F nodes are unavailable. Determine phase is to choose to carry-forward any value (if-any) from the Read phase or use the new value from the client. Write phase is to actually ask majority of the acceptors to save the value selected in the Determine phase.
- MatteoFrigo 5y ago
  You are totally correct that in Paxos the proposer is supposed to "carry-forward" the value proposed by somebody else. In this view, which is how everybody understands Paxos, Paxos is an algorithm for consensus. However, the proposer can also modify the value proposed by somebody else, and it turns out that this is a perfectly valid algorithm for implementing a distributed read-modify-write. This variant does more than just consensus---it basically behaves like a fault-tolerant memory with an atomic update operation (think compare-and-swap or load-linked/store-conditional). In his blog post, GP also mentions that paxos is a read-modify-write transaction, but perhaps I read too much into what he is saying. Either way, this RMW variant is correct, I have verified it exhaustively with TLA+, and it is used in a few production systems that I have implemented. The difficulty is now to say exactly what this RMW variant does. I was hoping that GP (or anybody else) may have some insights.
  - grogers 5y ago
    In case anyone wants to read more about the RMW variant, this is called CASPaxos: https://arxiv.org/abs/1802.07000 https://arxiv.org/abs/1802.07000 I first learned about this as a project called gryadka and I had trouble believing that extending Paxos from consensus (write once) to a full linearizable register worked until model checking a TLA+ spec for it that I wrote.

iambvk 5y ago

Instead of Read-Modify-Write, I like to think of it as Read/Determine/Write cycle. A note worthy point is that, Paxos actually expects proposers to drop their value and carry-forward someone-else's value to complete the consensus. This is typically not an intended behavior from client's point of view, but proposers role is to form the consensus, not push their value. Read phase is basically understanding if there is any value that could've been chosen when F nodes are unavailable. Determine phase is to choose to carry-forward any value (if-any) from the Read phase or use the new value from the client. Write phase is to actually ask majority of the acceptors to save the value selected in the Determine phase.

MatteoFrigo 5y ago
You are totally correct that in Paxos the proposer is supposed to "carry-forward" the value proposed by somebody else. In this view, which is how everybody understands Paxos, Paxos is an algorithm for consensus. However, the proposer can also modify the value proposed by somebody else, and it turns out that this is a perfectly valid algorithm for implementing a distributed read-modify-write. This variant does more than just consensus---it basically behaves like a fault-tolerant memory with an atomic update operation (think compare-and-swap or load-linked/store-conditional). In his blog post, GP also mentions that paxos is a read-modify-write transaction, but perhaps I read too much into what he is saying. Either way, this RMW variant is correct, I have verified it exhaustively with TLA+, and it is used in a few production systems that I have implemented. The difficulty is now to say exactly what this RMW variant does. I was hoping that GP (or anybody else) may have some insights.
- grogers 5y ago
  In case anyone wants to read more about the RMW variant, this is called CASPaxos: https://arxiv.org/abs/1802.07000 https://arxiv.org/abs/1802.07000 I first learned about this as a project called gryadka and I had trouble believing that extending Paxos from consensus (write once) to a full linearizable register worked until model checking a TLA+ spec for it that I wrote.