TY - GEN
T1 - SNOW revisited
T2 - 35th IEEE International Parallel and Distributed Processing Symposium, IPDPS 2021
AU - Konwar, Kishori M.
AU - Lloyd, Wyatt
AU - Lu, Haonan
AU - Lynch, Nancy
N1 - Publisher Copyright:
© 2021 IEEE.
PY - 2021/5
Y1 - 2021/5
N2 - READ transactions that read data distributed across servers dominate the workloads of real-world distributed storage systems. The SNOW Theorem [13] stated that ideal READ transactions that have optimal latency and the strongest guarantees - i.e., 'SNOW' READ transactions-are impossible in one specific setting that requires three or more clients: at least two readers and one writer. However, it left many open questions. We close all of these open questions with new impossibility results and new algorithms. First, we prove rigorously the result from [13] saying that it is impossible to have a READ transactions system that satisfies SNOW properties with three or more clients. The insight we gained from this proof led to teasing out the implicit assumptions that are required to state the results and also, resolving the open question regarding the possibility of SNOW with two clients. We show that it is possible to design an algorithm, where SNOW is possible in a multi-writer, single-reader (MWSR) setting when a client can send messages to other clients; on the other hand, we prove it is impossible to implement SNOW in a multi-writer, single-reader (MWSR) setting-which is more general than the two-client setting-when client-to-client communication is disallowed. We also correct the previous claim in [13] that incorrectly identified one existing system, Eiger [12], as supporting the strongest guarantees (SW) and whose read-only transactions had bounded latency. Thus, there were no previous algorithms that provided the strongest guarantees and had bounded latency. Finally, we introduce the first two algorithms to provide the strongest guarantees with bounded latency.
AB - READ transactions that read data distributed across servers dominate the workloads of real-world distributed storage systems. The SNOW Theorem [13] stated that ideal READ transactions that have optimal latency and the strongest guarantees - i.e., 'SNOW' READ transactions-are impossible in one specific setting that requires three or more clients: at least two readers and one writer. However, it left many open questions. We close all of these open questions with new impossibility results and new algorithms. First, we prove rigorously the result from [13] saying that it is impossible to have a READ transactions system that satisfies SNOW properties with three or more clients. The insight we gained from this proof led to teasing out the implicit assumptions that are required to state the results and also, resolving the open question regarding the possibility of SNOW with two clients. We show that it is possible to design an algorithm, where SNOW is possible in a multi-writer, single-reader (MWSR) setting when a client can send messages to other clients; on the other hand, we prove it is impossible to implement SNOW in a multi-writer, single-reader (MWSR) setting-which is more general than the two-client setting-when client-to-client communication is disallowed. We also correct the previous claim in [13] that incorrectly identified one existing system, Eiger [12], as supporting the strongest guarantees (SW) and whose read-only transactions had bounded latency. Thus, there were no previous algorithms that provided the strongest guarantees and had bounded latency. Finally, we introduce the first two algorithms to provide the strongest guarantees with bounded latency.
KW - Distributed transactions
KW - Strict-serializability
UR - http://www.scopus.com/inward/record.url?scp=85113426463&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85113426463&partnerID=8YFLogxK
U2 - 10.1109/IPDPS49936.2021.00101
DO - 10.1109/IPDPS49936.2021.00101
M3 - Conference contribution
AN - SCOPUS:85113426463
T3 - Proceedings - 2021 IEEE 35th International Parallel and Distributed Processing Symposium, IPDPS 2021
SP - 922
EP - 931
BT - Proceedings - 2021 IEEE 35th International Parallel and Distributed Processing Symposium, IPDPS 2021
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 17 May 2021 through 21 May 2021
ER -