Checking Causal Consistency of Distributed Databases
Preprint
Abstract
The CAP Theorem shows that (strong) Consistency, Availability, and Partition tolerance are impossible to be ensured together. Causal consistency is one of the weak consistency models that can be implemented to ensure availability and partition tolerance in distributed systems. In this work, we propose a tool to check automatically the conformance of distributed/concurrent systems executions to causal consistency models. Our approach consists in reducing the problem of checking if an execution is causally consistent to solving Datalog queries. The reduction is based on complete characterizations of the executions violating causal consistency in terms of the existence of cycles in suitably defined relations between the operations occurring in these executions. We have implemented the reduction in a testing tool for distributed databases, and carried out several experiments on real case studies, showing the efficiency of the suggested approach.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Boosting Sequential Consistency Checking Using Saturation2020
- Checking Causal Consistency of Distributed DatabasesLecture Notes in Computer Science, 2019
- Parameterized verification through view abstractionInternational Journal on Software Tools for Technology Transfer, 2015
- SwiftCloud: Fault-Tolerant Geo-Replication Integrated all the Way to the Client Machine2014
- Don't settle for eventual2011
- Line-up2010
- Verifying sequential consistency on shared-memory multiprocessors by model checkingIEEE Transactions on Parallel and Distributed Systems, 2003
- Causal memory: definitions, implementation, and programmingDistributed Computing, 1995
- Testing and Verifying Concurrent ObjectsJournal of Parallel and Distributed Computing, 1993
- How to Make a Multiprocessor Computer That Correctly Executes Multiprocess ProgramsIEEE Transactions on Computers, 1979