Client-centric consistency formalization and verification for system with large-scale distributed data storage

摘要

Customized consistency is necessary in systems with large-scale distributed data storage, which have to make a tradeoff between consistency and performance. Client-centric consistency is intuitive for applications to specify their consistency requirements, but the properties of system implementations that satisfy client-centric consistency are not clear. So constraints on implementation and costs in performance are not known. In this paper, we formally define the four client-centric consistencies and their basis, i.e. eventual consistency, borrowing the framework from the theory of database concurrency control. Based on their definitions, we prove relations among these consistencies. Such relations imply how the implementation of one consistency can be made upon another. Besides, with these formal definitions, we can make simple consistency verification on system implementations.