The SNOW Theorem Revisited
share
In the paper titled "The SNOW Theorem" the authors proposed four desirable properties in transaction processing systems for achieving low-latency of READ transactions, with asynchronous and reliable communications, and referred to them collectively as the SNOW properties: The underlying properties, in the context of an execution, are (i) strict serializability (S) property where READ and WRITE transactions seem to occur atomically, (ii) non-blocking (N) property implies for read operations, (iii) one version and one round (O) property, where reads operations completes in one-round of client-server communication and only one version of the object value is sent, and (iv) concurrent WRITE transactions (W) property, which means WRITE transactions can occur. Then they argued that it is impossible to implement all the four properties, in the same system, even with at least three clients. They referred to their result as the SNOW theorem, and they posed the two-client setting as an open question. Here we revisit the results of the work and present several new results. In our first result, we resolve the two-client scenario: We prove that even with two clients, without client-to-client messaging, it is impossible to design an transaction processing system which satisfies the SNOW properties. Second, we provide a rigorous proof of the SNOW theorem for systems with at least three clients, i.e., we show that it is impossible to implement a transaction processing system, consisting of at least three clients, even with client-to-client messaging, that satisfies the SNOW properties. Next we derive a useful property for executions of algorithms that implement objects of data types considered in our work that helps us show the S property of algorithms presented in the paper. Then we present two new algorithms that satisfies S, N, W and wreaked versions O property.
READ FULL TEXT