This looks interesting, but I still can't tell how it relates to the CAP theorem. Are they sacrificing global consistency? Availability? Partition-tolerance? Or do they have a subtle reformulation of these constraints which allows them to "get around" the restrictions imposed by the CAP theorem?

Most of the popular NoSQL solutions were designed to run as large server clusters, possibly distributed across multiple data centers. They're designed to handle such problems as, "Our fiber backbone is down, and our database has split into a 5,000 machine cluster and a 7,000 machine cluster! And it's three days before Christmas!" (This is more or less the problem Amazon's database is designed to survive.)

For any given "NoSQL" database, you want to figure out how they handle this problem: Do they allow the 5,000 and 7,000 node datacenters to become temporarily inconsistent? Do they block writes to the entire database? Do they block writes to the 5,000 node database (because it doesn't have a quorum)?

Any of these options are valid—you just need to know what tradeoffs you're choosing.