Complete CALM: A Coordination Criterion for Specifications
read the original abstract
The CALM theorem connects coordination-freedom to monotonicity, but is tied to relational transducers and set-inclusion growth. We generalize it to arbitrary concurrent specifications. A specification maps execution histories to outcome sets under a declared refinement order; we prove it admits coordination-free implementation if and only if its outcomes are monotone (\emph{Complete CALM}). The criterion subsumes CALM, CRDTs, I-confluence, and HATs as instances, enables verification of proper coordination, and yields a \emph{Complete CAP} companion: a specification admits a consistent, available, partition-tolerant implementation if and only if it is distributed-monotone.
This paper has not been read by Pith yet.
Forward citations
Cited by 2 Pith papers
-
Determination Provenance: From Ambiguity to Algebra
Determination provenance models tuple supports as elements of a commutative semiring under layered resolutions, inducing a filtration that positive relational algebra respects and that unifies isolation levels with ne...
-
When Coordination Is Avoidable: A Monotonicity Analysis of Organizational Tasks
A bridge theorem links Thompson's interdependence types to monotonicity, finding 74% of APQC workflows and 42% of O*NET tasks monotonic and thus coordination-avoidable for correctness.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.