On the Scalability of Snapshot Isolation?

Abstract. Many distributed applications require transactions. However, transactional protocols that require strong synchronization are costly in large scale environments. Two properties help with scalability of a trans-actional system: genuine partial replication (GPR), which leverages the intrinsic parallelism of a workload, and snapshot isolation (SI), which decreases the need for synchronization. We show that under standard assumptions (data store accesses are not known in advance, and transac-tions may access arbitrary objects in the data store), it is impossible to have both SI and GPR. Our impossibility result is based on a novel de-composition of SI which proves that, like serializability, SI is expressible on plain histories.