[DRAFT] CBCL: A Self-Bootstrapping Agent-Communication Language with Provable Safety and Convergence Properties
Hugo O’Connor, 2025-26-06
Abstract
Existing agent-communication languages (ACLs) expose a fixed vocabulary that can be extended only by out-of-band agreement. Open, rapidly changing environments such as IoT fleets, cross-chain smart contracts, and disaster-response coalitions inevitably experience semantic drift. This semantic drift produces failed communication attempts and requires human intervention.
We present CBCL (Constructor-Based Communication Language), a homoiconic ACL whose extension mechanism is encoded within the language itself. Unlike previous approaches that required trusted facilitators or pre-defined meta-languages, CBCL enables fully peer-to-peer dialect evolution. An agent written in CBCL can:
- define new domain dialects at run-time,
- teach them to peers in a fully peer-to-peer manner, and
- reason about which dialects it and its interlocutors speak.
We develop a formal operational semantics and prove that dialect evolution is:
• safe (core meanings of the bootstrap performatives are preserved),
• monotonic (knowledge only grows), and
• convergent (every dialect eventually spreads to all reachable, willing agents under weakly fair delivery).
A language-theoretic-security analysis, following the principles of Sassaman et al. [2011], establishes that self-extension never raises the computational class of the recognizer above deterministic context-free languages, eliminating the “weird-machine” attack surface. By constraining the input language complexity, we avoid the fundamental insecurity that arises when protocols approach undecidability. We prove that dialect verification is decidable in O(|δ|²) time and that propagation converges in O(log n) rounds under standard epidemic assumptions.
The theoretical framework demonstrates that runtime language extensibility is compatible with strong formal guarantees, resolving a fundamental tension in distributed system design. A complete planning dialect illustrates the framework’s expressiveness while maintaining all safety properties.
1 Introduction
1.1 Motivation