Weaker Forms of Monotonicity for Declarative Networking: a More Fine-grained Answer to the CALM-conjecture

Summary: Introduces a hierarchy of weaker monotonicity notions that exactly correspond to classes of coordination-free computations and provides explicit Datalog fragments (e.g., connected rules except in the final stratum) capturing each class. Characterizes coordination-freeness as absence of any need for global knowledge of other nodes, yielding a fine-grained refinement of the CALM conjecture. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1617
Venue: PODS
Year: 2014
Pagerank: 4.6426494e-05
Overall Rank: 7,822 | 45.59%
DOI: 10.1145/2594538.2594541

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
5,705	Datalog Unchained	2021	PODS	5.3621239e-05
8,215	Parallel-Correctness and Transferability for Conjunctive Queries	2015	PODS	4.5577562e-05
11,159	Distributed Consistency Beyond Queries	2023	PODS	4.1945683e-05
11,315	Decoupled Transactions: Low Tail Latency Online Transactions Atop Jittery Servers	2022	CIDR	4.1945683e-05
11,831	Logical Aspects of Massively Parallel and Distributed Systems	2016	PODS	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 12 of 12 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
778	Declarative Networking: Language, Execution and Optimization	2006	SIGMOD	0.00016791276
989	Relational Transducers for Electronic Commerce	1998	PODS	0.00014814282
1,018	ILOG: Declarative Creation and Manipulation of Object Identifiers	1990	VLDB	0.00014627963
1,110	Parallel Evaluation of Conjunctive Queries	2011	PODS	0.00013968198
1,310	Consistency Analysis in Bloom: a CALM and Collected Approach	2011	CIDR	0.00012658593
1,374	Relational Transducers for Declarative Networking	2011	PODS	0.0001230835
1,411	Communication Steps for Parallel Query Processing	2013	PODS	0.0001212565
1,865	Diagnosis of Asynchronous Discrete Event Systems: Datalog to the Rescue!	2005	PODS	0.00010275334
1,875	Verification of Communicating Data-Driven Web Services	2006	PODS	0.00010243508
3,135	Dynamically Distributed Query Evaluation	2001	PODS	7.4963337e-05
3,888	On the Expressive Power of Datalog: Tools and a Case Study	1990	PODS	6.6634475e-05
4,927	A Rule-based Language for Web Data Management	2011	PODS	5.8225392e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,298	Well-Founded Semantics for Extended Datalog and Ontological Reasoning	2013	PODS	6.2885419e-05
11,558	On Monotonic Determinacy and Rewritability For Recursive Queries and Views	2020	PODS	4.1945683e-05
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
4,223	Monotonic Aggregation in Deductive Databases	1992	PODS	6.3474752e-05
778	Declarative Networking: Language, Execution and Optimization	2006	SIGMOD	0.00016791276
6,833	Keep CALM and CRDT On	2023	VLDB	4.9125021e-05
11,889	Inner CALM: Concurrency control protocols through the looking glass	2015	CIDR	4.1945683e-05
2,339	Inference of Monotonicity Constraints in Datalog Programs (Extended Abstract)	1989	PODS	9.005745e-05
11,159	Distributed Consistency Beyond Queries	2023	PODS	4.1945683e-05
1,374	Relational Transducers for Declarative Networking	2011	PODS	0.0001230835