A Semilattice Characterization of Convergent Local Self-Configuration

Draft 3: Changes Draft 2 on the status of the identity element, the CRDT comparison, the constant-operation example and one interpretation of the Telic Principle.

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 the domains of two telors overlap, a single outcome must obtain, but Langan’s formulation does not specify an algebraic mechanism for reconciling the two contributions at the shared boundary. 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, and given that e is an identity, terminal states are invariant across all arrival orders and duplicate deliveries if and only if ⊔ is commutative, associative, and idempotent; that is, if and only if (S, ⊔, e) is a bounded semilattice. Order invariance is equivalent to commutativity and associativity. Invariance under duplicate delivery is then equivalent to idempotence. We verify these properties on finite Cayley tables and show that the same conditions underlie state-based 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 holds across network delays, interleavings, and duplicate transmissions. These properties define a bounded semilattice. Within the operational model of Section 3, which defines the empty boundary state as an identity, commutativity, associativity, and idempotence are both necessary and sufficient.

1.2 Contributions

A term rewriting model of local overlap resolution parameterized by a binary combination operation.
A proof that, given an identity element, boundary derivations converge across all permutations and duplications of local inputs if and only if the combination operation is commutative, associative, and idempotent (a bounded semilattice).
Counterexamples demonstrating the independence of commutativity, associativity, and idempotence, along with proof that an identity element is not implied by the other three axioms.
Executable test cases verifying these properties on finite Cayley tables, and an implementation showing that additive totals converge when each contribution carries an identifier.
An analysis mapping these conditions to the CTMU’s Telic Principle and to the homogeneity of SCSPL syntax.

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.

Because each list reduces deterministically one contribution at a time, the system is confluent in the standard rewriting sense (invariance under redex selection order). Throughout this paper, confluence refers specifically to invariance of the terminal state under input order and input multiplicity.

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

State-based Conflict-free Replicated Data Types (CvRDTs) share this structure: replica states form a join-semilattice and merge computes the least upper bound, ensuring replicas converge via pairwise merges without coordination (Shapiro et al. 2011). Whereas standard CRDT formulations require only a semilattice without a mandatory bottom element, this boundary model requires an identity element to initialize an unconfigured boundary state.

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, while 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 divergence is an expected consequence of decentralized execution. Langan writes that “localized telic binding is freely and independently effected by localized, mutually decoherent telic operators,” yielding ubiquitous deviations from perfect complementarity (Langan 2002). Global coherence is maintained by SCSPL syntax, which “incorporates a global (syntactic) invariant that works to minimize the total deviation from perfect complementarity of syntax and state”. This invariant, the Telic Principle, functions as “a selection function with a quantitative parameter, generalized utility, related to the deviation” (Langan 2002). Addressing wave-function coherence directly, Langan states that without global coherence the universe “pathologically decoheres into independent and mutually irrelevant subrealities” (Langan, correspondence). Because the source formulation does not define an operational rule for local boundary reconciliation, this paper determines the algebraic conditions required to guarantee convergence when contributions arrive asynchronously without an ordering coordinator.

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 ⊔ v₁) ⊔ v₂) ... ⊔ v_n))

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 hold 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 so that e is a two-sided identity: e ⊔ w = w ⊔ e = w for every w ∈ S. In particular, v ⊔_last e = v is defined explicitly, as an unextended projection rule would otherwise return e. Adjoining an identity to an associative operation preserves associativity.

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], their outputs contradict (p ≠ 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).

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.
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′ such that the two instances of v are adjacent yields accumulator state a immediately preceding them:

(a ⊔ v) ⊔ v = a ⊔ (v ⊔ v) = a ⊔ v

The first equality follows from associativity and the second from idempotence. The intermediate state after both instances equals the state after one. Because the remaining suffix reduces from this identical state, foldl(⊔, e, L′) = foldl(⊔, e, L). By induction, duplicate inputs reduce without changing the final state, establishing set confluence. ■

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 when e is an identity, the system converges under arbitrary reordering and duplication if and only if ⊔ is commutative, associative, and idempotent, forming a bounded semilattice (S, ⊔, e).

4.3 The Identity Element

The identity element is an independent structural requirement. Non-empty subsets of {p, q} under union satisfy commutativity, associativity, and idempotence, but lack an identity element unless the empty set is adjoined explicitly as e. The characterization relies on identity to equate foldl(⊔, e, [x, y]) with x ⊔ y, evaluate three-element lists, and extend closure to S. Without identity, necessity does not hold under the present formulation.

5. Computational Verification

5.1 Representation of Finite Algebras

Finite binary operations are represented as explicit Cayley tables encoded as ground 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 completes the bounded semilattice. In the test implementation, ⊥ is designated bottom, specifying rules (op bottom x) → x because a left fold initialized at ⊥ does not receive ⊥ as a right argument. The test predicates verify axioms directly on D.

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

Integer addition with identity 0 satisfies commutativity and associativity, but not idempotence. The test implementation models this via a partial table (add-table) containing only sums generated by the test sequences:

			
> (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 accumulator diverges.

5.4 Additive Tracking via Tagged Identifiers

Failure of idempotence in addition does not preclude additive tracking in distributed states. When contributions carry unique identifiers, boundary merge operations evaluate over sets via union (a semilattice), and totals are computed projectionally over the merged set. This corresponds to a grow-only set (G-Set) read through a summation projection, or a grow-only counter (G-Counter) tracking per-replica counts via entrywise maximum. 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 governs the underlying boundary state, not downstream 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 extension, the operation lacks an identity and does not satisfy the model in Section 3.2.

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, reducing every sequence of length ≥ 2 to k. However, it violates set confluence: for x ≠ k, foldl(⊔_k, e, [x]) = x, whereas foldl(⊔_k, e, [x, x]) = k.
On carrier D = {k}: The operation satisfies commutativity, associativity, and idempotence (k ⊔_k k = k), forming a valid bounded semilattice with adjoined identity e.

The constant operation converges under both reordering and duplication only on a singleton carrier, where input distinctions do not exist. On larger carriers, it achieves order invariance solely by discarding inputs, and fails under duplicate deliveries. By Theorems 1 and 2, any operation with identity that converges across both reordering and duplication must be a bounded semilattice.

7. Discussion

7.1 Equivalence to Distributed Convergence

Under Section 3.2, the convergence requirements for boundary resolution correspond directly to the criteria for state-based CRDTs, supplemented with an identity element for boundary initialization. Both formalisms resolve asynchronous updates without centralized scheduling. These constraints govern telic recursion whenever overlap reconciliation proceeds via independent local updates without global coordination.

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. Section 3.3 demonstrates that under non-commutative operations, terminal states depend on arrival sequence. Two regions executing the same rule on identical inputs in different sequences will diverge. Shared syntax ensures boundary agreement only if the shared combination operation is a semilattice.

This requirement aligns directly with the primary stage of telic recursion. If every telor resolves overlaps by computing a maximum under a shared total ordering of states (with consistent tie-breaking), the combination rule forms a semilattice. If telors apply disparate local preference rankings, boundary states diverge. Every semilattice induces a partial order (x ≤ y if and only if x ⊔ y = y), though not necessarily a total order (as shown by set union). A shared ranking provides a sufficient mechanism to satisfy this condition. Interpreting the Telic Principle as a global selection function parameterized by generalized utility (Langan 2002) yields a semilattice merge, formalizing Langan’s observation that distributed coherence relies on shared teleology.

7.3 Scope and Limitations

Model assumptions: The results depend on the framework 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 deterministic agreement on a provided set of inputs, but does not constrain which inputs telors propose. Strategic proposals may still result in Pareto-suboptimal states.
Carrier scope: Computational checks verify finite domains, whereas the proofs in Section 4 hold for arbitrary carriers.
Scope of claims: This analysis formalizes the algebraic mechanics of overlap resolution and does not evaluate broader metaphysical claims in the CTMU.

8. Conclusion

Within the model of Section 3.2, where inputs arrive independently and the empty boundary acts as identity, boundary resolution converges across arbitrary arrival orders and repeated inputs if and only if the combination operation is commutative, associative, and idempotent (a bounded semilattice). Commutativity and associativity guarantee order invariance, idempotence guarantees deduplication, and an identity element preserves single contributions. These conditions match the convergence criteria of state-based CRDTs. In the CTMU, where overlap resolution is not algebraically specified, local convergence requires a bounded semilattice, which can be implemented by ordering states via 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, reply to Paul Mackenzie on 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 test suite evaluates:

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