Data Consistency in Transactional Storage Systems: a Centralised Approach
Modern distributed databases weaken data consistency guarantees to allow for faster transaction processing. It poses several challenges: formalising user-observable behaviour; then verifying protocols of databases and reasoning about client applications. We abstract such databases to centralised multi-version key-value stores and client views which provide partial information about such stores. We propose an operational semantics that is parametric in the notion of execution test, which determines if a client with a given view is allowed to commit a transaction. Different execution tests give rise to different consistency models, which are equivalent to the declarative consistency models defined in the literature. Using our semantics, we prove the correctness of distributed protocols and analyse the robustness of simple client applications.
READ FULL TEXT