4 ms·

Not quite. What I'm saying is that a dropped packet or a failed node are not partitions as far as the CAP theorem is considered. A distributed system is consi

by dadkins 16y ago

Not quite. What I'm saying is that a dropped packet or a failed node are not partitions as far as the CAP theorem is considered. A distributed system is considered available if "every request received by a non-failing node [results] in a response." It does not mean you cannot retransmit or retry. Similarly, the consistency guarantee only requires that there exist a total order on operations. Failures are ok, as we're allowed to retransmit, retry, and otherwise tolerate faults. There is no inconsistency, nor is anything eventual. My point is that a "temporary" partition is just a fault, and as long as the fault is shorter than the allowed response time of the system, it doesn't make a difference.

allertonm 16y ago
Yes, a system is available if one node doesn't respond and you can contact another. But that node will be unable to guarantee consistency. If a node you can contact is required to guarantee consistency, there will be some times that it will have to refuse your request because other nodes are not contactable. The author's point was that in any distributed system there is a non-zero probability of a network failure. While both clients and server nodes can retry connections, there is a non-zero probability that the problem will persist longer than your "availability agreement" allows. In that case, you have a choice - return potentially inconstent data or refuse the request. What you seem to be arguing is that the probabilities of failure - in particular of repeated failure - while non-zero, are effectively zero. The author would disagree (as they point out, the probabilities combine exponentially as the number of nodes increase.) I think he's right and that you are wrong.
- dadkins 16y ago
  Paxos is the quintessential example of a highly available, consistent system. It is available as long as more than half of the nodes are up and able to communicate with each other. It remains consistent, regardless of the failure pattern. You really do only have to worry about a true network partition. This isn't a probabilistic argument in any sense.
  - allertonm 16y ago
    As you have yourself pointed out, Paxos will in some cases (when less than half the nodes are up) become unavailable, but remain consistent in all cases where it is available. So it is tolerant of partition and it sacrifices availability in favour of consistency. So it is CP, not CA.
    - dadkins 16y ago
      Of course it will become either unavailable or inconsistent (or both) during a network partition. That's the essence of the CAP theorem. But what does it mean to tolerate a partition? As if the system has a choice? Any CA system is claiming to be consistent and available as long as the network doesn't partition. That's the strongest statement you can make under the CAP theorem, and Paxos certainly falls in that camp. My problem with the original article was that it claimed that any individual network or node failure was a partition affecting the consistency or availability of the system. Paxos is a clear counterexample to that, as it tolerates a lot more than that without sacrificing consistency or availability. Once the network actually partitions (or half the nodes become unreachable), then you are correct. The CAP theorem comes into play again and we must sacrifice either C or A, and Paxos chooses A.
    - tbrownaw 16y ago
      * it never becomes inconsistent (C) * it always returns either success or failure (A) * sufficiently severe partitions kill it dead (!P) Or does any system subject to hardware or power failure fail to count as "available"?
HenryR 16y ago
No, dropped packets are partitions. They really are. A partitionable network is modelled as one which may fail to deliver any subset of sent messages between nodes. The Gilbert and Lynch paper makes this explicit. The consistency guarantee requires that RW histories are compatible with some sequentially consistent history on a non-concurrent RW register. Defining a total order on operations is sufficient, I believe, but not necessary (does it matter what order two consecutive reads happened in?).
- dadkins 16y ago
  How do you explain Paxos, then? How does a dropped packet prevent the system from responding to queries? How about if I broadcast every response 10 times to everyone I know? How many packets must be dropped for the system to be considered unavailable?
  - HenryR 16y ago
    Depends on the protocol, in general. Paxos is, fundamentally, a quorum-based system that deals with reordering of messages. It sacrifices liveness for correctness - if the proposer does not hear back from a majority of nodes (in the case of, e.g. a partition), the protocol will not complete (availability is sacrificed). My point is not that there is a 'vital packet' in every protocol, the omission of which will cause either a lack of availability or consistency (although I can certainly design protocols that way!) - it's that for every protocol there is a network partition which causes it to be either unavailable or inconsistent. That network partition might be dropping ten messages, or just one. Retransmitting would make sense, but in real life message failures are often highly temporally correlated :( The proof of this, by the way, is in a very famous paper by Fischer, Lynch and Patterson called "The Impossibility of Distributed Consensus With One Faulty Process". One take away is that one slow-running process can take down any protocol. It may take a few missed messages, but only a single node...
    - ithkuil 16y ago
      CAPL: consistency, availability, partition tolerance, latency Paxos sacrifices latency

by dadkins 16y ago

allertonm 16y ago

Yes, a system is available if one node doesn't respond and you can contact another. But that node will be unable to guarantee consistency. If a node you can contact is required to guarantee consistency, there will be some times that it will have to refuse your request because other nodes are not contactable. The author's point was that in any distributed system there is a non-zero probability of a network failure. While both clients and server nodes can retry connections, there is a non-zero probability that the problem will persist longer than your "availability agreement" allows. In that case, you have a choice - return potentially inconstent data or refuse the request. What you seem to be arguing is that the probabilities of failure - in particular of repeated failure - while non-zero, are effectively zero. The author would disagree (as they point out, the probabilities combine exponentially as the number of nodes increase.) I think he's right and that you are wrong.

dadkins 16y ago
Paxos is the quintessential example of a highly available, consistent system. It is available as long as more than half of the nodes are up and able to communicate with each other. It remains consistent, regardless of the failure pattern. You really do only have to worry about a true network partition. This isn't a probabilistic argument in any sense.
- allertonm 16y ago
  As you have yourself pointed out, Paxos will in some cases (when less than half the nodes are up) become unavailable, but remain consistent in all cases where it is available. So it is tolerant of partition and it sacrifices availability in favour of consistency. So it is CP, not CA.
  - dadkins 16y ago
    Of course it will become either unavailable or inconsistent (or both) during a network partition. That's the essence of the CAP theorem. But what does it mean to tolerate a partition? As if the system has a choice? Any CA system is claiming to be consistent and available as long as the network doesn't partition. That's the strongest statement you can make under the CAP theorem, and Paxos certainly falls in that camp. My problem with the original article was that it claimed that any individual network or node failure was a partition affecting the consistency or availability of the system. Paxos is a clear counterexample to that, as it tolerates a lot more than that without sacrificing consistency or availability. Once the network actually partitions (or half the nodes become unreachable), then you are correct. The CAP theorem comes into play again and we must sacrifice either C or A, and Paxos chooses A.
  - tbrownaw 16y ago
    * it never becomes inconsistent (C) * it always returns either success or failure (A) * sufficiently severe partitions kill it dead (!P) Or does any system subject to hardware or power failure fail to count as "available"?

HenryR 16y ago

No, dropped packets are partitions. They really are. A partitionable network is modelled as one which may fail to deliver any subset of sent messages between nodes. The Gilbert and Lynch paper makes this explicit. The consistency guarantee requires that RW histories are compatible with some sequentially consistent history on a non-concurrent RW register. Defining a total order on operations is sufficient, I believe, but not necessary (does it matter what order two consecutive reads happened in?).

dadkins 16y ago
How do you explain Paxos, then? How does a dropped packet prevent the system from responding to queries? How about if I broadcast every response 10 times to everyone I know? How many packets must be dropped for the system to be considered unavailable?
- HenryR 16y ago
  Depends on the protocol, in general. Paxos is, fundamentally, a quorum-based system that deals with reordering of messages. It sacrifices liveness for correctness - if the proposer does not hear back from a majority of nodes (in the case of, e.g. a partition), the protocol will not complete (availability is sacrificed). My point is not that there is a 'vital packet' in every protocol, the omission of which will cause either a lack of availability or consistency (although I can certainly design protocols that way!) - it's that for every protocol there is a network partition which causes it to be either unavailable or inconsistent. That network partition might be dropping ten messages, or just one. Retransmitting would make sense, but in real life message failures are often highly temporally correlated :( The proof of this, by the way, is in a very famous paper by Fischer, Lynch and Patterson called "The Impossibility of Distributed Consensus With One Faulty Process". One take away is that one slow-running process can take down any protocol. It may take a few missed messages, but only a single node...
  - ithkuil 16y ago
    CAPL: consistency, availability, partition tolerance, latency Paxos sacrifices latency