Scalable distributed b-tree

Import thing to note here is that partition tolerance here means tolerance to network partitions. As in, tolerating a situation where a link between datacenters/racks in a datacenters goes down and the instance becomes partitioned away. Allowing the tables to be partitioned doesn't require tolerance to network partitioning.

Amazon Dynamo (and various open source datastores which borrow its infrastructure- Voldemort, Dynomite, Cassandra) is a classical example of a partition tolerant datastore: rather than using two phase commit at write time (meaning writes could fail if the cohorts and the coordinator are separated) it uses vector clocks for read-time reconciliation.

Not sure why I put paradox instead of conjecture there, but a quick answer to the "what is it" query that does not involve reading papers is that for a distributed system at any point in time you can only have two of consistency, availability, or partition-tolerance. "At any point in time" is a key item there, as can change the two characteristics chosen as the DB goes through its various states or at different layers in the transaction.

OTOH, saying partition-tolerance is unimportant is only partially-true if your db is only going to run on a single lan. This is often the case (i.e. basically saying that "distributed" is another word for "cluster") but if your db is going to run across a wan then sacrificing partition-tolerance can have unpleasant consequences. I do a lot of work in Erlang and its built-in distributed db (like the language itself) was designed to run in a phone switch among SBCs and blades that shared a common backplane. In this case a partition meant that something extremely bad was happening and graceful shutdown/failure in the face of a partition was a good choice. Now that a lot of us are using these tools out in the wilds of the internet we are discovering that sacrificing partition-tolerance has some unpleasant side-effects too: running mnesia across EC2 instances, for example, is not a trivial undertaking because you need to deal with inevitable network problems by shutting down auto-rejoin features of the db and effectively turn off availability for a short period during the rejoin.