Practical Sequential Consistency Checking

This artefact includes an implementation of the Sequential Consistency checking algorithms covered in the paper, an archive of operation histories obtained from a Couchbase cluster, and a Docker setup to replicate this. Abstract. Sequential Consistency (SC) is a fundamental correctness model for concurrent objects in multi-threaded and distributed systems. Testing such systems requires high-concurrency workloads that produce execution traces, which must then be validated by a decision algorithm. However, as the number of operations and concurrency levels increase, validation becomes a significant computational bottleneck. This paper introduces an optimised recursive decision algorithm using heuristics tailored for register read/write workloads. Experimental results, using both synthetic benchmarks and traces from a commercial distributed database, demonstrate that this approach is a practical and scalable solution for testing the SC conformance of industrial systems.