Software engineers love Paxos because it takes something very complex (a distributed system) and makes it equivalent to working with a single machine: you only ever talk to the leader. It gives you redundancy at the expense of performance.
Paxos is used to achieve something called Strong Consistency, where each node sees the same message in the same order. If you think of each node as a deterministic state machine, they are guaranteed to end up in the same state after responding to the same sequence of messages. It's nice and intuitive, but requiring global synchronization on every write is terrible for performance.
Other consistency schemes exist. A popular one is Eventual Consistency, where writes are made immediately at any node (not just the leader) and the system is expected to synchronize in the background and "converge" to the same state. However, this can result in merge conflicts: if you're editing a document in collaboration with other users, what if you edit a word in a paragraph while another user deletes that entire paragraph? Does the system resolve this automatically, or require user assistance? The answer to this question varies according to system requirements. I think most HN users have experienced the joys of resolving merge conflicts.
A newer model is something called Strong Eventual Consistency, which is similar to Eventual Consistency but merge conflicts are impossible by design: every update to the system must be commutative, associative, and idempotent with other updates. It is not always possible to design your system this way. These systems are implemented with Conflict-Free Replicated Data Types (or ad-hoc equivalents) and have excellent liveness/throughput/performance characteristics compared to Strong Consistency.
CRDTs are not as simple as Paxos. You're forced out of the cozy one-system world and your system must deal with two nodes concurrently holding different values. For most applications, magic Paxos dust is all you need. For others, CRDTs are an excellent tool.
I strongly suggest Shapiro's paper[0] on CRDTs. In a nutshell, the only really problematic data type are sequences such as arrays or strings. There are some specialized approaches specifically for those, and you can always fall back on a LWW conflict resolution.
In general, I like to think of Paxos as an approach that uses LWW for all value types.
Shapiro's name is on about seven different CRDT papers :) it makes citations difficult for the Wikipedia article. Personal opinion, this[0] 2011 paper is probably the best one to read, where Shapiro's and Baquero's teams finally joined forces and put out a good comprehensive paper on the subject. The one you linked focuses a bit too heavily on TreeDoc in lieu of good treatment of CRDT theory. Their survey of known CRDTs[1] is also worth reading.
IMHO 'Eventual consistency' and related 'consistencies' are not really giving a consistent state, as they're more about a promise that the system will reach a consistent state 'eventually', but when that happens is unknown: in a volatile database, the system could never reach a consistent state, due to the lack of linearizability. See: http://hackingdistributed.com/2013/03/23/consistency-alphabe...
Wow! Great blog post. I've been looking for something along these lines for a while. The author is correct that Wikipedia's coverage of consistency is difficult to follow, and I don't yet have a deep enough understanding to contribute.
Paxos is used to achieve something called Strong Consistency, where each node sees the same message in the same order. If you think of each node as a deterministic state machine, they are guaranteed to end up in the same state after responding to the same sequence of messages. It's nice and intuitive, but requiring global synchronization on every write is terrible for performance.
Other consistency schemes exist. A popular one is Eventual Consistency, where writes are made immediately at any node (not just the leader) and the system is expected to synchronize in the background and "converge" to the same state. However, this can result in merge conflicts: if you're editing a document in collaboration with other users, what if you edit a word in a paragraph while another user deletes that entire paragraph? Does the system resolve this automatically, or require user assistance? The answer to this question varies according to system requirements. I think most HN users have experienced the joys of resolving merge conflicts.
A newer model is something called Strong Eventual Consistency, which is similar to Eventual Consistency but merge conflicts are impossible by design: every update to the system must be commutative, associative, and idempotent with other updates. It is not always possible to design your system this way. These systems are implemented with Conflict-Free Replicated Data Types (or ad-hoc equivalents) and have excellent liveness/throughput/performance characteristics compared to Strong Consistency.
CRDTs are not as simple as Paxos. You're forced out of the cozy one-system world and your system must deal with two nodes concurrently holding different values. For most applications, magic Paxos dust is all you need. For others, CRDTs are an excellent tool.