

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?

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...


CAPL: consistency, availability, partition tolerance, latency

Paxos sacrifices latency


Incorrect, paxos sacrifices availability. Paxos is consistent but does not necessarily ever terminate.

