A Semilattice Characterization of Convergent Local Self-Configuration

Draft 2: corrects Draft 1 on the scope of the conclusion and the constant-operation example. Slightly fuller explanations.

Draft 1: Hopefully gets the basic idea across.

The Cognitive-Theoretic Model of the Universe (CTMU) models reality’s self-configuration through a two-stage process called telic recursion, wherein global generalized utility is maximized while local operators (telors) maximize local utility functions independently (Langan 2002). When teloric domains overlap, a single outcome must obtain. However, the source formulation specifies no algebraic mechanism for reconciling conflicting boundary states. This paper models overlap resolution as a term rewriting system: contributions fold into a boundary state via a binary operation ⊔, initialized at an empty boundary state e. Within this model, terminal states are invariant across all arrival orders and duplicate inputs if and only if (S, ⊔, e) is a bounded semilattice. Confluence under reordering is equivalent to commutativity and associativity. Invariance under duplicate delivery requires idempotence. We verify these properties on finite Cayley tables and show that this requirement directly matches the algebraic basis of Conflict-free Replicated Data Types (CRDTs).

1. Introduction

1.1 Overview

Consider a distributed system that configures state locally without central synchronization: autonomous processes update adjacent regions that periodically intersect. If each process updates state solely according to local utility without constraints on boundary combination rules, overlapping regions yield divergent states.

Convergence requires restricting the combination rule. If local processes resolve overlaps using an operation invariant to input sequence (commutativity), invariant to grouping (associativity), insensitive to repeated inputs (idempotence), and equipped with an empty boundary state acting as identity, boundary convergence is guaranteed across network delays, interleavings, and duplicate transmissions. These properties define a bounded semilattice. Within the operational model developed in Section 3, these conditions are both necessary and sufficient.

1.2 Contributions

1. A term rewriting model of local overlap resolution parameterized by a binary combination operation.
2. A formal proof that boundary derivations converge across all permutations and duplications of local inputs if and only if the combination operation is a bounded semilattice.
3. Counterexamples demonstrating the independence of commutativity, associativity, and idempotence, along with proof that an identity element is not implied by the other three axioms.
4. Executable test cases verifying algebraic properties on finite Cayley tables, including CRDT-style tagged sets for additive tracking.
5. An analysis mapping these algebraic constraints to the CTMU’s Telic Principle and syntactic grammar.

2. Preliminaries

2.1 Terms and Rewriting

Let Σ be a set of function symbols and V a set of variables. A term is a variable, constant, or function symbol applied to terms. A rewrite rule is an ordered pair ℓ → r. A set of rewrite rules forms a rewriting system. A term s rewrites to t (s → t) if s matches pattern ℓ under substitution σ and t substitutes the matched subterm with σ(r). We evaluate ground terms over finite carrier sets.

Let L(D) denote the set of finite lists over carrier set D. A boundary rewriting system is permutation-confluent if derivations from sequences L₁, L₂ ∈ L(D) reach the same normal form whenever L₁ and L₂ are multiset-equivalent. The system is set-confluent if L₁ and L₂ reach the same terminal state whenever they contain the same underlying set of distinct elements.

2.2 Semilattices

Definition 1. Let S be a set, ⊔ : S × S → S a binary operation, and e ∈ S a distinguished element. The structure (S, ⊔, e) is a bounded semilattice if, for all x, y, z ∈ S:

• (commutativity) x ⊔ y = y ⊔ x
• (associativity) (x ⊔ y) ⊔ z = x ⊔ (y ⊔ z)
• (idempotence) x ⊔ x = x
• (identity) x ⊔ e = e ⊔ x = x

Bounded semilattices form the algebraic foundation of state-based Conflict-free Replicated Data Types (CvRDTs), in which distributed replicas converge deterministically via pairwise state merges without coordination (Shapiro et al. 2011).

3. Local Overlap Resolution

3.1 Telic Recursion

The CTMU divides self-configuration into primary (global) and secondary (local) telic recursion (Langan 2002). In the secondary stage, local telors maximize local utility functions over their individual domains. The primary stage corresponds to the global telor (reality as a whole). The framework defines local telors as operating freely and independently, producing contingent local states.

Under this framing, local telic divergence is not anomalous. Langan writes that local telors are “mutually decoherent” and that departures from perfect complementarity occur continuously. Coherence is enforced globally. Addressing systemic coherence, Langan states that the universal wave function must remain coherent to prevent reality from decohering into mutually irrelevant subrealities (Langan, correspondence). In the CTMU, global consistency is governed by the Telic Principle, a global syntactic selection function that minimizes deviations from complementarity by maximizing generalized utility. The source formulation does not specify how two intersecting telors reconcile boundary updates locally. This paper determines what algebraic constraints such a combination rule must satisfy in an asynchronous, uncoordinated setting.

3.2 Rewriting Model of Boundary Merge

Let D denote the set of values determined locally by telors, closed under combination. Let e ∉ D denote an uninitialized boundary state, and let S = D ∪ {e}. Boundary states are unary terms (state w) for w ∈ S. An incoming contribution v ∈ D incorporates via the rule schema:

(merge v (state w)) → (state (w ⊔ v))

Given initial state (state e) and an incoming sequence of contributions L = [v₁, v₂, …, v_n], sequential reductions yield the terminal state:

(state (...((e ⊔ v1) ⊔ v2) ... ⊔ vn))

This left-associative accumulation is defined as foldl(⊔, e, L):

• foldl(⊔, e, [ ]) = e
• foldl(⊔, e, v :: L′) = foldl(⊔, e ⊔ v, L′)

To ensure an initial contribution v ∈ D establishes boundary state v, e acts as identity: e ⊔ v = v ⊔ e = v for all v ∈ S.

This construction assumes that input contributions arrive asynchronously and that convergence must obtain across every delivery sequence.

3.3 Asymmetric and Non-Commutative Rules Diverge

Arbitrary combination operations fail to guarantee boundary agreement. Let D = {p, q} and define two projection operations:

⊔_first(w, v) = w      ⊔_last(w, v) = v

Extend both operations with identity e such that e ⊔_first v = v and e ⊔_last v = v.

Evaluating inputs [p, q] and [q, p]:

• Under ⊔_first:
  foldl(⊔_first, e, [p, q]) = (e ⊔_first p) ⊔_first q = p ⊔_first q = p
  foldl(⊔_first, e, [q, p]) = (e ⊔_first q) ⊔_first p = q ⊔_first p = q
• Under ⊔_last:
  foldl(⊔_last, e, [p, q]) = (e ⊔_last p) ⊔_last q = p ⊔_last q = q
  foldl(⊔_last, e, [q, p]) = (e ⊔_last q) ⊔_last p = q ⊔_last p = p

Reversing arrival order changes the terminal state. Because both projection operations are associative and idempotent, commutativity is logically independent of associativity and idempotence. Furthermore, if adjacent telors apply divergent projection rules (⊔_first versus ⊔_last) to identical inputs [p, q], they resolve to contradictory values p and q.

4. Algebraic Characterization

4.1 Permutation Confluence

Theorem 1. Let S = D ∪ {e} and let ⊔ : S × S → S admit identity element e. The rewriting system is permutation-confluent; that is, foldl(⊔, e, L₁) = foldl(⊔, e, L₂) for any two lists L₁, L₂ ∈ L(D) that are permutations of one another if and only if ⊔ is associative and commutative on D.

Proof (Sufficiency). Because e is an identity, associativity and commutativity on D extend directly to S. Any finite permutation decomposes into a sequence of adjacent transpositions. It therefore suffices to prove that transposing adjacent elements v_i, v_i+1 in L leaves foldl(⊔, e, L) invariant.

Let L = [v₁, …, v_i-1, v_i, v_i+1, v_i+2, …, v_n] and let L′ be L with v_i and v_i+1 transposed. Let prefix accumulator a = foldl(⊔, e, [v₁, …, v_i-1]). The derivations evaluate identically on the prefix, diverging at positions i and i+1:

Derivation₁: (a ⊔ v_i) ⊔ v_i+1

Derivation₂: (a ⊔ v_i+1) ⊔ v_i

Applying associativity and commutativity:

(a ⊔ v_i) ⊔ v_i+1 = a ⊔ (v_i ⊔ v_i+1) = a ⊔ (v_i+1 ⊔ v_i) = (a ⊔ v_i+1) ⊔ v_i

The state at step i+1 is identical across both paths. Because both derivations reduce the same remaining suffix [v_i+2, …, v_n] from this common state, terminal states coincide: foldl(⊔, e, L) = foldl(⊔, e, L′). ■

Proof (Necessity).

1. Commutativity: Let L₁ = [x, y] and L₂ = [y, x]. Because e is identity, foldl(⊔, e, [x, y]) = x ⊔ y and foldl(⊔, e, [y, x]) = y ⊔ x. Permutation confluence requires x ⊔ y = y ⊔ x for all x, y ∈ D.
2. Associativity: The lists [x, y, z] and [z, y, x] are permutations of each other. Evaluating both gives foldl(⊔, e, [x, y, z]) = (x ⊔ y) ⊔ z and foldl(⊔, e, [z, y, x]) = (z ⊔ y) ⊔ x. Commutativity establishes (z ⊔ y) ⊔ x = x ⊔ (y ⊔ z). Permutation confluence forces (x ⊔ y) ⊔ z = x ⊔ (y ⊔ z) for all x, y, z ∈ D. ■

4.2 Deduplication and Set Confluence

Permutation invariance guarantees order independence over multisets but does not prevent divergence under duplicated inputs.

Theorem 2. Let (S, ⊔, e) be a commutative and associative monoid. The system is set-confluent; that is, foldl(⊔, e, L₁) = foldl(⊔, e, L₂) whenever L₁ and L₂ contain the same set of distinct elements if and only if ⊔ is idempotent (x ⊔ x = x for all x ∈ D).

Proof (Sufficiency). Let L contain v, and let L′ be L with an extra instance of v inserted. By Theorem 1, elements may be transposed without changing the terminal value. Reordering L′ adjacent to v yields:

foldl(⊔, e, L′) = foldl(⊔, e, [v₁, …, (v ⊔ v), …, v_n])

Because v ⊔ v = v, this reduces directly to foldl(⊔, e, L). By induction, redundant inputs can be eliminated without altering the final state. ■

Proof (Necessity). Assume ⊔ is not idempotent; then x ⊔ x ≠ x for some x ∈ D. Evaluating L₁ = [x] and L₂ = [x, x]:
foldl(⊔, e, [x]) = e ⊔ x = x
foldl(⊔, e, [x, x]) = (e ⊔ x) ⊔ x = x ⊔ x
The outputs diverge even though L₁ and L₂ share the same underlying set {x}. Idempotence is therefore required. ■

Theorems 1 and 2 establish that the system converges under arbitrary reordering and duplication if and only if (S, ⊔, e) is a bounded semilattice.

4.3 The Identity Element

The identity element is an independent structural axiom. The family of non-empty subsets of {p, q} under union satisfies commutativity, associativity, and idempotence, but lacks an identity. The empty set must be adjoined explicitly as e. The characterization relies on identity to equate foldl(⊔, e, [x, y]) with x ⊔ y and to extend closure to S. Without identity, necessity does not follow.

5. Computational Verification

5.1 Representation of Finite Algebras

Finite binary operations are represented as explicit Cayley tables encoded as rewrite rules:

rules (rule (op a a) a) (rule (op a b) b) (rule (op a c) c)
      (rule (op b a) b) (rule (op b b) b) (rule (op b c) c)
      (rule (op c a) c) (rule (op c b) c) (rule (op c c) c)

This encodes the join semilattice ⊔ = max over D = {a, b, c} under order a < b < c. Adjoining ⊥ such that (op ⊥ x) → x and (op x ⊥) → x establishes the bounded semilattice.

Automated predicates evaluate the axioms across all carrier pairs and triples:

> (is-commutative? max-table (list a b c))  ==> true
> (is-associative? max-table (list a b c))  ==> true
> (is-idempotent?  max-table (list a b c))  ==> true
> (is-semilattice? max-table (list a b c))  ==> true

A non-associative counter-table (broken-table) satisfies commutativity and idempotence while failing associativity:

> (is-commutative? broken-table (list a b c))  ==> true
> (is-idempotent?  broken-table (list a b c))  ==> true
> (is-associative? broken-table (list a b c))  ==> false
> (is-semilattice? broken-table (list a b c))  ==> false

5.2 Order Independence

Evaluating permutations through max-table and broken-table confirms Theorem 1:

> (fold-op max-table    bottom (list a b c))  ==> c
> (fold-op max-table    bottom (list c b a))  ==> c
> (fold-op max-table    bottom (list b c a))  ==> c
> (fold-op broken-table bottom (list a b c))  ==> c
> (fold-op broken-table bottom (list c b a))  ==> a
> (fold-op broken-table bottom (list b c a))  ==> a

The semilattice table converges across all permutations. The non-associative table diverges.

5.3 Duplicate Delivery

An integer addition table (add-table) with identity 0 satisfies commutativity and associativity, but not idempotence:

> (fold-op max-table bottom (list a b c))       ==> c
> (fold-op max-table bottom (list a b a c b))   ==> c
> (fold-op add-table 0 (list 1 2))              ==> 3
> (fold-op add-table 0 (list 1 2 1))            ==> 4

Duplicate inputs leave the idempotent operator invariant, whereas the non-idempotent sum diverges.

5.4 Additive Tracking via Tagged Identifiers

Non-idempotence in addition does not preclude additive tracking in distributed states. By tagging contributions with unique identifiers, boundary merge operations operate over sets via union (a semilattice), and total sums are computed projectionally over the merged set. This matches standard grow-only counter (G-Counter) implementations in CRDT architectures. In examples/semilattice-tagged.pal, events e1 and e2 carry values 1 and 2:

> plain addition, all orders of [1, 2]                     ==> (list 3)
> plain addition, [1, 2] and [1, 2, 1]                    ==> 3 4
> tagged, all orders of [e1:1, e2:2, e1:1]                ==> (list 3)
> tagged, [e1:1, e2:2] and [e1:1, e2:2, e1:1]              ==> 3 3
> tagged, distinct events [e1:1, e2:2, e3:1]              ==> 4

The semilattice requirement applies to the merged boundary state, not to projection functions evaluated on that state.

6. The Degenerate Constant Operation

Consider the constant operation x ⊔_k y = k for fixed k, extended such that e ⊔_k v = v ⊔_k e = v. Without this identity extension, the operation lacks an identity and does not satisfy the model in Section 3.2.

1. On carrier D with |D| > 1: The operation is commutative and associative, but fails idempotence because x ⊔_k x = k ≠ x for x ≠ k. By Theorem 1, its fold is order-invariant, mapping every sequence of length ≥ 2 to k. However, it violates set confluence: foldl(⊔_k, e, [x]) = x, whereas foldl(⊔_k, e, [x, x]) = k.
2. On carrier D = {k}: The operation satisfies commutativity, associativity, and idempotence (k ⊔_k k = k), forming a valid bounded semilattice with adjoined identity e.

A constant merge ensures convergence solely by discarding input information. Preserving information across non-singleton domains (|D| > 1) while guaranteeing invariance under reordering and duplication requires a non-trivial bounded semilattice.

7. Discussion

7.1 Equivalence to Distributed Convergence

Under Section 3.2, the convergence requirements for boundary resolution are mathematically identical to the convergence conditions of state-based CRDTs. Both models resolve updates without centralized scheduling. Applying these constraints to telic recursion is valid whenever overlap resolution involves independent local updates without global synchronization.

7.2 Syntactic Homogeneity, Shared Teleology, and SCSPL

The CTMU posits syntactic homogeneity: all regions instantiate identical grammatical rules (hology). However, shared syntax does not guarantee boundary consensus if combination rules remain unconstrained. As demonstrated in Section 3.3, processes running identical grammars can implement non-semilattice operations that produce permanent boundary contradictions.

This requirement aligns with the CTMU’s primary stage. A total order join (max) is a semilattice. If every telor evaluates overlaps by maximizing a shared ranking, the combination rule constitutes a single shared semilattice. Conversely, if telors evaluate local preferences without a shared ranking, outcomes diverge. The semilattice property formalizes how telors defer to a shared ranking. This matches Langan’s definition of the Telic Principle as a selection function parameterized by generalized utility, and aligns with the concept of shared teleology as a requirement for coherence.

7.3 Scope and Limitations

• Model assumptions: The results require the assumptions in Section 3.2: outcomes fold independently delivered inputs, and convergence must hold across all delivery orders. If the CTMU’s global stage selects outcomes directly, or if boundaries enforce fixed arrival schedules, semilattice constraints do not necessarily apply.
• Convergence versus optimization: A semilattice ensures agreement on a given input set, but does not dictate which contributions telors propose. If choices are strategic, boundary outcomes may remain suboptimal.
• Carrier scope: Computational checks verify finite domains, whereas the proofs in Section 4 hold for arbitrary carriers.
• Scope of claims: This analysis evaluates the algebraic mechanics of overlap resolution and does not evaluate broader CTMU metaphysical assertions.

8. Conclusion

Resolving boundary overlaps across autonomous local processes converges deterministically across arbitrary arrival orders and repeated inputs if and only if the combination operation is a bounded semilattice. Associativity and commutativity guarantee order invariance. Idempotence guarantees deduplication. An identity element preserves single contributions. This matches the convergence criterion of state-based CRDTs. In the CTMU, where overlap resolution is not algebraically specified, convergence requires a bounded semilattice structure, which can be realized by ordering states through generalized utility under a shared Telic Principle.

References

Christopher M. Langan, “The Cognitive-Theoretic Model of the Universe: A New Kind of Reality Theory” (2002).

Christopher M. Langan, correspondence on wholeness and the coherence of the universal wave function, in The Portable Chris Langan.

Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski, “Conflict-free Replicated Data Types,” Stabilization, Safety, and Security of Distributed Systems (SSS 2011), Lecture Notes in Computer Science vol. 6976, Springer, 2011.

Appendix A: Reproduction

git clone https://github.com/thoriumrobot/palimpsest
cd palimpsest
cargo build --release
./target/release/palimpsest examples/telor-semilattice.pal
./target/release/palimpsest examples/semilattice-tagged.pal
./verify-semilattice.sh

The automated suite evaluates:

1. Axiom checks (commutativity, associativity, idempotence) and the composite semilattice check on max-table and broken-table (Section 5.1).
2. Permutation invariance on max-table versus divergence on broken-table (Section 5.2).
3. Deduplication invariance on max-table versus summation divergence on add-table (Section 5.3).
4. Order and duplicate invariance of additive counters across tagged identifiers (Section 5.4).
5. Comparison of executed outputs against reference vectors via verify-semilattice.sh.