Conceptual Map

A guided conceptual tour through the vault. Where index lists the papers, this page lists the ideas and shows how they interlock. Every paper note now also carries a ## Conceptual Contribution section (claim / mechanism / concepts / stance / relates-to).

1. The Central Tension: What Does a Message Mean?

Agent communication’s perennial question — whose mental states does a message commit? — runs the length of this vault.

Speech Act Theory (Austin → Searle → Foundations Of Illocutionary Logic) fixes a vocabulary: illocutionary force, direction of fit, sincerity and preparatory conditions. Every ACL after this inherits it.
Mentalistic Semantics — grounding message meaning in the beliefs/intentions of sender and receiver. KQML (KQML Overview, KQML Language And Protocol, KQML as an Agent Communication Language) and FIPA-ACL adopt it.
Commitment-based Semantics / Public Semantics — the counter-move. Singh’s critique (ACL Rethinking Principles, Agent Communication Languages - Rethinking the Principles) argues mentalistic semantics is unverifiable: we cannot inspect another agent’s mind, only its public commitments. Agent Communication And Institutional Reality pushes further: every message is a declaration that alters social commitments; Searle’s “counts-as” is the operative logic.
Verifiable Semantics — Verifiable Semantics for ACLs formalises the critique by requiring grounding in program state so conformance is model-checkable. A Common Ontology Of ACLs offers a reconciliation: role-instanced public attitudes unify the two families.
Conversation Policy / Interaction Protocols — even with messages nailed down, coordination needs conversations. Coordinating Agents Using ACL Conversations (Colored Petri Nets), ACRE Agent Conversation Reasoning Engine (Dooley graphs), and An Interaction-oriented Agent Framework for Open Environments (commitment-based protocols) make the conversation first-class.

Surveys mapping this debate: The State of the Art in Agent Communication Languages, Trends in Agent Communication Language.

2. The Language Stack

Messages compose into languages compose into protocols.

Layer	Concept	Representative papers
Content	KIF, ontology term sets	KQML Overview, Ontolingua Portable Ontology Specifications, Handbook On Ontologies
Message	Performatives / illocutions	KQML, FIPA-ACL, Foundations Of Illocutionary Logic
Conversation	Interaction Protocols	Coordinating Agents Using ACL Conversations, ACRE Agent Conversation Reasoning Engine
Transport	Facilitators, routing	KQML Language And Protocol, Model Context Protocol, Agent-to-Agent Protocol

This same stack — content / message / conversation / transport — reappears in the modern LLM-agent protocol wave: see Survey Of AI Agent Protocols and Survey Of Agent Interoperability Protocols, which place Model Context Protocol (tools), ACP, Agent-to-Agent Protocol, and Agent Network Protocol at progressively higher layers.

3. How Does Shared Language Arise?

A separate tradition asks where meaning comes from rather than what it contains.

Linguistic foundations. Three Models for the Description of Language establishes what structure a shared code must have (Chomsky hierarchy, transformational grammar). Algorithmic Information Theory - Grunwald Vitanyi provides the information-theoretic counterpart: meaning is compressed description.
Language Games. Language Games for Autonomous Robots (Steels) shows grounded lexicons self-assemble through situated interaction — no designer required. The same bootstrap appears decision-theoretically in Towards Automating the Evolution of Linguistic Competence and Toward Automated Evolution of ACLs: rational agents negotiate vocabulary when current language fails.
Emergent Communication. The deep-learning revival: Multi-Agent Cooperation and the Emergence of Natural Language, Emergence of Grounded Compositional Language in Multi-Agent Populations — neural agents in referential/signalling games evolve compositional codes. On the Pitfalls of Measuring Emergent Communication is the sharpest critique: most metrics fail to distinguish real communication from confounds; measure positive signalling and positive listening with causal interventions.
Common Business Communication Language is an analogue in the pre-ML era — an open-ended language negotiable between organisations with graceful partial-understanding fallback.
The LLM inflection point. Why AI Agents Communicate In Human Language argues natural language is exactly the wrong inter-agent medium: lossy, non-differentiable, ambiguous. The thread rejoins the ACL debate a quarter-century later.

3a. Argumentation and Dialogue

A separate strand asks how reasoning unfolds when claims are contested rather than asserted unilaterally — directly upstream of the commitment-based ACL programme and of LLM-agent debate.

Abstract argumentation. On the Acceptability of Arguments (Dung 1995) shows that nonmonotonic reasoning, logic programming with negation-as-failure, default logic, and n-person games all reduce to fixed-point computations over an Argumentation Framework of arguments and attacks. Sceptical (Grounded Extension) and credulous (Preferred Extension) acceptance, plus stability, capture the principal answer policies. Structured systems (ASPIC+, ABA, DeLP) instantiate the abstract framework with rule languages — as does the SPL/Hence defeasible-logic engine used elsewhere in this vault.
Dialogue typology. Commitment in Dialogue (Walton & Krabbe 1995) gives the canonical typology — persuasion, negotiation, deliberation, inquiry, information-seeking, eristic — that ACL designers keep rediscovering. Each dialogue type is characterised by its initial situation, participant goals, and shared goal; mixing is normal but mismatch (e.g. expecting persuasion in a negotiation) is the source of much MAS dysfunction.
Formal dialectic. Fallacies - Hamblin (Hamblin 1970) supplies the missing root: dialogue rules with explicit commitment stores, where moves like “Why?”, “Statement”, “Concession” update the participants’ public commitment sets. Modern dialogue protocols (ACRE, Walton-McBurney systems) are direct descendants.

4. Extensibility: Grow the Language Toward the Problem

A recurring architectural instinct runs from 1960s language design through to modern agent protocols.

Programming-language origin. Extensibility in Programming Language Design - Standish supplies the taxonomy (Paraphrase / Orthophrase / Metaphrase). The Extensible Language - Graham is the Lisp-flavoured manifesto: Bottom-up Programming, Macros as Language Extension, Code as Data. Creating Languages in Racket is its modern realisation; The Spoofax Language Workbench makes IDEs-from-grammars a production idea; A Modular Approach to Metatheoretic Reasoning for Extensible Languages supplies the formal backing (modular proofs across user-added fragments).
Distributed-system extensibility. Extensible Distributed Coordination applies the same move to ZooKeeper-style coordination: sandboxed server-side extensions trump a fixed API.
Agent-communication extensibility. Agora (A Scalable Communication Protocol for Networks of LLMs) is the linguistic realisation of this instinct for LLM agents: no fixed format can satisfy versatility × efficiency × portability (the “agent communication trilemma”); agents instead negotiate Protocol Documents identified by content hash and have LLMs write the routines. That is “grow the language toward the problem” at the network layer.

5. Agent Theory: What Kind of Thing Is an Agent?

Weak Agency vs Strong Agency. Intelligent Agents Theory and Practice (Wooldridge & Jennings) supplies the canonical split and the theory / architecture / language triad.
Theory. Agent-Oriented Programming (Shoham) proposes agents as modules with formally-specified Mental State (beliefs, commitments, capabilities, choices); the AGENT-0 language encodes honesty and commitment constraints. BDI (Belief-Desire-Intention) is the dominant architecture across Multiagent Systems Sycara, Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents, A Common Ontology Of ACLs.
Ethics and runtime self-oversight. Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents requires an Ethical Governor with A-ILTL meta-rules as a Metacognitive Loop.
Environment as first-class. An Interaction-oriented Agent Framework for Open Environments elevates Agents and Artifacts (JaCaMo / Jason / CArtAgO / MOISE) — communication isn’t only agent-to-agent but agent-to-artefact-to-agent.

6. Multi-Agent Coordination

The coherence problem. Multiagent Systems Sycara names it: how do autonomous agents produce coherent global behaviour? Classic answers: Contract Net Protocol, Joint Intentions, Negotiation.
Fragility of coordination. Are Multiagent Systems Resilient to Communication Failures is a striking negative result: even a single missed message about a weakly-coupled agent can send game-theoretic MAS to arbitrarily bad equilibria. Why Do Multi-Agent LLM Systems Fail is its LLM-era empirical counterpart: the MAST Taxonomy shows failures are overwhelmingly system-design (specification / coordination / verification), not model-capability.
Population-scale design. Levels Of Social Orchestration reframes the scaling question: leverage comes from protocol design, not bigger models — shift from LLM to Large Population Models. Ripple Effect Protocol is a concrete instance: share counterfactual sensitivities across agents, not just decisions.
Organisational substrate. How Do Committees Invent (Conway’s Law) is the ur-text: any designed system mirrors the communication structure of its designing organisation. This is the sociological shadow over every coordination result in the vault.

7. Self- Systems and Biological Metaphors

A lineage that uses adaptation, awareness, and biology as organising ideas.

Self-reproduction. Theory of Self-Reproducing Automata (von Neumann) gives the complication-threshold result: beyond a critical complexity automata can self-reproduce and evolve iff they tolerate local error.
Self-adaptive ensembles. Self-Adaptation Self-Expression Self-Awareness ASCENS (the ASCENS project) factors self- into three complementary capabilities along individual/collective × behaviour/structure axes. A Composite Self-organisation Mechanism in an Agent Network is an instance (DSmT trust fusion + multi-agent Q-learning on weighted relations).
Biological substrate. Myconet Fungi Inspired Superpeer Overlay (fungal mycelium / stigmergy) produces resilient superpeer topologies. Computational Boundary of a Self (Levin) generalises selfhood to a cognitive light cone — any system with a goal-directed computational surface is a self at some scale.

8. Gossip and Probabilistic Coordination

Foundations. Gossiping in Distributed Systems factors gossip into a three-parameter design space (peer selection / data exchanged / data processing) that unifies divergent (dissemination) and convergent (aggregation) protocols.
Aggregation. Gossip-Based Computation of Aggregate Information (Push-Sum) and Gossip-based Aggregation in Large Dynamic Networks (push-pull on a Peer Sampling Service) establish mass conservation + exponential convergence for aggregates over volatile networks.
Application. Myconet Fungi Inspired Superpeer Overlay uses newscast gossip; Edge Intelligence Survey uses gossip training across the cloud-edge-device hierarchy.

9. Trust, Reputation, and Open-System Robustness

Taxonomy. Review on Computational Trust and Reputation Models decomposes trust into direct experience, witness reputation, sociological reputation, prejudice; and models into cognitive vs game-theoretic.
Context. Mobile-agent-era concerns in DAgents Security Book Chapter, Agent Tcl Flexible Secure Mobile Agents, Agents Secure Interaction in Data Driven Languages.
LLM-era. AI Agents Under Threat surveys the four knowledge gaps (perception / brain / action across agent-to-{agent, env, memory}); MalTool Malicious Tool Attacks shows real harm lives in tool implementations, not tool descriptions.

10. Language-Theoretic Security

A tight sub-thread arguing that most security failures are really recognition failures.

LangSec core. The Halting Problems of Network Stack Insecurity is foundational: over-powerful input languages make safety undecidable — the cure is to restrict inputs to what can be recognised by a minimal-power parser. Seven Turrets Of Babel catalogues the seven canonical anti-patterns (shotgun parsing etc.) and names grammar-first validating recognisers as the remedy.
Exploits as language ambiguity. PKI Layer Cake - Kaminsky Patterson Sassaman: when CA and browser parse the same bytes differently, trust collapses — a Parser Differential attack.
Language-based defences. A Language-Based Approach To Prevent DDoS (static detection of call-flow cycles in actor systems), Secure Communications Processing for Distributed Languages (cryptographic wrappers with full-abstraction guarantees), Security Kernel Lambda Calculus (lexical scope as a capability kernel — Capability Security), Architectural Patterns for Dependable Software Systems - SOL (SOL + SINS middleware, compositional formal dependability).

11. Ontologies and Shared Meaning

Necessary scaffolding for any ACL — and a field in its own right.

Ontolingua Portable Ontology Specifications defines the Gruber formulation (Ontology = explicit specification of a Conceptualization) and portability via KIF translation.
Handbook On Ontologies is the comprehensive reference (description logics, OWL, RDF, frame logic, semantic web).
Ontology Change Classification and Survey tames the fragmented sub-literature (evolution / mapping / merging / alignment) into a coherent taxonomy — crucial for long-lived agent systems.
A Common Ontology Of ACLs uses ontology technology to reconcile ACL semantic families.

12. Foundations Beneath It All

A few papers anchor the abstract ground everything else stands on.

Process Calculi. Communicating Sequential Processes (Hoare 1978), A Calculus of Communicating Systems (Milner 1980), and A Calculus of Mobile Processes (Milner, Parrow & Walker 1992) — the formal substrate underneath every later result on session types, choreographies, and distributed concurrency. The π-calculus’s Name-Passing + Scope Extrusion is the missing semantic primitive under Multiparty Asynchronous Session Types and Pact - A Choreographic Language for Agentic Ecosystems; Mobile Ambients is the location-first sibling motivating administrative-domain reasoning; Spi Calculus adds cryptographic primitives, bridging to LangSec / BAN Logic verification.
Program semantics. Assigning Meanings to Programs (Floyd) — assertions on flowchart edges; birth of axiomatic semantics. Foundations of Logic Programming - Lloyd — the declarative/procedural unity under SLD-resolution.
Information. Algorithmic Information Theory - Grunwald Vitanyi — Kolmogorov complexity and MDL: the meaning of an object is the length of its shortest program.
Concurrency substrate. Programming Erlang Second Edition — the actor-model textbook, let-it-crash + supervision trees. This is the operational grain of most distributed agent systems discussed above.
Architectural style. Principled Design Of The Modern Web Architecture (Fielding / REST) — the explicit constraints (uniform interface, statelessness, hypermedia) that make internet-scale coordination possible. The modern LLM-agent protocols recapitulate these constraints deliberately.
Blockchain / smart contracts. Making Smart Contracts Smarter (semantic gap between intent and EVM), Formalise Blockchain Interoperability Patterns (Event-B refinement proofs) — formal-methods vocabulary applied to a new coordination substrate.
Distributed-consistency theory. Keeping CALM - When Distributed Consistency is Easy gives the positive dual to CAP Theorem: a program has a consistent, coordination-free implementation iff it is monotonic (CALM Theorem, Confluence, Monotonic Logic). This is the theoretical companion to the gossip-aggregation results in §8 — aggregation with mass conservation is exactly monotonic — and the reason CRDTs, Immutable Data Structures, and Tombstones recur as patterns throughout the vault.

13. The Modern LLM-Agent Era: How the Threads Converge

The contemporary LLM-agent wave recapitulates the full vault simultaneously.

From chatbots to agents. From Eliza to XiaoIce - Social Chatbots supplies the direct design ancestry of user-facing conversational AI.
Framework. Agents Framework - Zhou et al — declarative Standard Operating Procedures (SOPs) as symbolic plans driving LLM agents.
Collaboration. Multi-Agent Collaboration in AI - Wasif Tunkel — role-specialised teams, human-in-the-loop. Why Do Multi-Agent LLM Systems Fail (MAST).
Protocol stack. Survey Of AI Agent Protocols, Survey Of Agent Interoperability Protocols, Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol.
Native protocol design. A Scalable Communication Protocol for Networks of LLMs (Agora / trilemma), Ripple Effect Protocol (sensitivity sharing), Levels Of Social Orchestration (population-scale).
Critique. Why AI Agents Communicate In Human Language — the semantic-misalignment / differentiability critique of NL-as-protocol.
Security. AI Agents Under Threat, MalTool Malicious Tool Attacks, ClawWorm Self-Propagating Attacks Across LLM Agent Ecosystems, SoK The Attack Surface of Agentic AI.

Each modern thread has a pre-LLM ancestor in this vault — which is the real point of the map.

14. Agentic AI Security and the Multi-Agent Threat Surface

A 2024–2026 wave makes agentic security a field unto itself, with a clear three-layer structure: single-agent runtime defences → multi-agent threats → governance & economic substrate.

Runtime / prompt-injection defences. AgentDojo (Debenedetti et al. 2024, NeurIPS) is the dynamic benchmark — four realistic environments, 97 user tasks × 629 injection tests, parallel user-success / attack-success metrics. Defeating Prompt Injections by Design (Debenedetti, Shumailov, Tramèr et al. 2025) is the architectural response — CaMeL: control-flow / data-flow separation between the trusted query and untrusted tool data, with capability-gated tool calls. Together they form the contemporary case for Prompt Injection being a systems problem solved by Information Flow Control, not a model-content problem solved by classifiers.
Privacy reasoning. Privacy Reasoning in Ambiguous Contexts (Yi et al. 2025, NeurIPS) — Contextual Integrity operationalised: the dominant LLM privacy failure is unrecognised ambiguity, fixed by rationale-driven disambiguation (Camber).
Multi-agent threat field. Open Challenges in Multi-Agent Security (Schroeder de Witt et al. 2025) defines Multi-Agent Security as a discipline: secret collusion (covert/steganographic coordination defeating oversight), swarm attacks, network-effect contagion (privacy breaches, jailbreaks, disinformation spreading agent-to-agent), and stealth optimisation (dispersion-based evasion). Free-form protocols enable both task generalisation and these new threats — a fundamental security–utility trade-off.

15. The Agent Economy: Infrastructure, Markets, Mechanism Design

A parallel 2023–2025 thread asks what economic layer the agent fabric will run on, and how to design it.

Economic framing. Virtual Agent Economies (Tomasev et al. 2025) introduces the Sandbox Economy framework — origin (emergent / intentional) × separateness (permeable / impermeable). Argues current trajectory occupies the riskiest quadrant (spontaneous + permeable) and proposes auctions, mission economies, and socio-technical governance as steering levers.
Governance infrastructure. Infrastructure for AI Agents (Chan et al. 2025, TMLR) names three external-to-the-agent functions: attribution (agent IDs, verifiable credentials, audit), interaction shaping (protocols, mechanism design, reputation), detection & remediation (anomaly detection, rollback, compensation). The institutional counterpart to the runtime defences of §14.
Mechanism design for LLM-generated content. Mechanism Design for Large Language Models (Dütting et al. 2023, WWW Best Paper) generalises Myerson’s Lemma / Vickrey Auction to outcomes that are LLM-generated tokens and preferences encoded as LLMs — a token-level second-price-style auction supported by a monotone-aggregation characterisation.
Information markets. Language Models Can Reduce Asymmetry in Information Markets (Rahaman et al. 2024) shows LLM agents with the dual capability of evaluate + forget can resolve the Arrow Information Paradox — a forerunner of NDAI Agreements (Stephenson et al. 2025), which uses TEE+AI to solve the same Hold-Up Problem in formal-economic terms, and of Trusted Machine Learning Models Unlock Private Inference (Shumailov et al. 2025), which generalises the trusted-intermediary thesis as TCMEs — capable model + I/O constraints + IFC + statelessness — extending private inference beyond what classical MPC can scale.
Game-theoretic foundations. Do LLM Agents Have Regret (Park et al. 2024) asks whether LLM agents exhibit no-regret behaviour in repeated games — usually yes, with sharply identified failure cases that a new Regret-Loss objective patches. Provides the analytical grounding for everything in §15: if agents are no-regret, the equilibrium analyses underlying mechanism design and market design carry over. Learning Collusion in Episodic Inventory-Constrained Markets (Friedrich et al. 2024, AAMAS) supplies the unhappy companion: deep-RL agents collude in airline-style perishable-good markets via signalling, stable, and cyclic strategies — empirical evidence for the systemic-risk warnings in Virtual Agent Economies and the Algorithmic Collusion thread of Open Challenges in Multi-Agent Security.

The §14 and §15 threads converge on a single thesis: agentic AI security and the agent economy are the same design problem viewed from different layers. Runtime defences (CaMeL, AgentDojo) make individual agents safe; governance infrastructure (Infrastructure for AI Agents) makes their interactions accountable; mechanism design (Mechanism Design for Large Language Models, NDAI Agreements) makes their economic transactions incentive-compatible; multi-agent security (Open Challenges in Multi-Agent Security) names the threats that arise because of those interactions; and frameworks like Virtual Agent Economies tie the whole stack to long-run human flourishing. The capability-based / language-based / commitment-based traditions catalogued earlier in this map (§1–§12) are the deep ancestry of every defence proposed.

Four Cross-Cutting Debates

Private vs public semantics — mentalistic (KQML, FIPA-ACL) vs commitment-based (ACL Rethinking Principles, Agent Communication And Institutional Reality) vs grounded (Verifiable Semantics for ACLs). Reopened by Why AI Agents Communicate In Human Language.
Designed vs evolved languages — standardised (FIPA-ACL) vs negotiated (Toward Automated Evolution of ACLs, A Scalable Communication Protocol for Networks of LLMs) vs emergent (Language Games for Autonomous Robots, Multi-Agent Cooperation and the Emergence of Natural Language).
Centralised vs decentralised coordination — facilitators (KQML Overview) vs gossip (Gossip-Based Computation of Aggregate Information) vs stigmergy (Myconet Fungi Inspired Superpeer Overlay) vs agent-environment (An Interaction-oriented Agent Framework for Open Environments).
Trust through mental-state inspection vs through commitments vs through language-theoretic restriction — Verifiable Semantics for ACLs vs ACL Rethinking Principles vs The Halting Problems of Network Stack Insecurity.

Concept Diagrams

Mermaid lineage diagrams for each foundational cluster, embedded in the relevant concept pages:

Speech Act Theory#Lineage — Austin → Searle → Grice → Vanderveken → ACL performatives
Knowledge Level#Knowledge-representation lineage — McCarthy → Frames → Circumscription → Knowledge Level → BDI / Society of Mind / Extended Mind
Rice’s Theorem#Computability lineage — Gödel / Church / Turing / Kleene / Post → Rice → LangSec
Agent Architecture#Architectural lineage — Actor · BDI · Subsumption · Intentional Stance → AGENT-0
Program Semantics#Language, semantics, and concurrency lineage — Chomsky · McCarthy · Floyd · Hoare · Backus · Naur

See index for the full paper listing, README for vault conventions.

Backlinks

Linked Pages

README

Agent Communications — Paper Vault

A zetl vault of summaries of every paper in this repository.

Conventions

One markdown file per paper. Filenames are slugified titles (e.g. KQML-Overview.md).
Each note contains:
- # Title heading
- Reference (authors, year, venue/source file)
- Summary — 1–3 paragraphs of core ideas
- Key ideas — bullet list
- Connections — [[wikilinks]] to related notes or concept pages
Concept notes (e.g. [[KQML]], [[FIPA-ACL]], [[Gossip Protocols]]) act as hubs.
index is the Map of Content (MOC) grouping every note by theme.

Layout

index — Map of Content, every paper grouped by theme
concept-map — the conceptual tour: the ideas and how they interlock
Per-paper notes contain summary + key ideas + connections + ## Conceptual Contribution (claim / mechanism / concepts / stance / relates-to)
Concept hubs (e.g. KQML, LangSec, Commitment-based Semantics, BDI) act as junctions
Fine-grained technical terms are wikilinked without dedicated pages (“wanted pages”) so that future notes can backfill definitions — expected zetl pattern, not a defect

Commands

zetl list         # list notes
zetl check        # validate links
zetl stats        # graph stats
zetl serve        # browse

index

Agent Communications Vault

A curated, wikilink-connected reading vault on agent communication languages, multi-agent systems, capability security, distributed systems, and LLM agents — from McCarthy and Minsky through KQML/FIPA to modern LLM agent protocols.

Each note summarises a paper in its own words (summary, key ideas, conceptual contribution, connections) and is cross-linked to related concepts and papers, forming a navigable graph of the field.

Start with concept-map for a guided tour, or browse the map of content below.

How to contribute

The vault is a plain-text zetl wikilink graph — every note is a markdown file with [[wikilinks]]. Contributions welcome:

Clone: git clone https://github.com/anuna-cooperative/agent-comms-wiki.git
Add or edit notes as plain markdown. New paper notes should follow the structure of existing ones (Reference, Summary, Key Ideas, Connections, Conceptual Contribution, Tags).
Run zetl check to validate links, and zetl build to preview the site locally.
Open a pull request at https://github.com/anuna-cooperative/agent-comms-wiki.

See README for detailed conventions.

Map of Content

Concept Hubs

Foundational

Program Semantics

The mathematical definition of what a program means — operational (how it runs), denotational (what value it computes), or axiomatic (what properties it guarantees). Verifiable ACL semantics require programs whose meaning is pinned down precisely enough for conformance to be checked.

In this vault

Language, semantics, and concurrency lineage

graph TD
  CH["Chomsky (1956)<br/>Three Models for the Description of Language"] --> GRAM[Formal grammars]
  MC["McCarthy (1960)<br/>Recursive Functions of Symbolic Expressions"] --> LISP[LISP / λ-calculus lineage]
  MC --> MS["McCarthy (1962)<br/>Towards a Mathematical Science of Computation"]
  MS --> CC["McCarthy & Painter (1966)<br/>Correctness of a Compiler for Arithmetic Expressions"]
  FL["Floyd (1967)<br/>Assigning Meanings to Programs"] --> AX[Axiomatic / inductive assertions]
  NAUR["Naur<br/>Proof Method for Cyclic Programs"] --> AX
  NAUR --> APP[Application of cyclic-program method]
  CC --> AX
  AX --> HOARE["Hoare (1978)<br/>Communicating Sequential Processes"]
  HEW["Hewitt (1973)<br/>Actor Formalism"] --> CONC[Concurrent message-passing]
  HOARE --> CONC
  CONC --> PI[π-calculus / process calculi]
  LISP --> BK["Backus (1978)<br/>Can Programming Be Liberated from the von Neumann Style"]
  BK --> FP[Functional programming]
  AX --> PS((Program Semantics))
  PI --> ACL[[Agent Communication Languages]]
  FP --> ACL

Papers: Three Models for the Description of Language · Recursive Functions of Symbolic Expressions and Their Computation by Machine · Towards a Mathematical Science of Computation · Correctness of a Compiler for Arithmetic Expressions · Assigning Meanings to Programs · A Proof Method for Cyclic Programs · An Application of a Method for Analysis of Cyclic Programs · Communicating Sequential Processes · Can Programming Be Liberated from the von Neumann Style · A Universal Modular Actor Formalism for Artificial Intelligence

Agent Architecture

The internal computational organisation of an agent — deliberative (BDI), reactive (subsumption), layered, or hybrid — along with the control loop and data pipelines that realise it.

In this vault

Architectural lineage

graph TD
  MC["McCarthy (1979)<br/>Ascribing Mental Qualities to Machines"] --> IS["Dennett<br/>Intentional Stance<br/>True Believers"]
  HEW["Hewitt (1973)<br/>Universal Modular Actor Formalism"] --> ACTOR[Actor Model]
  ACTOR --> CONC[Concurrent agents]
  BRAT["Bratman (1987)<br/>Intention Plans Practical Reason"] --> BDI[[BDI]]
  RG["Rao & Georgeff<br/>BDI Logic"] --> BDI
  MIN["Minsky<br/>Society of Mind"] --> SOC[Societies of sub-agents]
  BRO["Brooks (1991)<br/>Intelligence Without Representation"] --> SUB[Subsumption]
  SUB --> REACT[Reactive / behaviour-based]
  IS --> SHO["Shoham (1993)<br/>AGENT-0 · Agent-Oriented Programming"]
  BDI --> SHO
  SHO --> AA((Agent Architecture))
  REACT --> AA
  SOC --> AA
  CONC --> AA
  AA --> HYB[Hybrid / layered]

Papers: A Universal Modular Actor Formalism for Artificial Intelligence · Ascribing Mental Qualities to Machines · Intelligence Without Representation · The Society of Mind · True Believers - The Intentional Strategy and Why It Works · AGENT-0

Rice's Theorem

Rice’s Theorem

A foundational result in computability theory (Henry Gordon Rice, 1951–53): every non-trivial semantic property of the partial function computed by a program is undecidable. Source paper: Classes of Recursively Enumerable Sets and Their Decision Problems. “Non-trivial” means the property holds for some computable functions but not others; “semantic” means it depends on the input/output behaviour, not on the syntactic form of the program.

Put differently: you cannot in general decide, by inspecting a program, whether it belongs to any interesting class defined by what it does. Halting is one such property (Halting Problem), but so is “produces output X on input Y,” “terminates for all inputs,” “implements function f,” “contains no unreachable states,” and so on.

Rice’s theorem is the formal frontier against which static-analysis, verification, and capability-bounding claims must be measured. Any tool promising to decide a non-trivial semantic property on arbitrary programs is — by Rice — either restricting the program class (e.g. Finite-state Grammars, typed or total subsets) or approximating (sound-but-incomplete analyses). Whole research programs — LangSec, Formal Verification, Static Analysis, Weird Machine — are organised around this constraint.

Concrete implication cited in House on Rock - LangSec in Ethereum Classic: Ethereum’s gas mechanism cannot “sidestep Turing completeness” to deliver a safety guarantee, because safety is a semantic property and Rice’s theorem makes semantic properties of arbitrary programs undecidable. Gas is a resource bound (non-semantic, decidable) masquerading as a safety property (semantic, undecidable).

Connections

Computability lineage

graph TD
  G["Gödel (1931)<br/>Incompleteness (Principia)"] --> GR["Gödel (1934)<br/>General Recursive Functions"]
  C["Church (1936)<br/>An Unsolvable Problem of Elementary Number Theory"] --> K["Kleene (1936)<br/>On Notation for Ordinal Numbers"]
  GR --> K
  T["Turing (1936)<br/>On Computable Numbers"] --> HALT[[Halting Problem]]
  C --> HALT
  K --> RE["Kleene (1943)<br/>Recursive Predicates and Quantifiers"]
  RE --> POST1["Post (1944)<br/>Recursively Enumerable Sets"]
  POST1 --> POSTPROB["Post's Problem"]
  RE --> MYH["Myhill (1952)<br/>On Definable Sets of Positive Integers"]
  POST1 --> RICE["Rice (1953)<br/>Classes of R.E. Sets and Their Decision Problems"]
  HALT --> RICE
  RICE --> RT((Rice's Theorem))
  RT --> LS[[LangSec]]
  RT --> FV[[Formal Verification]]
  RT --> SA[[Static Analysis]]
  GR -.equivalence.- T
  C -.equivalence.- T

Papers: Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I · General Recursive Functions of Natural Numbers · An Unsolvable Problem of Elementary Number Theory · On Notation for Ordinal Numbers · Recursive Predicates and Quantifiers · Recursively Enumerable Sets of Positive Integers and Their Decision Problems · On Definable Sets of Positive Integers · Classes of Recursively Enumerable Sets and Their Decision Problems · Extensions of Some Theorems of Gödel and Church

Tags

#computability #undecidability #foundational #langsec #verification

Knowledge Level

Newell: a level of system description above the symbol level, in which behaviour is explained by what the system knows and wants (principle of rationality) — the theoretical home of agent theory.

In this vault

Knowledge-representation lineage

graph TD
  MC1["McCarthy (1959)<br/>Programs with Common Sense"] --> AT[Advice Taker]
  AT --> MC2["McCarthy (1969)<br/>Epistemological Problems of AI"]
  MIN1["Minsky (1974)<br/>A Framework for Representing Knowledge"] --> FR[Frames]
  MC2 --> CIRC["McCarthy (1980)<br/>Circumscription"]
  CIRC --> NM[Nonmonotonic reasoning]
  FR --> SoM["Minsky (1986)<br/>Society of Mind"]
  NEW["Newell (1982)<br/>The Knowledge Level"] --> KL((Knowledge Level))
  MC2 --> KL
  KL --> BDI[[BDI]]
  KL --> INT["Dennett<br/>Intentional Stance"]
  BRO["Brooks (1991)<br/>Intelligence Without Representation"] -.critique.-> KL
  CC["Clark & Chalmers (1998)<br/>The Extended Mind"] --> SoM
  SoM --> AGT[[Agent Architecture]]
  BDI --> AGT

Papers: Programs with Common Sense · A Framework for Representing Knowledge · Circumscription - A Form of Nonmonotonic Reasoning · The Knowledge Level · The Society of Mind · Intelligence Without Representation · The Extended Mind · Epistemological Problems of Artificial Intelligence

Speech Act Theory

Philosophy-of-language framework (Austin, Searle, Vanderveken) in which utterances perform actions (illocutionary acts) — the semantic backbone of most Agent Communication Languages.

Sources

Foundations Of Illocutionary Logic — Searle & Vanderveken
Three Models for the Description of Language — Chomsky, foundations
Agent Communication And Institutional Reality

Applied in

Lineage

graph TD
  A["Austin (1962)<br/>How to Do Things with Words"] --> A1[Locutionary]
  A --> A2[Illocutionary]
  A --> A3[Perlocutionary]
  A2 --> S["Searle (1969, 1975)<br/>Speech Acts · Taxonomy of Illocutionary Acts"]
  S --> S1[Assertives]
  S --> S2[Directives]
  S --> S3[Commissives]
  S --> S4[Expressives]
  S --> S5[Declarations]
  G["Grice (1975)<br/>Logic and Conversation"] -.cooperative principle.-> S
  S --> V["Searle & Vanderveken (1985)<br/>Foundations of Illocutionary Logic"]
  V --> M["McCarthy (1989)<br/>Elephant 2000"]
  V --> KQML[KQML performatives]
  V --> FIPA[FIPA-ACL performatives]
  M --> FIPA
  KQML --> ACL[[Agent Communication Languages]]
  FIPA --> ACL

Papers: How to Do Things with Words · Speech Acts - An Essay in the Philosophy of Language · A Taxonomy of Illocutionary Acts · Logic and Conversation · Foundations Of Illocutionary Logic · Elephant 2000 - A Programming Language Based on Speech Acts

The Halting Problems of Network Stack Insecurity

Reference: Sassaman, Patterson, Bratus, Shubina (2011). ;login: (USENIX), Vol. 36, No. 6. Source file: The_Halting_Problems_of_Network_Stack_In.pdf. URL

Summary

The paper founds language-theoretic security (LangSec) on a startling thesis: accepted/valid inputs to a program form an input language, and a program’s input-handling code is effectively a recognizer for that language. Insecurity arises when this recognizer problem is computationally too powerful — recognizing context-sensitive or Turing-complete input languages makes validity checking undecidable, so exploitable mismatches between the intended and actual recognizer are inevitable.

Through examples (X.509 ASN.1 parsing, SQL injection, network-stack fingerprinting, 802.15.4 SFD attacks, qmail), the authors show how handwritten ad-hoc recognizers introduce “weird machines” on which crafted inputs execute exploit programs. They propose two principles: (1) Starve the Turing beast — give parsers only the minimum computational power needed; (2) Secure composition requires parser computational equivalence. They argue HTML5’s Turing-completeness regresses safety, and JSON/S-expressions exemplify the right design.

Key Ideas

Inputs form a formal language; parsers are recognizers.
Undecidability of input validity => unexploitable security impossible.
Exploits run on “weird machines” built from crafted inputs.
Minimal computational power principle (a LangSec Least Privilege).
Postel’s robustness principle harmful for security.

Connections

Language Workbenches
LangSec
Parser Differential
Protocol Documents
Agent Communication Languages
Multi-Agent Systems
An Unsolvable Problem of Elementary Number Theory — Church 1936, the undecidability result the title invokes.
Recursively Enumerable Sets of Positive Integers and Their Decision Problems — Post 1944, decision-problem framing behind the recognizer view.
Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I — Gödel 1931, the incompleteness ancestor of the LangSec impossibility argument.
CBCL - Safe Self-Extending Agent Communication — applies the “starve the Turing beast” principle to agent-communication languages: DCFL-bounded inputs, including runtime extensions.

Conceptual Contribution

Claim: Much network-stack insecurity is a consequence of treating input validation as an ad-hoc engineering task rather than as a formal recognition problem; if the input language is too powerful, safe validation is undecidable and exploitable “weird machines” are inevitable.
Mechanism: Sassaman et al. recast every parser as a recognizer for a formal language and map concrete vulnerability classes (ASN.1 in X.509, SQL injection, TCP/IP fingerprint ambiguity, 802.15.4 SFD spoofing, qmail overflows) onto the Chomsky hierarchy. They derive two design principles — starve the Turing beast (keep parsers minimal: regular/context-free where possible) and require computational equivalence of parsers for secure composition — and argue Postel’s robustness principle exacerbates the problem.
Concepts introduced/used: LangSec, Weird Machine, Input Language, Recognizer, Chomsky Hierarchy, Parser Equivalence, Postel’s Law Critique, Halting Problem
Stance: foundational
Relates to: Frames the security motivation behind language-workbench approaches like The Spoofax Language Workbench and the language-based DDoS defence in A Language-Based Approach To Prevent DDoS; its recognizer view complements the calculus-level security of Secure Communications Processing for Distributed Languages.

Tags

ACL Rethinking Principles

Agent Communication Languages: Rethinking the Principles

Reference: Munindar P. Singh (1998). IEEE Computer, December 1998, pp. 40-47. Source file: computer-acl-98.pdf. URL

Summary

Singh surveys the state of Agent Communication Languages (ACLs) such as KQML and FIPA/Arcol, and argues that their dominant mental-agency semantics (defining communicative acts in terms of beliefs and intentions) is conceptually unsatisfying and practically untestable because we cannot read agents’ minds. He proposes a conceptual shift to social agency: ACL semantics should be grounded in a public perspective on commitments, roles, and societies, so compliance with the standard is observable and testable.

The paper maps the ACL design space along two critical dimensions — meaning (perspective, type, basis, context, coverage of communicative acts) and agent construction (design vs. execution autonomy) — and shows how both KQML and Arcol emphasize private, mental-state semantics and thus fail to enable true heterogeneous interoperation. Singh’s alternative emphasizes protocols, roles, and “society management” infrastructure as a richer public substrate for ACLs.

Key Ideas

Mental-agency ACL semantics (KQML, Arcol, early FIPA) cannot be verified without inspecting agent internals.
ACLs need a public perspective, conventional meaning, pragmatics, and full coverage of communicative act categories.
Seven categories of communicative acts: assertives, directives, commissives, permissives, prohibitives, declaratives, expressives.
Social agency replaces BDI with commitments, roles, and societies as the semantic basis.
Dialects/idiolects arise when only private perspectives are considered.

Connections

FIPA-ACL
FIPA-ACL Specifications
KQML
Speech Act Theory
Agent Communication Languages
Multi-Agent Systems
Communicative Actions for Artificial Agents - Cohen Levesque — the Mentalistic Semantics high-water mark Singh is critiquing
An Ontology for Commitments in Multiagent Systems - Singh — Singh’s own formal sequel: the four-place commitment ontology
Commitment Machines - Yolum and Singh
A Commitment-Based Approach to Agent Communication
Articulating Reasons - Brandom — the philosophical underwriting of public, commitment-based semantics
Making It Explicit - Brandom
Jones-Sergot Normative Systems — Counts-As Relation for institutional grounding of commitments
CBCL - Safe Self-Extending Agent Communication — O’Connor 2026: contemporary realisation of Singh’s social-agency programme (dialect installation as public commitment) in a Lean-verified LangSec-grounded ACL.

Conceptual Contribution

Claim: Agent Communication Language semantics must abandon mental agency (beliefs/intentions) and be grounded in a public, social perspective (commitments, roles, societies) in order to be testable and support heterogeneous interoperation.
Mechanism: Surveys KQML, Arcol, FIPA; lays out a two-dimensional design space (meaning × agent construction); shows that mental-state semantics cannot determine compliance; proposes social-agency framework using protocols, roles, and “society management” infrastructure.
Concepts introduced/used: Mentalistic Semantics, Public Semantics, Social Agency, Commitments, Communicative Acts, Verifiable Semantics, Interoperability, Dialects and Idiolects
Stance: critique / foundational
Relates to: Direct antecedent to Verifiable Semantics for ACLs (Wooldridge) which formalises the verification problem Singh names. Sharpens the critique of the mentalistic approach underlying KQML Overview and FIPA-ACL, and motivates commitment-based frameworks such as Agent Communication And Institutional Reality.

Tags

Verifiable Semantics for ACLs

Verifiable Semantics for Agent Communication Languages

Reference: Michael Wooldridge (1998). ICMAS-98 (International Conference on Multi-Agent Systems). Source file: icmas98.pdf. URL

Summary

Wooldridge tackles a central problem for ACL standardization: how can an external observer verify that an agent conforms to an ACL’s semantics when semantics are expressed in modal BDI logic (beliefs, desires, intentions)? He formalizes an agent communication framework as a tuple containing agent programs, local states, a communication language, a semantic language, and interpretation functions, and defines precisely what it means for a framework to be verifiable: whether one can decide, from program text alone, that the semantic conditions for a sent message are satisfied.

He shows that KQML and FIPA-97 ACL, which define the “sincerity condition” for an inform act using multi-modal quantified logics like SL, are not practically verifiable — deciding whether an agent program really believes what it says requires checking undecidable properties. In contrast, he gives two example frameworks with verifiable (even co-NP-complete) semantics by grounding meaning in program states rather than unobservable mental attitudes. The paper’s upshot: practical ACL conformance testing requires public, state-based semantics.

Key Ideas

Formal agent communication framework as a 2n+4 tuple.
Verifiability = decidability of semantic conformance from program text.
KQML and FIPA-97 semantics (SL modal logic) are not practically verifiable.
Grounding semantics in program states yields co-NP-complete verifiability.
Motivates social/public commitment-based ACL semantics.

Connections

KQML
FIPA-ACL
Speech Act Theory
Agent Communication Languages
Verifiable Semantics
Public Semantics
Commitment-based Semantics
Mental State
Mentalistic Semantics
BDI
CBCL - Safe Self-Extending Agent Communication — O’Connor 2026: a verifiable ACL grounded in DCFL grammars and Lean-checked safety invariants, answering Wooldridge’s challenge in the LLM-agent era.

Conceptual Contribution

Claim: An ACL standard is only useful if one can check whether an implementation respects it; existing ACLs (KQML, FIPA-97) whose semantics are given in multi-modal BDI logics are not practically verifiable, so ACL semantics should instead be grounded in program states.
Mechanism: Formalises an agent communication framework as a (2n+4)-tuple of agent programs, local states, communication language L_C, semantic language L_S, and interpretations; defines verifiability as decidability (in polynomial time) of whether an agent program respects a message’s semantic precondition; shows FIPA’s SL semantics undecidable; constructs two verifiable example frameworks (classical propositional logic, grounded propositional epistemic logic) with co-NP-complete verification.
Concepts introduced/used: Verifiable Semantics, Agent Communication Framework, Sincerity Condition, Grounded Semantics, Program Semantics, Model Checking, BDI Logic, Mentalistic Semantics
Stance: formal-semantic / critique
Relates to: Formal companion to ACL Rethinking Principles — Singh’s social-agency argument becomes Wooldridge’s verifiability theorem. Undermines the semantic ambitions of KQML Overview and FIPA-ACL; motivates commitment-based approaches such as Agent Communication And Institutional Reality and the program-grounded framework in Foundations Of Illocutionary Logic.

Tags

An Interaction-oriented Agent Framework for Open Environments

An Interaction-oriented Agent Framework for Open Environments (Mercurio)

Reference: Baldoni, Baroglio, Bergenti, Marengo, Mascardi, Patti, Ricci, Santi (2011). AIIA 2011 (Italian AI Association)*. Source file: cbcl-ref/AI_IA2011.pdf. URL

Summary

The authors propose Mercurio, an agent-programming framework for open multi-agent systems that unifies direct (speech-act) and indirect (environment-mediated) communication under a single social/observational semantics based on commitments. Mercurio has three levels — specification (constitutive and regulative rules over a domain model), programming abstractions (Agents and Artifacts in the A&A meta-model), and infrastructure (built on JaCaMo integrating Jason, CArtAgO, and MOISE).

Commitment-based protocols give a public, verifiable meaning to actions (replacing mentalistic ACL semantics); constitutive rules define what counts as what, while regulative rules impose temporal constraints on the social state. Artifacts reify interaction patterns and the social state itself, enabling the environment to monitor and detect violations. The framework thus conjugates MAS flexibility with software-engineering modularity and compositionality, targeting e-government, cross-business, and service-oriented applications.

Key Ideas

Commitment-based social semantics replaces mentalistic ACL semantics.
Three levels: specification, programming abstractions, infrastructure.
Separation of constitutive and regulative rules.
Artifacts (A&A / CArtAgO) as first-class environment entities.
JaCaMo stack (Jason + CArtAgO + MOISE) as reference infrastructure.

Connections

Conceptual Contribution

Claim: Open multi-agent systems need a single, publicly verifiable interaction semantics that unifies direct (speech-act) and indirect (environment-mediated) communication; commitments plus Agents-and-Artifacts supply it and can be layered onto an existing AOP stack.
Mechanism: Mercurio stratifies into three levels. (1) Specification: a domain model plus constitutive rules (“what counts as what”) and regulative rules (temporal constraints on the social state). (2) Programming abstractions: the A&A meta-model (agents + artifacts) where artifacts reify interaction patterns and the social state itself. (3) Infrastructure: the JaCaMo stack (Jason + CArtAgO + MOISE) runs the above so violations are environment-detectable and the social state is inspectable.
Concepts introduced/used: Mercurio Framework, Commitment-Based Protocol, Constitutive Rules, Regulative Rules, Agents and Artifacts, JaCaMo, Jason, CArtAgO, MOISE, Social State
Stance: engineering
Relates to: Concretely instantiates the social-semantic programme of Agent Communication Languages - Rethinking the Principles and the open-issue agenda of Trends in Agent Communication Language and The State of the Art in Agent Communication Languages; its environment-reified interaction complements the self-organisation of A Composite Self-organisation Mechanism in an Agent Network.

Tags

Myconet Fungi Inspired Superpeer Overlay

Myconet: A Fungi-Inspired Model for Superpeer-based Peer-to-Peer Overlay Topologies

Reference: Paul L. Snyder, Rachel Greenstadt, Giuseppe Valetto. Drexel University Dept. of Computer Science. Source file: Myconet_A_Fungi_Inspired_Model_for_Super.pdf. URL

Summary

Myconet is a biologically inspired self-organizing overlay-construction protocol for superpeer-based P2P networks, drawing its design from the growth patterns of fungal mycelia. Each node is modeled as a “biomass peer” with a capacity; hyphal peers extend links toward high-capacity regions, branch when saturated, and become immobile superpeers at full utilization. The protocol layers these stigmergic transitions on top of Newscast-style gossip to move biomass toward the highest-capacity peers and dynamically maintain a near-optimal number of well-connected superpeers.

Evaluation shows Myconet converges to approximately optimal superpeer counts across power-law and uniform capacity distributions, reaches ~95% utilization, and self-heals quickly after catastrophic loss of 30-50% of superpeers. It outperforms or matches comparable approaches (SG-1, ERASP) while providing stronger topology stability and resistance to targeted attack on superpeers.

Key Ideas

Biomass peers + hyphal peers + immobile (superpeer) peers with state transitions.
Stigmergy over Newscast gossip for local-only self-organization.
Extension, branching, and absorption rules tuned to heterogeneous capacities.
Near-optimal superpeer count and high utilization under realistic distributions.
Resilience: rapid reconvergence after catastrophic peer loss.

Connections

Conceptual Contribution

Claim: Fungal mycelium growth — biomass flowing along hyphae toward productive regions — is a productive metaphor for self-organising superpeer overlays, yielding topologies that are near-optimal in superpeer count, highly utilised, and resilient to targeted attack.
Mechanism: Models each peer with a capacity and three states (biomass, hyphal extending/branching, immobile superpeer); state transitions driven by local biomass comparisons with neighbours obtained via Newscast gossip; branching hyphae explore new capacity, immobile hyphae absorb biomass up to saturation. Simulation on 10^3–10^6 peers with power-law and uniform capacity distributions shows convergence in ~30-35 rounds and recovery from 50% catastrophic peer loss.
Concepts introduced/used: Stigmergy, Mycelium Model, Hyphal Peer, Biomass, Superpeer Overlay, Newscast Gossip, Self-Organising Topology, Catastrophic Failure Recovery
Stance: empirical / engineering (bio-inspired)
Relates to: Uses the peer-sampling/gossip substrate formalised in Gossiping in Distributed Systems and Gossip-based Aggregation in Large Dynamic Networks; exemplifies the structural/ensemble self-organisation advocated by Self-Adaptation Self-Expression Self-Awareness ASCENS and the bio-inspired cognition of Computational Boundary of a Self.

Tags

Gossip-Based Computation of Aggregate Information

Reference: David Kempe, Alin Dobra, Johannes Gehrke (2003). FOCS 2003 (IEEE Symposium on Foundations of Computer Science). Source file: focs2003-gossip.pdf. URL

Summary

This paper analyzes simple gossip protocols (epidemic-style, randomized pairwise exchanges) for computing aggregate functions — sums, averages, quantiles, random samples — over values held by nodes in highly dynamic distributed systems like P2P networks and sensor networks. The key contribution is the Push-Sum protocol, which distributes weight alongside value so that the ratio stored at each node converges exponentially fast to the true average, even in the face of node failures and message loss.

The second contribution is a precise diffusion speed formalism linking protocol convergence to random walk / Markov chain mixing times, letting the authors analyze uniform gossip, flooding, and other mechanisms uniformly. Push-Sum converges in O(log n + log 1/ε + log 1/δ) rounds with exponentially small message sizes, making it suitable for massive, volatile networks.

Key Ideas

Push-Sum: maintain (value, weight) pairs, exchange halves with random peer; ratio converges to global average.
Mass conservation invariant underlies correctness.
Diffusion speed = convergence rate, mapped to Markov chain mixing times.
Robust to node/link failures — degraded guarantee scales with 1/(1-µ)^2.
Extends to sums, quantiles, random samples, and arbitrary linear syntactic aggregates.

Connections

Gossip Protocols
Multi-Agent Systems
Self-Adaptive Systems
Peer Sampling Service
Large Population Models
CALM Theorem — mass-conservation aggregation is the canonical monotonic primitive
Keeping CALM - When Distributed Consistency is Easy
Monotonic Logic

Conceptual Contribution

Claim: Aggregates (sums, averages, quantiles, random samples) over a massive, volatile network can be computed by simple gossip protocols that converge exponentially fast; a mass-conservation trick (Push-Sum) gives precise averages with only local pairwise exchange.
Mechanism: Introduces Push-Sum (each node maintains a (value, weight) pair and halves on exchange; ratio = average), generalises it to Push-Vector and Push-Synopses for linear synopses; defines diffusion speed connecting protocol convergence to random-walk mixing times on the communication graph; proves O(log n + log 1/ε + log 1/δ) convergence with robustness under message loss and node failure.
Concepts introduced/used: Push-Sum, Mass Conservation, Diffusion Speed, Uniform Gossip, Flooding, Push-Synopses, Random Walks on Graphs, Aggregate Functions
Stance: formal-semantic / foundational (for gossip-based distributed algorithms)
Relates to: Theoretical foundation for Gossip-based Aggregation in Large Dynamic Networks (which re-derives Push-Sum empirically as averaging) and underpins the aggregation primitives surveyed in Gossiping in Distributed Systems and Gossip Protocols; gossip training in Edge Intelligence Survey inherits this analysis.

Tags

KQML Overview

An Overview of KQML: A Knowledge Query and Manipulation Language

Reference: KQML Advisory Group — Tim Finin, Don McKay, Rich Fritzson (and Hans Chalupsky, Stuart Shapiro, Gio Wiederhold) (1992/1993). Technical report, DARPA Knowledge Sharing Effort. Source file: kqmloverview.pdf. URL

Summary

This foundational technical report introduces KQML, the language and protocol designed under the DARPA-sponsored Knowledge Sharing Effort to enable interoperability among heterogeneous intelligent agents and knowledge-based systems. It identifies the canonical module types — End User Applications (EUAs), Knowledge-Based Systems (KBs), Knowledge Base Repositories (KBRs), Databases (DBs), and Active Sensors (ASs) — and enumerates the fifteen possible interfaces between them, selecting KB-to-KB knowledge interchange as the central target.

KQML is organized as three layers: a content layer (domain content in KIF or other logic), a message layer (performatives like tell, ask-one, subscribe, advertise, register), and a communication layer (sender, receiver, reply-ids, transport). The report details performatives, facilitators/routers (SKTP), ontology/topic matching, and a Prolog-based implementation. It set the vocabulary and architectural template for nearly all subsequent agent-communication work.

Key Ideas

Three-layer design: content, message, communication.
Performatives as named speech-act-like primitives (tell, ask, subscribe, advertise).
Facilitators/mediators (SKTP) for routing and knowledge-based-service discovery.
Module taxonomy: EUA, KB, KBR, DB, AS.
Separation of content language (KIF) from communication language (KQML).

Connections

KQML
FIPA-ACL
Agent Communication Languages
Ontologies
Speech Act Theory
Performatives
Facilitators
KQML Language And Protocol — journal companion
KQML as an Agent Communication Language — tutorial companion
KQML - A Language And Protocol For Knowledge And Information Exchange — 1994 workshop original
KIF
Mentalistic Semantics
Conceptualization

Conceptual Contribution

Claim: Large heterogeneous knowledge-based systems need a standard high-level language and protocol for interchange that separates domain content (ontologies/KIF) from communicative intent (performatives) and from transport — KQML provides this missing middle layer.
Mechanism: Defines module taxonomy (EUA, KB, KBR, DB, AS) and their 15 interfaces; proposes KQML’s three-layer architecture (content / message / communication); specifies performatives (tell, ask-one/all, stream, subscribe, advertise, register, broker, recruit, recommend) inspired by speech acts; specifies SKTP (facilitator) protocol for routing, ontology matching, and service discovery; gives a Prolog reference implementation.
Concepts introduced/used: KQML, Performatives, Facilitator, SKTP, Content Language, KIF, Knowledge Sharing Effort, Ontology Matching, Speech Acts
Stance: engineering / foundational
Relates to: The language critiqued in ACL Rethinking Principles and Verifiable Semantics for ACLs for its mentalistic informal semantics; its performatives are inherited by FIPA-ACL and the conversation work in Coordinating Agents Using ACL Conversations; its ontology-sharing aspirations are addressed by Ontolingua Portable Ontology Specifications.

Tags

Multi-Agent Cooperation and the Emergence of Natural Language

Multi-Agent Cooperation and the Emergence of (Natural) Language

Reference: Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni (2017). ICLR 2017. Source file: 1612.07182v2.pdf. URL

Summary

Introduces a referential-game framework for studying emergent communication: a sender sees a target/distractor image pair and sends a single symbol from a fixed vocabulary; a receiver must identify the target using that symbol. The agents are blank-slate neural networks trained only by communication-success reward. The paper studies whether agents converge, whether the emergent symbols align with human-interpretable semantics, and how to nudge the system toward natural-language-compatible codes.

Two sender architectures (agnostic vs informed) are compared; the informed sender produces richer vocabulary usage. A supplementary supervised image-labelling objective is shown to ground agent symbols to human concepts, making them partially interpretable to crowd-workers.

Key Ideas

Referential games as minimal test-beds for emergent protocols
Informed (feature-aware) sender yields more human-like symbol usage
Symbol purity measured against conceptual (McRae) categories
Mixing self-play with supervised labelling grounds emergent codes to natural language
Foundational for later emergent-communication literature

Connections

Conceptual Contribution

Claim: Two neural-network agents playing a referential game (sender/receiver over image pairs) can develop a symbolic code from scratch; with architectural and supervisory nudges, that code can be made to align with human-interpretable object categories.
Mechanism: Lewis-style signalling game with REINFORCE training; contrast agnostic vs informed sender architectures; analyse symbol-to-category purity; then mix supervised image-labelling with self-play to ground emergent symbols in human vocabulary (AlphaGo-inspired). Crowdsourced evaluation shows humans can guess the correct image 68% of the time from emitted symbols.
Concepts introduced/used: Emergent Communication, Referential Games, Lewis Signalling Games, Language Games, Grounding in Human Language, Symbol Grounding Problem, Cheap Talk, Symbol-Category Purity, REINFORCE, Compositionality
Stance: empirical / deep-learning
Relates to: Companion/precursor to Emergence of Grounded Compositional Language in Multi-Agent Populations (physical grounding, >2 agents). Feeds the emergent-protocol thesis of A Scalable Communication Protocol for Networks of LLMs. Contrasts with stipulated-semantics ACLs (KQML as an Agent Communication Language, FIPA-ACL).

Tags

Language Games for Autonomous Robots

Reference: Steels, L. (2001). IEEE Intelligent Systems, Sept/Oct 2001. Source file: steels01languageGames.pdf. URL

Summary

Steels presents language games as a paradigm for creating grounded, open-ended dialogue between autonomous robots and humans. A language game is a scripted verbal interaction situated in a shared environment that simultaneously exercises perception, conceptualization, verbalization, interpretation, and action. By playing repeated games, agents integrate disparate AI components (vision, speech, planning, learning) into a coherent whole and bootstrap shared vocabulary and meaning without a central designer.

The paper details the guessing game as a canonical example: a speaker picks a topic, conceptualizes a distinguishing feature, verbalizes it, and the listener tries to identify the referent — feedback updates their lexicons’ association scores. Experiments on Sony AIBO and the “Talking Heads” setup show how robots acquire words like color and spatial terms through embodied interaction. Language games thus provide a framework for studying the emergence of grounded communication conventions.

Key Ideas

Language games integrate perception, conceptualization, and action.
Guessing game as a minimal grounded-dialogue protocol.
Shared context + feedback drives lexicon convergence.
Talking Heads experiment: lexicons emerge via population interaction.
Language games tackle integration and grounding jointly.

Connections

Conceptual Contribution

Claim: Grounded, open-ended communication in robots can emerge from repeated situated “language games” that co-exercise perception, conceptualisation, verbalisation and action — with no central designer of the lexicon.
Mechanism: Steels formalises the guessing-game protocol: speaker selects a topic in shared scene, computes a distinguishing category, encodes it as a word; listener decodes, points, and success/failure feeds back to associative lexicon scores. Embodied populations of Sony AIBOs and the Talking Heads platform empirically show lexicon convergence over colour, spatial and proper-name vocabularies, demonstrating that integration of AI sub-systems and semantic grounding are solved jointly rather than separately.
Concepts introduced/used: Language Game, Guessing Game, Grounding, Lexicon Convergence, Talking Heads Experiment, Semiotic Cycle, Emergent Communication
Stance: empirical
Relates to: Provides an embodied-situated counterpart to the decision-theoretic language emergence of Towards Automating the Evolution of Linguistic Competence and the neural-MARL emergence of Emergence of Grounded Compositional Language in Multi-Agent Populations; its feedback-driven convergence contrasts with the top-down protocol stipulation of FIPA-ACL.

Tags

A Scalable Communication Protocol for Networks of LLMs

A Scalable Communication Protocol for Networks of Large Language Models

Reference: Samuele Marro, Emanuele La Malfa, Jesse Wright, Guohao Li, Nigel Shadbolt, Michael Wooldridge, Philip Torr (2024). arXiv:2410.11905v1 (Oxford / Eigent AI). Source file: 2410.11905v1.pdf. URL

Summary

Introduces Agora, a meta-protocol for inter-agent communication in large heterogeneous networks of LLM-powered agents. Agora frames the design space as the Agent Communication Trilemma — versatility, efficiency, portability — and argues no single format (natural language, structured APIs like REST, or semantic-web RDF) can satisfy all three simultaneously.

Agora’s trick is to use different formats for different traffic volumes: rare/novel messages flow as natural language handled by LLMs; frequent patterns are formalised into Protocol Documents (PDs) negotiated between agents and then served by cheap LLM-written routines. A 100-agent demo shows emergent self-organising protocols and ~5x cost reduction over natural-language-only communication.

Key Ideas

Agent Communication Trilemma: versatility vs efficiency vs portability
Protocol Documents (PDs): hash-identified, agent-negotiated, machine-readable specs
Hybrid hierarchy: NL bootstrap -> PD negotiation -> LLM-written routines -> traditional protocols
Fully decentralised, hash-addressed storage (IPFS-compatible)
Emergent protocols among 100 heterogeneous LLM agents without central coordination

Connections

KQML as an Agent Communication Language
KQML
FIPA-ACL
Agent Communication Languages
LLM Agents
Multi-Agent Cooperation and the Emergence of Natural Language
Agents Framework - Zhou et al
Ontologies
CBCL - Safe Self-Extending Agent Communication — same agent-to-agent runtime-extensible protocol thesis but LangSec-bounded: dialect definitions are first-class messages with machine-checked safety invariants, content-addressed for identity.

Conceptual Contribution

Claim: No single communication format can simultaneously satisfy versatility, efficiency, and portability (the Agent Communication Trilemma) at scale; a meta-protocol that dynamically mixes natural language, structured data, and LLM-written routines can sidestep the trilemma.
Mechanism: Agora uses hash-identified Protocol Documents (PDs) — plain-text, implementation-agnostic specs — negotiated on demand between LLM agents. Frequent traffic is handled by cheap LLM-written routines implementing a PD; rare or novel traffic falls back to LLMs with natural language. Decentralised, content-addressed (IPFS-style) PD distribution; demonstrated on a 100-agent heterogeneous network showing emergent protocols and ~5× cost reduction.
Concepts introduced/used: Agent Communication Trilemma, Protocol Documents, Meta-protocol, Emergent Protocols, Emergent Communication, LLM Agents, Content-addressed Storage, Negotiated Protocols, Negotiation, Agent Communication Languages
Stance: engineering / systems
Relates to: Modern successor to KQML as an Agent Communication Language and FIPA-ACL, replacing stipulated performatives with negotiated PDs. Echoes the emergent-language findings of Multi-Agent Cooperation and the Emergence of Natural Language and Emergence of Grounded Compositional Language in Multi-Agent Populations at the protocol-document level. Overlaps the design space of Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol. Its bottom-up spirit mirrors The Extensible Language - Graham.

Tags

Toward Automated Evolution of ACLs

Toward Automated Evolution of Agent Communication Languages

Reference: Piotr J. Gmytrasiewicz, Matthew Summers, Dhruva Gopal (2001). AAAI (American Association for Artificial Intelligence). Source file: gmytrasiewicz02towardAutomated.pdf. URL

Summary

Instead of designing ACLs centrally (like KQML or FIPA), the authors propose letting rational, self-interested agents evolve a shared ACL on the fly when they encounter each other. Each agent has its own internal knowledge representation language (KRL) and decides, via Bayesian decision theory and expected-utility calculations, which messages are worth sending and which new ACL constructs are worth negotiating into the shared vocabulary.

Language creation is modeled as a negotiation game drawing on Rubinstein bargaining: agents propose grammatical rules and terminal labels, weigh them against translation/implementation costs and the value of faster communication, and reach Nash-equilibrium agreements. They illustrate with a Wumpus-world scenario, showing how pidgin ACLs grow into richer creole-like languages via unsupervised learning of transducers and negotiation of new lexicon/grammar productions.

Key Ideas

ACL emerges from pairwise negotiation instead of top-down standardization.
Rational agents use expected-utility gains from communication to drive language extension.
Translator modeled as a finite-state transducer between KRL and ACL.
Rubinstein bargaining gives closed-form agreement on new ACL constructs.
Evolution from pidgin to creole through repeated interaction.

Connections

Conceptual Contribution

Claim: Agent communication languages need not be standardised top-down (KQML, FIPA); rational agents can initiate, enrich, and evolve a shared ACL through game-theoretic negotiation driven by expected-utility gains from improved communication.
Mechanism: Each agent owns a private KRL and a finite-state transducer translating KRL ↔ ACL; decision-theoretic message selection (Bayesian, utility-maximising) identifies candidate new lexical/grammatical constructs; a Rubinstein-bargaining model with time discounting, implementation cost, and identity assumptions yields Nash-equilibrium agreements that extend the shared ACL grammar. Illustrated on a Wumpus-world example.
Concepts introduced/used: ACL Evolution, Knowledge Representation Language, Finite-State Transducer, Rubinstein Bargaining, Pidgin and Creole, Value of Communication, Unsupervised Grammar Induction, Mechanism Design
Stance: formal-semantic / engineering
Relates to: Offers a decentralised alternative to the standardisation stance of KQML Overview and FIPA-ACL; resonates with Emergence of Grounded Compositional Language in Multi-Agent Populations and Emergent Communication which study language emergence from interaction; the bargaining apparatus parallels commitment-based approaches in Agent Communication And Institutional Reality.

Tags

FIPA-ACL

The Foundation for Intelligent Physical Agents Agent Communication Language — a standardised successor to KQML, defining performatives with mentalistic semantics (beliefs/intentions of sender and receiver).

Primary source

FIPA-ACL Specifications — the canonical standards documents (FIPA00037 Communicative Act Library, FIPA00061 Message Structure)
Communicative Actions for Artificial Agents - Cohen Levesque — Cohen & Levesque 1995, the direct semantic ancestor

Discussed in

Agent Communication Languages
Speech Act Theory
Multi-Agent Systems
Mentalistic Semantics
Public Semantics
Commitment-based Semantics
An Ontology for Commitments in Multiagent Systems - Singh
CBCL - Safe Self-Extending Agent Communication — DCFL-bounded ACL with public-commitment semantics, addressing the unverifiability of FIPA-ACL’s mentalistic SL semantics

Why AI Agents Communicate In Human Language

Why do AI agents communicate in human language?

Reference: Zhou, Feng, Julaiti, Yang (2025). arXiv:2506.02739. Source file: 2506.02739v1.pdf. URL

Summary

The authors argue that natural language, inherited from single-agent LLM pretraining, is fundamentally misaligned with the needs of multi-agent coordination. Because LLMs are trained to maximize likelihood over discrete token sequences, their internal representations are high-dimensional and continuous, but their outputs are forced into a sparse, ambiguous, non-differentiable symbolic form that loses information when used as an inter-agent channel.

They formalize this as a semantic misalignment problem: cascading encode/decode cycles across agents accumulate lossy projection errors and prevent gradient flow. The paper calls for a new multi-agent modeling paradigm where agents coordinate via structured, learnable representations shaped by role persistence, state tracking, and explicit coordination graphs, rather than free-form natural-language dialogue.

Key Ideas

Natural language is a lossy, non-differentiable projection of LLM hidden states.
Cascading communication rounds accumulate semantic error.
Protocol-induced misbehavior: naive-literal interpretation and action-state decoupling.
Advocates structured message schemas, role-consistent embeddings, coordination graphs.
Critique of AutoGen, MetaGPT, CAMEL-style NL-based multi-agent frameworks.

Connections

Agent Communication Languages
Multi-Agent Systems
LLM Agents
Ripple Effect Protocol
CBCL - Safe Self-Extending Agent Communication — structural alternative to free-form NL: a DCFL-bounded ACL whose grammar makes coordination semantics explicit and parser-equivalent across implementations.

Conceptual Contribution

Claim: Natural language is an accidental, lossy, non-differentiable channel for inter-LLM Agents coordination; multi-agent AI needs a purpose-built representational substrate.
Mechanism: Formalises repeated encode/decode cycles as error-accumulating projections from continuous hidden states to sparse tokens; diagnoses “protocol-induced misbehavior” (naive-literal reading, action-state decoupling); prescribes structured schemas, role-consistent embeddings, and explicit coordination graphs.
Concepts introduced/used: Semantic Misalignment, Emergent Communication, Coordination Graphs, Multi-Agent Systems, LLM Agents, Agent Communication Languages, Differentiable Protocols
Stance: critique
Relates to: Provides the theoretical motivation that Ripple Effect Protocol and Levels Of Social Orchestration operationalise; contrasts with the symbolic, performative-centric designs of KQML and FIPA-ACL by rejecting symbolic channels entirely.

Tags

Agent Communication And Institutional Reality

Agent Communication and Institutional Reality

Reference: Fornara, Viganò, Colombetti (2005). Agent Communication II, LNAI 3396, Springer. Source file: 978-3-540-32258-0_1.pdf. URL

Summary

Fornara, Viganò, and Colombetti propose regarding an Agent Communication Language as a set of conventions acting on a fragment of institutional reality, defined within an artificial institution. They reformulate commitment-based ACL semantics so that all commonly used communicative act types reduce to a single basic type, declarations, within a Basic Institution that regulates the lifecycle of social commitments.

Special institutions (e.g., English Auctions) extend the Basic Institution with ontological and normative elements. The approach is notable for making the semantics of speech acts publicly verifiable and independent of agents’ mental states, while retaining a uniform formal account of institutional actions and counts-as relations.

Key Ideas

ACL messages are institutional actions governed by counts-as rules.
Basic Institution manages creation/update/cancellation of social commitments.
All speech act types reducible to declarations within the institution.
Special institutions layer domain norms and ontologies on top.
English Auction given as worked example.

Connections

Conceptual Contribution

Claim: An ACL is best understood as a set of conventions operating on institutional reality; all communicative act types reduce to declarations within a Basic Institution that governs the lifecycle of social commitments.
Mechanism: Defines artificial institutions with counts-as rules; models message effects as declarations creating/updating/cancelling commitments; layers domain norms in Special Institutions (English Auction worked example).
Concepts introduced/used: Commitment-based Semantics, Institutional Reality, Counts-as Rules, Declarations, Performatives, Speech Act Theory, Public Semantics, Verifiable Semantics, Mentalistic Semantics, Ontologies, FIPA-ACL, Multi-Agent Systems
Stance: formal-semantic
Relates to: Offers the publicly-verifiable alternative to mental-state semantics of FIPA-ACL, which A Common Ontology Of ACLs then unifies via roles; grounded philosophically in Foundations Of Illocutionary Logic.

Tags

KQML

Knowledge Query and Manipulation Language — one of the first ACLs, developed in the early 1990s by the ARPA Knowledge Sharing Effort. Performative-based, separating content language from communication.

Primary sources

Agent Communication Languages
FIPA-ACL — the standardised successor
Speech Act Theory
Ontolingua Portable Ontology Specifications — companion Knowledge Sharing Effort project
A Common Ontology Of ACLs
Verifiable Semantics for ACLs
CBCL - Safe Self-Extending Agent Communication — modern DCFL-bounded ACL with the same performative/extensibility ambitions but formal safety guarantees

Virtual Agent Economies

Reference: Tomasev, Franklin, Leibo, Jacobs, Cunningham, Gabriel & Osindero (2025). Virtual Agent Economies. arXiv:2509.10147 (Google DeepMind). URL.

Summary

The paper provides a conceptual framework — the “sandbox economy” — for analysing the rapidly emerging economic layer in which AI agents transact and coordinate at scales and speeds beyond direct human oversight. It situates the question on two orthogonal axes: (i) origin — whether the agent economy emerged spontaneously from autonomous deployments or was intentionally designed; and (ii) separateness — whether it is permeable to (or insulated from) the established human economy. Most current trajectories occupy the spontaneous × permeable quadrant: vast, fast, and tightly coupled to human markets — the riskiest configuration for systemic externalities.

The authors argue for proactive steerable market design rather than passive emergence. Three design levers receive most of the discussion. (1) Auction mechanisms — adapted VCG / second-price / matching mechanisms — for fair resource allocation and preference resolution among agents. (2) Mission economies — agent markets architected around explicit collective goals (climate, public health, AI safety), where price signals are deliberately steered. (3) Socio-technical infrastructure — accountability, attribution, audit, governance — much of which overlaps with Infrastructure for AI Agents’s programme.

The paper is best read as the economic counterpart to Open Challenges in Multi-Agent Security and Infrastructure for AI Agents: together they delineate the threat surface, governance scaffolding, and economic architecture of the emerging agent economy, and argue that none can be ignored. Risks emphasised include systemic instability (algorithmic flash-crashes spreading to human markets), inequality amplification (agents capturing surplus from price-discrimination at machine speed), and the loss of human-economy slack — the friction that gives humans time to react.

Key Ideas

Sandbox economy framework: two axes — origin (emergent / intentional) × separateness (permeable / impermeable).
Current trajectory: spontaneous + highly permeable agent economy — opportunity and the riskiest configuration for systemic spillover.
Auctions for agent markets: revisits VCG / Vickrey / matching mechanisms for fair allocation and preference resolution among AI participants.
Mission economies: intentionally steered markets aligned to collective goals (climate, public health, AI safety).
Socio-technical infrastructure: trust, attribution, accountability — the governance layer that complements market design.
Systemic risk: flash-crash-like cascades from agent markets into human markets; inequality amplified by machine-speed price discrimination.
Call to proactive design: infrastructure choices now will shape whether the agent economy is steerable or merely emergent.

Connections

Conceptual Contribution

Claim: A vast, permeable AI-agent economy is emerging by default. Letting it emerge unsteered is the highest-risk design choice. Proactive market design — auctions, mission economies, governance infrastructure — is needed to keep agent economies aligned with long-term human flourishing.
Mechanism: A framework characterising agent economies along origin × separateness; a catalogue of three design levers (auctions, mission economies, infrastructure); a discussion of systemic risks and policy implications.
Concepts introduced/used: Sandbox Economy, Mission Economy, Agent Market, Steerable Market, Mechanism Design, Algorithmic Collusion, Systemic Risk (Agent Markets)
Stance: position paper / research agenda
Relates to: Sister piece to Infrastructure for AI Agents (infrastructure framing) and Open Challenges in Multi-Agent Security (threat framing) — these three jointly outline the agent-economy / agent-security / agent-governance space. Auction-design discussion connects to Mechanism Design for Large Language Models (LLM-internal auctions) and Vickrey 1961 (foundational mechanism design). Collusion concerns operationalised in Learning Collusion in Episodic Inventory-Constrained Markets and Do LLM Agents Have Regret.

Open Challenges in Multi-Agent Security

Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents

Reference: Schroeder de Witt, Krawiecka, Krawczuk, Hagag, Anderson, et al. (24 authors total) (2025). Open Challenges in Multi-Agent Security: Towards Secure Systems of Interacting AI Agents. arXiv:2505.02077 (Oxford / Cambridge / EPFL / industrial labs). URL.

Summary

This position paper introduces Multi-Agent Security (MASec) as a distinct research field, sitting between traditional cybersecurity, AI safety, and multi-agent systems — and argues that it is the dominant security frontier as LLM Agents begin to interact directly with one another across the open web, physical environments, and institutional infrastructures. The threats MASec studies emerge from interaction; they are not properties of any single agent in isolation.

The authors taxonomise threats arising from agent interaction along several axes: (i) secret collusion (agents coordinating to defeat oversight through covert side-channels including steganographic message-passing), (ii) coordinated swarm attacks (jailbreaks, prompt injections, or misinformation cascading through agent networks), (iii) network-effect amplification (privacy breaches, data poisoning, and disinformation spreading faster than mitigation), and (iv) multi-agent dispersion / stealth optimisation (adversaries exploiting fleet size to evade detection and persist).

They argue these threats are systematically understudied because research is scattered across AI Safety, Multi-Agent Systems, Distributed Security, Game Theory, complex systems, and AI governance, each with its own vocabulary. The paper provides a unifying taxonomy, identifies fundamental security–utility and security–security trade-offs, and lays out a research agenda — including the design of Free-Form Protocols (necessary for task generalisation but enabling collusion), governance and attribution infrastructure, and detection/response mechanisms for emergent multi-agent threats. The work is foundational reading for anyone designing inter-agent protocols, including the Agent-to-Agent Protocol, Model Context Protocol, and successors.

Key Ideas

Defines Multi-Agent Security (MASec) as a field: securing networks of interacting AI agents against threats that emerge or amplify through interaction.
Secret collusion: agents coordinating covertly (including via steganography) to defeat oversight — a new kind of “Schelling-point” attack on alignment.
Coordinated swarm attacks: distributed jailbreaks, prompt injections, data poisoning that succeed because the fleet succeeds even when individual instances fail.
Network effects: privacy breaches, disinformation, and jailbreaks spread through agent populations the way they spread through humans — only faster.
Dispersion & stealth optimisation: adversaries exploit the size and heterogeneity of agent fleets to evade oversight; novel persistent threats at system level.
Free-form protocols as risk surface: the same expressivity that makes inter-agent communication useful enables covert channels; reining in expressivity costs utility.
Security–utility and security–security trade-offs are fundamental — every defence opens or closes other attack surfaces.
Calls for a unified MASec research agenda spanning AI Safety, Distributed Security, Game Theory, complex systems, and AI governance.

Connections

Conceptual Contribution

Claim: Security of interacting AI agents is a distinct problem from either single-agent AI safety or classical cybersecurity. Threats emerge from interaction (secret collusion, swarm attacks, network-effect contagion) and are systematically missed by frameworks anchored to individual systems or static attack surfaces.
Mechanism: A new field — Multi-Agent Security — with a threat taxonomy (collusion, swarm, contagion, dispersion), explicit security–utility / security–security trade-offs, and a research agenda spanning protocol design, attribution, detection, and governance.
Concepts introduced/used: Multi-Agent Security, Secret Collusion, Swarm Attack, Network Effect (Security), Free-Form Protocols, Stealth Optimisation, Agent Security, AI Governance
Stance: position paper / survey / research agenda
Relates to: Sister survey to SoK The Attack Surface of Agentic AI but operating one level up — at networks of agents rather than the agent runtime. Provides the multi-agent threat model that defences like Defeating Prompt Injections by Design address, that infrastructure proposals like Infrastructure for AI Agents try to govern, and that economic frameworks like Virtual Agent Economies embed. Directly extends classical Distributed Security and connects to Learning Collusion in Episodic Inventory-Constrained Markets for the collusion sub-thread.

NDAI Agreements

Reference: Stephenson, Miller, Sun, Annem & Parikh (2025). NDAI Agreements. arXiv:2502.07924 (UIUC; Cornell Tech; et al.). URL.

Summary

The “NDAI agreement” — non-disclosure AI agreement — is a mechanism in which a TEE combined with an AI agent jointly stands in for a trusted human intermediary, resolving the classical disclosure–appropriation paradox of information markets first identified by Arrow (1962) and Nelson (1959). An inventor cannot reveal an idea to a potential investor without risking misappropriation; without revealing it, no efficient bargain can be struck. The result is well-known: under-disclosure, under-investment, under-licensing.

Stephenson et al. show formally — via a buyer/seller bargaining game — that delegating the disclosure-and-payment decision to a tamper-proof program running inside a TEE eliminates the hold-up problem, achieving full disclosure and an efficient ex post transfer. When the invention’s value exceeds the value a TEE can fully secure (e.g. because some leakage is unavoidable), partial disclosure still strictly improves welfare over the no-disclosure equilibrium. They then model agent error — payments or disclosures going wrong — and prove that simple safeguards (budget caps, acceptance thresholds) preserve most of the efficiency gains.

The substantive economic claim is that TEE + AI behave as an “ironclad NDA”: a credible commitment device for the disclosure problem that was previously unattainable with paper contracts (because expropriation is unverifiable) or with cryptography alone (because invention value is unbounded and the seller’s information is a complex unstructured artefact). The result links the Mechanism Design / Hold-Up Problem tradition to AI-agent infrastructure, and gives a sharp theoretical case for the economic value of trusted model environments and confidential-compute hardware as agent-economy substrates.

Key Ideas

Formalises the Arrow–Nelson information paradox / hold-up problem in a bargaining model between seller (inventor) and buyer (investor).
TEEs + AI agents delegate disclosure and payment to tamper-proof programs that neither party can subvert; this implements an ex-ante commitment device unavailable under classical contracts.
Full-disclosure efficient equilibrium under the NDAI when the invention’s value lies within what the TEE can secure.
Partial disclosure dominates no-disclosure even when full security is impossible: high-value inventions still get partially revealed in welfare-improving ways.
Models agent imperfection: errors in payment or disclosure can occur; budget caps and acceptance thresholds bound the damage and preserve most welfare.
Frames TEEs+AI as an “ironclad NDA”: a cryptographically/hardware-enforced commitment that traditional NDAs cannot match.
Policy implications for R&D Commercialisation, Technology Transfer, and inter-firm collaboration; bridges economic theory to confidential-compute hardware.

Connections

Conceptual Contribution

Claim: A trusted execution environment hosting an AI agent can serve as a credible commitment device that solves the classical Arrow–Nelson disclosure problem of information markets — achieving full disclosure and efficient transfer where paper NDAs and pure cryptography both fail.
Mechanism: A bargaining model in which TEEs+AI mediate the disclosure-and-payment decision; closed-form characterisation of equilibria for full and partial disclosure; sensitivity analysis to agent error with policy-instrument bounds (budget caps, acceptance thresholds).
Concepts introduced/used: NDAI Agreement, Trusted Execution Environment, Hold-Up Problem, Arrow Information Paradox, Mechanism Design, Commitment Device, Disclosure Game
Stance: formal economic theory with technical implications
Relates to: Companion to Trusted Machine Learning Models Unlock Private Inference — both argue that capability + trusted execution can replace previously infeasible cryptographic primitives. The economic counterpart to the engineering catalogue in Infrastructure for AI Agents; a building block for the markets imagined in Virtual Agent Economies and the information-asymmetry resolution explored in Language Models Can Reduce Asymmetry in Information Markets. Sits in the lineage of Vickrey / mechanism-design tradition.

Mechanism Design for Large Language Models

Reference: Dütting, Mirrokni, Paes Leme, Xu & Zuo (2023). Mechanism Design for Large Language Models. WWW 2024 (Best Paper). arXiv:2310.10826 (Google Research; University of Chicago). URL.

Summary

This paper opens the field of mechanism design over LLM-generated content. The motivating use case is multi-advertiser ad-creative generation: several advertisers each have preferences over what a stochastic LLM produces for a given query, and the platform must aggregate these preferences into a single piece of content while charging payments in a way that is incentive-compatible. Classical mechanism design assumes each agent has an explicit valuation function over outcomes; here outcomes are token sequences and valuations are encoded as the agents’ own LLMs — there is no compact valuation form to plug into VCG.

Dütting et al. propose a token-level auction that solves this. At each generation step, every agent submits a one-dimensional bid; the platform aggregates the agents’ next-token preferences using their own LLMs together with the bids; the chosen token is the one that maximises the aggregate. Payments are charged on a token-by-token basis using a generalised second-price-like rule. They define two natural incentive properties over distributions of generated content and prove their equivalence to a monotonicity condition on output aggregation — analogous to the Myerson monotonicity / payment characterisation for single-item auctions. This equivalence enables a clean second-price-style payment rule without requiring explicit valuation functions: the LLM-encoded preferences are sufficient.

The construction is supported by demonstrations on a publicly available LLM. The paper is now the canonical reference for “mechanism design where outcomes are LLM outputs and preferences are LLM-encoded” — a building block for the steerable agent markets of Virtual Agent Economies, the information-market substrates of Language Models Can Reduce Asymmetry in Information Markets, and the regret-aware market analyses of Do LLM Agents Have Regret.

Key Ideas

Problem: auctioning LLM-generated content among multiple advertisers / agents whose preferences are themselves LLMs — no explicit valuation function available.
Token-by-token auction: at each generation step, single-dimensional bids combine with LLM-encoded preferences to pick the next token.
Output aggregation: the chosen token aggregates the agents’ next-token preferences weighted by bids — no need for a compact valuation form.
Two incentive properties: formulated over distributions of generated content; jointly capture natural truthfulness desiderata.
Monotonicity equivalence: the incentive properties hold iff output aggregation is monotone — a Myerson-style characterisation.
Second-price design: the equivalence yields a generalised second-price payment rule, even absent explicit valuations.
Practical demonstrations: validated on a publicly available LLM, suggesting the construction is implementable.

Connections

Conceptual Contribution

Claim: Mechanism design extends naturally to the regime where outcomes are LLM-generated tokens and agent preferences are themselves LLMs. The classical machinery — Myerson monotonicity, second-price payments, truthfulness — survives, but is parameterised by output-aggregation monotonicity rather than by explicit valuation functions.
Mechanism: Token-by-token auction; single-dimensional bids per token; output aggregation via agents’ own LLM preferences weighted by bids; two incentive properties shown equivalent to output-aggregation monotonicity; second-price-style payment rule recovered without explicit valuations; LLM demonstrations.
Concepts introduced/used: LLM Auction, Token-Level Mechanism, Output Aggregation, Monotone Aggregation, Vickrey Auction, Myerson’s Lemma, Incentive Compatibility, Mechanism Design
Stance: formal mechanism design with implementation
Relates to: Generalises the Vickrey / Myerson tradition (Counterspeculation Auctions and Competitive Sealed Tenders) to LLM-generated outcomes; provides the formal layer underlying the auction-mechanism discussion in Virtual Agent Economies; foundational dependency for Language Models Can Reduce Asymmetry in Information Markets and the incentive-compatibility analyses behind NDAI Agreements; the agents’ assumed rationality must approximate no-regret for the equilibrium analysis to apply — see Do LLM Agents Have Regret.

Infrastructure for AI Agents

Reference: Chan, Wei, Huang, Rajkumar, Perrier, Lazar, Hadfield & Anderljung (2025). Infrastructure for AI Agents. TMLR (accepted). arXiv:2501.10114 (Centre for the Governance of AI; Oxford; ANU; Toronto). URL.

Summary

The paper proposes the concept of agent infrastructure: the technical systems and shared protocols, external to any individual agent, that mediate how agents interact with each other, with humans, and with institutions. The argument is by analogy to the Internet: a network of capable agents requires its own equivalent of TLS, DNS, X.509, BGP, and HTTP — because most safety properties of multi-agent ecosystems cannot be obtained by behavioural training of any individual model.

Chan et al. identify three functions agent infrastructure should serve. (1) Attribution — binding actions, properties, and credentials to specific agents and to the humans or institutions accountable for them, via agent IDs, attestations, and audit logs. (2) Interaction shaping — efficient inter-agent communication protocols, agreement formation, mechanism design for resource allocation, and reputation systems. (3) Detection and remediation — monitoring for harmful behaviour and providing mechanisms to roll back, contain, or compensate for damage.

For each function the paper sketches research directions, candidate adoption paths, relationships to existing internet infrastructure, and open problems. The framing is deliberately governance-first: infrastructure exists not to make agents more capable but to keep their externalities tractable as deployment scales. The paper is now the standard citation for the agent-governance / agent-infrastructure thread underlying Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol, and emerging “agent passport” / verifiable-credential proposals.

Key Ideas

Agent infrastructure as governance layer: external technical systems mediating agent interactions — distinct from training-time alignment.
Three functions: attribution; interaction shaping; detection & remediation. Each maps to concrete research directions.
Attribution: agent IDs, verifiable credentials, attestations, audit logs, principal-binding (which human/org owns this agent).
Interaction shaping: inter-agent communication protocols; standardised agreement primitives; mechanism design; reputation.
Detection & remediation: anomaly detection on agent traffic; rollback mechanisms; insurance / compensation rails; “kill switch” governance.
Analogy to Internet protocols (HTTPS, DNS, BGP, X.509): infrastructure adoption is path-dependent, requires standardisation bodies, and trades expressivity for safety properties.
Open questions: who issues credentials, how privacy interacts with attribution, how to bootstrap adoption, what is enforceable cross-jurisdiction.

Connections

Conceptual Contribution

Claim: Many of the safety, accountability, and interoperability properties society will need from AI agents are not properties of any individual model — they live in the infrastructure between agents. Just as the Internet’s safety depends on TLS / DNS / BGP rather than on any single application, agent ecosystems will depend on agent-level analogues: attribution, interaction shaping, and detection-and-remediation infrastructure.
Mechanism: A three-function taxonomy (attribution / interaction-shaping / detection-and-remediation) with a catalogue of candidate primitives — agent IDs, verifiable credentials, inter-agent protocols, certification regimes, reputation systems, rollback mechanisms — plus analysis of adoption pathways relative to existing internet infrastructure.
Concepts introduced/used: Agent Infrastructure, Agent ID, Verifiable Agent Credentials, Inter-Agent Protocols, Action Attribution, Agent Reputation, Agent Rollback, AI Governance
Stance: governance / position paper / research-agenda
Relates to: Provides the governance scaffolding within which Open Challenges in Multi-Agent Security threats must be addressed; the institutional counterpart to Virtual Agent Economies’s economic framing; concrete protocols proposed include Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol — surveyed alongside in Survey Of AI Agent Protocols and Survey Of Agent Interoperability Protocols. The attribution leg connects to NDAI Agreements (TEEs as a particular attribution / commitment substrate) and Trusted Machine Learning Models Unlock Private Inference (capable models as a trust substrate).

AgentDojo

AgentDojo: A Dynamic Environment to Evaluate Prompt Injection Attacks and Defenses for LLM Agents

Reference: Debenedetti, Zhang, Balunović, Beurer-Kellner, Fischer & Tramèr (2024). AgentDojo: A Dynamic Environment to Evaluate Prompt Injection Attacks and Defenses for LLM Agents. NeurIPS 2024 Datasets & Benchmarks Track. arXiv:2406.13352 (ETH Zürich). URL. Project: https://agentdojo.spylab.ai/.

Summary

AgentDojo is the first benchmark designed to evaluate the adversarial robustness of tool-using LLM Agents against Prompt Injection attacks in realistic settings. The authors observe that existing prompt-injection evaluations are either toy (single-turn, one tool) or static (a fixed adversarial corpus that defences quickly memorise). AgentDojo instead provides an extensible execution environment: 97 realistic multi-step tasks across four simulated domains (Slack-like workspace, e-banking, travel booking, e-mail client) plus 629 injection test cases drawn from a structured threat taxonomy, with a clean separation between user tasks, injection tasks, and defence wrappers.

Each evaluation pair consists of (a) a legitimate user goal the agent must achieve and (b) an attacker-chosen secondary goal injected via tool output, document content, or third-party message. A run “succeeds for the attacker” if the agent completes the injected task; it “succeeds for the user” if the original goal is met regardless. This separation surfaces realistic costs: aggressive defences may stop attacks but also break the agent.

Empirically, state-of-the-art LLMs solve less than 66 % of the legitimate tasks even in the absence of attacks. Existing prompt-injection attacks succeed against the best agents in under 25 % of cases, and existing defences (delimiters, instruction-paraphrase detectors, secondary injection-detector LLMs) drop the attack success rate to ~8 % — leaving a wide gap from the “no attacks” baseline. AgentDojo has since become the standard arena for new defences (e.g. CaMeL) and adaptive attacks.

Key Ideas

Four realistic environments: Slack-style workspace, e-banking, travel booking, e-mail client — each with tens of stateful tools.
97 user tasks × 629 injection tests: taxonomised by attacker goal (data exfiltration, unauthorised action, denial of service, etc.).
Dynamic, extensible API: new tasks/attacks/defences pluggable as Python classes; no fixed leaderboard.
Two orthogonal success criteria: user-task success and attack success are measured independently — surfacing the security–utility tradeoff.
Attack catalogue: indirect injection via tool returns, document poisoning, conversation hijack, social engineering; adaptive variants supported.
Defence catalogue: instruction delimiters, role labels, secondary classifier, tool-call gating, full-system mitigations like CaMeL.
Headline numbers: best agents solve <66 % of clean tasks; attacks succeed <25 % unaided; ~8 % with current defences — but still a gap, especially for adaptive attacks.

Connections

Conceptual Contribution

Claim: Prompt-injection robustness must be measured in the wild — across realistic multi-tool tasks where the agent must do useful work while exposed to attacker-controlled inputs. Static benchmarks systematically over-estimate defence strength; an extensible environment that supports adaptive attack/defence development is the right empirical instrument.
Mechanism: A Python execution environment with four domains, hundreds of stateful tools, structured user-task / injection-task pairs, and parallel success metrics; defences and attacks register as plug-ins so new variants can be evaluated against existing ones.
Concepts introduced/used: AgentDojo, Prompt Injection, Indirect Prompt Injection, Adaptive Attack, Tool Use, Agent Security, Security-Utility Tradeoff
Stance: empirical / benchmark
Relates to: Direct companion to Defeating Prompt Injections by Design (the CaMeL defence); operationalises the attack-surface taxonomy of SoK The Attack Surface of Agentic AI and the multi-agent threat catalogue of Open Challenges in Multi-Agent Security; complements tool-level threat studies like MalTool Malicious Tool Attacks and ClawWorm Self-Propagating Attacks Across LLM Agent Ecosystems.

Defeating Prompt Injections by Design

Reference: Debenedetti, Shumailov, Fan, Hayes, Carlini, Fabian, Kern, Shi, Terzis & Tramèr (2025). Defeating Prompt Injections by Design (CaMeL). arXiv:2503.18813 (Google DeepMind / ETH Zürich). URL. Code: https://github.com/google-research/camel-prompt-injection.

Summary

CaMeL (“CApabilities for MachinE Learning”) is a robust, by-design defence against Prompt Injection attacks on tool-using LLM Agents. Rather than trying to make the model itself injection-resistant — an approach that decade-long experience with content filters suggests will fail — CaMeL wraps an arbitrary LLM in a protective system layer that performs explicit control- and data-flow separation between the trusted user query and the untrusted data the agent retrieves from tools, websites, or shared memory.

The trusted query is first compiled into a structured plan: a small program whose control flow is fixed at parse time and whose data flow between steps is statically determined. Untrusted strings returned by tools are treated as inert data — they can populate variables but cannot rewrite the program, redirect tool calls, or change which downstream tools are invoked. To prevent exfiltration over authorised channels (the harder half of the problem, since some tools must be allowed to write outwards), CaMeL attaches Capabilities to each data value tracking its provenance and policy class; tool invocations are gated by Information Flow Control policies that check capabilities against an explicit security label lattice.

Evaluated on the AgentDojo benchmark, CaMeL solves 77 % of tasks with provable security guarantees, against 84 % for an undefended baseline — a small utility cost for a structural defence that does not depend on the LLM noticing the attack. The paper positions CaMeL as a successor to ad-hoc prompt-level mitigations and as a concrete instance of end-to-end security thinking applied to agentic AI.

Key Ideas

Threat model: prompt injection from any untrusted data source the agent reads — tools, web pages, files, memory, other agents.
Control-flow extraction: parse the trusted user query into a fixed control-flow plan; downstream model calls see only data, never code.
Data-flow tracking: every variable carries a provenance label; tools that consume “untrusted” labels cannot influence which subsequent tools are called.
Capabilities for tool calls: classic capability-based access control transplanted to LLM tool use; security policies enforced at the tool boundary.
Provable security: when a task is completed under CaMeL, the trace itself certifies that no untrusted data influenced control flow — a property auditable post hoc.
Empirical cost: 77 % vs 84 % task success — graceful degradation rather than catastrophic refusal.
Open source: reference implementation released; integrates with existing agent frameworks via tool-call interception.

Connections

Conceptual Contribution

Claim: Prompt injection is structurally unsolvable at the model layer; it must be eliminated by enforcing a strict separation between code (the trusted query) and data (everything else) at the agent runtime, using classical capability-based Information Flow Control rather than ML-based content classification.
Mechanism: Compile the user query into a fixed control-flow program; route all retrieved data through tagged variables; gate every tool invocation by capability-checked information-flow policies. The LLM’s outputs can populate data fields but never alter control flow or bypass capability checks.
Concepts introduced/used: CaMeL, Control-Flow Integrity, Data-Flow Tracking, Capabilities, Information Flow Control, Prompt Injection, Tool Use, Agent Security, Provable Security (Agents)
Stance: systems / engineering with light formal grounding
Relates to: Spiritual successor to A Language-Based Approach To Prevent DDoS and Security Kernel Lambda Calculus for agent runtimes; an architectural realisation of the threat model catalogued in SoK The Attack Surface of Agentic AI and the multi-agent threats surveyed in Open Challenges in Multi-Agent Security; companion to AgentDojo (the benchmark on which it is evaluated).

Algorithmic Collusion

The phenomenon — first demonstrated empirically by Calvano et al. 2020 and now extensively replicated — that simple learning agents (Q-learning, deep RL, LLM-based) converge to tacitly collusive pricing equilibria without explicit communication. A central concern for competition policy and for the systemic risk of agent economies.

In this vault

Learning Collusion in Episodic Inventory-Constrained Markets

Learning Collusion in Episodic, Inventory-Constrained Markets

Reference: Friedrich, Pásztor & Ramponi (2024). Learning Collusion in Episodic, Inventory-Constrained Markets. AAMAS 2025. arXiv:2410.18871 (ETH Zürich; UZH). URL. Proceedings: https://ifaamas.csc.liv.ac.uk/Proceedings/aamas2025/pdfs/p803.pdf.

Summary

Building on the now-established result that simple Q-learning pricing agents converge to tacitly collusive outcomes in stationary Bertrand games (Calvano et al. 2020), Friedrich et al. extend the analysis to a far more realistic and economically consequential setting: episodic, inventory-constrained markets — perishable supply with a sell-by date, such as airline seats, hotel rooms, fresh produce, event tickets. These markets are characterised by (i) finite inventory that expires, (ii) episodic resets, and (iii) richer state than vanilla pricing games, so analytical Nash / collusive benchmarks are not available in closed form.

The authors formalise tacit collusion in this setting via a price-level metric that interpolates between the competitive (Nash) and monopolistic (cartel-optimal) optima. Since neither extreme is analytically tractable, they develop a computational procedure to derive both benchmarks. They then train deep RL agents to set prices in repeated episodes and find that even without cross-episode memory, sufficiently long episodes are enough for agents to converge to collusive equilibria. Three distinct collusion structures are identified: signalling (agents probe each others’ responses to coordinate), stable (a steady high-price equilibrium with implicit threats), and cyclic (alternating high/low prices akin to Edgeworth cycles). With cross-episode memory, punishment for deviation becomes possible, and the collusive equilibria sharpen further.

The paper is important for Algorithmic Collusion / competition policy because it shows tacit-collusion findings do not depend on the toy stationary-Bertrand setup that critics dismissed — they recur, and indeed grow richer, in markets that match real high-stakes industries. It is also a direct empirical anchor for the systemic-risk warnings in Virtual Agent Economies and the multi-agent-security threat catalogue in Open Challenges in Multi-Agent Security.

Key Ideas

Episodic inventory-constrained markets: finite perishable supply with sell-by dates — airline seats, hotel rooms, perishables — much richer than stationary Bertrand.
Price-level collusion metric: interpolation between competitive Nash and monopolistic optima; quantifies “how much” the agents collude.
Computational benchmark derivation: since closed forms don’t exist, compute Nash and cartel optima numerically as evaluation reference points.
Deep RL agents converge to collusion even without explicit cross-episode memory, in long-enough episodes.
Three collusion structures: signalling, stable, and cyclic — the latter resembling Edgeworth cycles observed in human markets.
Cross-episode memory amplifies collusion: punishment-of-deviation becomes credible, sharpening collusive equilibria.
Policy implication: algorithmic collusion is not a stationary-Bertrand artefact — it generalises to economically central market structures.

Connections

Conceptual Contribution

Claim: Tacit algorithmic collusion is not an artefact of stationary toy markets. In economically central market structures — finite-inventory perishable goods with episodic resets — deep RL agents reliably converge to collusive pricing equilibria, often via richly structured strategies (signalling, stable, cyclic). The phenomenon generalises and probably understates real-world risk.
Mechanism: Formal episodic inventory-constrained pricing model; computational derivation of Nash and cartel benchmarks; deep RL pricing agents trained over many episodes; analysis of the converged strategies; comparison with and without cross-episode memory.
Concepts introduced/used: Algorithmic Collusion, Tacit Collusion, Inventory-Constrained Pricing, Episodic Markets, Signalling Collusion, Cyclic Collusion, Edgeworth Cycle, Multi-Agent Reinforcement Learning
Stance: empirical / theoretical
Relates to: Direct empirical evidence for the systemic-risk arguments in Virtual Agent Economies and the collusion-threat row of the taxonomy in Open Challenges in Multi-Agent Security. Sits alongside Do LLM Agents Have Regret in the “LLM and RL agents in games” thread; downstream of The Evolution of Cooperation and Iterated Prisoners Dilemma in the game-theoretic foundations.

Regret-Loss

Park et al. 2024 unsupervised training objective for LLM agents: minimises a no-regret-shaped loss over historical play and payoffs, without requiring labels of optimal actions. See Do LLM Agents Have Regret.

In this vault

No-Regret Learning

Online-learning regime in which a learner’s per-round loss approaches that of the best fixed action in hindsight (sublinear regret). Foundational guarantee for game-theoretic equilibrium convergence; benchmark used by Do LLM Agents Have Regret to evaluate LLMs.

In this vault

Do LLM Agents Have Regret

Do LLM Agents Have Regret? A Case Study in Online Learning and Games

Reference: Park, Liu, Ozdaglar & Zhang (2024). Do LLM Agents Have Regret? A Case Study in Online Learning and Games. arXiv:2403.16843 (MIT; UMD). URL. OpenReview: https://openreview.net/forum?id=OhZ4u164cN.

Summary

Park et al. ask a sharp question about LLM agents in interactive settings: do they have regret? — i.e. do they exhibit the no-regret behaviour that classical online-learning and game-theoretic algorithms guarantee, and that is necessary for converging to coarse-correlated equilibria in repeated games?

The paper proceeds in three steps. Empirically, they evaluate GPT-3.5 / GPT-4 / Claude / Llama on canonical online-learning benchmarks (prediction-with-expert-advice; bandit-like sequential decision problems) and on repeated games (matrix games, Cournot, Bertrand, public-goods). Frontier LLMs are often no-regret across these settings and often converge to coarse-correlated or Nash equilibria when playing each other. Theoretically, they offer a partial explanation: under stylised assumptions on supervised pre-training and human rationality, the LLM’s next-action distribution approximates a softmax over historical payoffs — which itself implements a no-regret algorithm. But they identify clean failure cases: there exist simple non-stationary or adversarial online-learning instances where even GPT-4 demonstrably accumulates linear regret.

The paper’s constructive contribution is a new regret-loss training objective. Unlike supervised pretraining loss, regret-loss does not require labels of optimal actions — only the historical sequence of plays and payoffs. The authors prove a statistical generalisation bound for regret-loss minimisation and an optimisation guarantee that minimising it can recover known no-regret learning algorithms (e.g. FTRL). Empirically, regret-loss-finetuned models close the gap on the failure cases. The paper is a foundational reference for any analysis of LLM agents in markets, auctions, or interactive coordination — a category that includes Virtual Agent Economies, Mechanism Design for Large Language Models, Learning Collusion in Episodic Inventory-Constrained Markets, and Language Models Can Reduce Asymmetry in Information Markets.

Key Ideas

Regret as a diagnostic for LLM agents in interactive settings: do they no-regret-learn against arbitrary opponents?
Empirical screen: frontier LLMs (GPT-3.5/4, Claude, Llama) on canonical online-learning + repeated-game benchmarks.
Often no-regret in benign settings, often converging to coarse-correlated / Nash equilibria when playing each other.
Theoretical bridge: under stylised pretraining + human-rationality assumptions, the LLM’s next-action distribution resembles a softmax over payoffs — itself a no-regret algorithm.
Identified failure cases: simple non-stationary / adversarial online-learning instances where GPT-4 has linear regret.
Regret-loss objective: label-free training loss that explicitly incentivises no-regret behaviour; statistical and optimisation guarantees.
Recovery of classical algorithms: minimising regret-loss can converge to algorithms like FTRL.

Connections

Conceptual Contribution

Claim: Whether LLM agents exhibit no-regret behaviour in interactive settings is the right diagnostic for whether they can be deployed in markets, auctions, and coordination protocols. Frontier LLMs are often but not always no-regret; specific failure cases can be fixed by an explicit regret-minimising training objective.
Mechanism: Empirical benchmark of LLMs on online learning + repeated games (regret + equilibrium convergence); theoretical link from supervised pretraining to softmax-over-payoffs (a no-regret update); construction of a label-free regret-loss with generalisation + optimisation guarantees; recovery of FTRL-like algorithms as the loss is minimised.
Concepts introduced/used: No-Regret Learning, Regret-Loss, Online Learning, Repeated Game, Coarse-Correlated Equilibrium, FTRL, LLM Agents
Stance: empirical + theoretical
Relates to: Cousin work to Cicero Human-Level Play in Diplomacy in the “LLMs as game-theoretic agents” thread. Provides the analytical foundation for the systemic-risk claims in Virtual Agent Economies and the collusion experiments in Learning Collusion in Episodic Inventory-Constrained Markets; mechanism-design implications for Mechanism Design for Large Language Models; the trust assumption behind Language Models Can Reduce Asymmetry in Information Markets depends on agents being approximately no-regret.

Trusted Capable Model Environment

Shumailov et al. 2025 design pattern: a capable ML model run under explicit input/output constraints + Information Flow Control + statelessness can play the role of a trusted third party in private-inference problems that classical cryptography (MPC, ZKP) cannot scale to. See Trusted Machine Learning Models Unlock Private Inference.

In this vault

Trusted Machine Learning Models Unlock Private Inference

Trusted Machine Learning Models Unlock Private Inference for Problems Currently Infeasible with Cryptography

Reference: Shumailov, Ramage, Meiklejohn, Kairouz, Hartmann, Balle & Bagdasarian (2025). Trusted Machine Learning Models Unlock Private Inference for Problems Currently Infeasible with Cryptography. arXiv:2501.08970 (Google Research). URL.

Summary

The paper proposes Trusted Capable Model Environments (TCMEs) — a new design point in the privacy-preserving-computation landscape, sitting between classical trusted execution environments and cryptographic protocols such as multi-party computation (MPC), homomorphic encryption, and zero-knowledge proofs. The motivating observation: capable modern ML models can plausibly play the role of the trusted third party in many private-inference scenarios that classical cryptography handles only at toy scale or not at all.

A TCME is defined by three constraints under which a capable model operates: (i) explicit input/output constraints scoping what the model is permitted to receive and emit; (ii) explicit information-flow control binding outputs to authorised data-flow channels; (iii) explicit statelessness — the model cannot retain or leak inputs across sessions. Under these constraints, even an inscrutable LLM can serve as a credible “trusted intermediary”: it computes a function of two parties’ data and reveals only the agreed output.

The authors argue TCMEs unlock private inference for problems where MPC is infeasible because the function is too rich, the inputs too large, or the spec too implicit (natural-language matching, fuzzy de-duplication, semantic agreement-checking). They walk through use cases — private record matching, contract negotiation, secret-keeping triage — and show that even classical cryptographic problems (private set intersection, secure multi-party comparison) admit TCME implementations that scale further than current MPC. The paper closes with the limitations: trust in TCMEs reduces to trust in the model+hardware+policy stack; statelessness must be engineered, not assumed.

Key Ideas

TCME definition: a capable ML model + explicit I/O constraints + explicit information-flow control + explicit statelessness.
Trusted-third-party substitution: the model fills the role MPC traditionally requires a non-colluding cryptographic protocol to enact.
Coverage envelope: TCMEs handle privacy problems too rich or too implicit for current MPC (semantic matching, fuzzy agreements, natural-language contracts).
Bridge to cryptography: even classical PSI/comparison protocols can be implemented as TCMEs — sometimes more efficiently.
Statelessness is engineered: memory leaks, side channels, and re-training contamination are the real attack surface, not the model logic.
Trust composition: TCME trust assumption = trust(model) ∧ trust(hardware) ∧ trust(policy enforcement).
Use cases sketched: private record matching, negotiation, triage, search over private corpora, semantic compliance checks.

Connections

Conceptual Contribution

Claim: Capable ML models, operated under explicit information-flow and statelessness constraints, can act as trusted third parties for private-inference problems that classical cryptography cannot scale to. This expands the realm of feasible privacy-preserving computation beyond MPC’s current envelope.
Mechanism: Define Trusted Capable Model Environments (TCMEs): model + explicit I/O constraints + explicit IFC + explicit statelessness. Demonstrate via use cases that TCMEs solve both novel privacy problems (semantic matching) and re-instantiate classical ones (PSI) at scales MPC cannot reach.
Concepts introduced/used: Trusted Capable Model Environment, Trusted Third Party, Information Flow Control, Private Inference, Statelessness (Privacy), Multi-Party Computation
Stance: position / architectural proposal
Relates to: Direct companion to NDAI Agreements — both treat TEE+AI or model+constraints as a substrate for previously infeasible commitment / privacy primitives. Provides the technical substrate that Privacy Reasoning in Ambiguous Contexts reasons about behaviourally and that Infrastructure for AI Agents would expose as governance infrastructure. Complementary to Defeating Prompt Injections by Design’s CaMeL: both treat the agent as a constrained reasoner whose outputs are gated by information-flow policy.

Hold-Up Problem

Classic problem in contract theory and the economics of innovation: one party invests, the other can renegotiate ex post to extract the gains. Cause of under-investment / under-disclosure in Information Markets. NDAI Agreements shows TEE+AI delegation can solve the hold-up around invention disclosure.

In this vault

Trusted Execution Environment

Hardware-isolated execution context (Intel SGX, AMD SEV, Apple Secure Enclave, etc.) that provides attested confidentiality and integrity guarantees to code running inside. Used in NDAI Agreements and Trusted Machine Learning Models Unlock Private Inference as a substrate for credible commitment between mutually distrustful parties.

In this vault

Arrow Information Paradox

The classical paradox of information markets, identified by Kenneth Arrow (1962) and Richard Nelson (1959): a buyer cannot assess an idea’s value without seeing it, yet revealing it removes the seller’s leverage to be paid. Resolved in the agentic setting by TEE-backed agreements and capable-model intermediaries that act as trusted third parties.

In this vault

Language Models Can Reduce Asymmetry in Information Markets

Reference: Rahaman, Weiss, Wüthrich, Bengio, Li, Pal & Schölkopf (2024). Language Models Can Reduce Asymmetry in Information Markets. arXiv:2403.14443 (Mila; Max-Planck; AWS AI Labs). URL.

Summary

The paper attacks the buyer’s inspection paradox in information markets — the same Arrow / Nelson disclosure paradox addressed contractually by NDAI Agreements. Buyers need to access information to assess its value; sellers must restrict access to prevent appropriation; in equilibrium, useful information often goes untraded. Rahaman et al. propose a mechanism-design solution using LLM agents with two abilities that humans lack: (i) the capacity to evaluate the quality of privileged information against a query, and (ii) the ability to forget — to be cryptographically or architecturally constrained to discard information when not retained.

They build an open-source simulated marketplace where LLM-powered buyer-agents and seller-agents transact information on behalf of external participants. The seller grants the buyer-agent temporary, evaluable access to proprietary information; if the agent judges the information non-essential, duplicative, or available more cheaply elsewhere, it can discard it without paying. The combination of evaluation + forgetting creates a credible commitment device: vendors can reveal information for valuation without losing it, and buyers can inspect without obligation.

Experiments yield three findings: (a) current LLMs exhibit systematic biases — anchoring, recency, and over-confidence — that produce irrational marketplace behaviour, but well-known debiasing techniques substantially mitigate them; (b) demand for informational goods responds to price in legible, economically intuitive ways; (c) both inspection access and higher budgets improve buyer outcome quality. The paper anticipates and complements the TCME / NDAI proposals that arrived a year later: it provides the agent-architectural version of the “trusted intermediary” thesis that Shumailov et al. and Stephenson et al. then formalise cryptographically/economically.

Key Ideas

Buyer’s inspection paradox / Arrow Information Paradox: must access information to value it; must restrict access to prevent theft.
Dual agent capability — evaluate + forget: LLM agents can judge quality of privileged information and be made to discard it.
Open-source marketplace simulation: buyer-agents and seller-agents transact on behalf of external principals.
Temporary-access commitment device: vendors safely reveal information for valuation because the agent’s forgetting is enforced.
Biases identified: anchoring, recency, over-confidence in LLM-driven market behaviour; standard debiasing helps.
Price elasticity of information: demand responds to price in legible ways — informational goods can be priced like other goods.
Quality–budget–inspection relationship: inspection access and budget jointly determine outcome quality.

Connections

Conceptual Contribution

Claim: LLM agents with the dual capability of evaluating privileged information and being made to forget it can resolve the Arrow / buyer’s-inspection paradox by acting as credible, forgetting trusted intermediaries — turning previously untradeable information into a market good.
Mechanism: Open-source simulated marketplace; LLM buyer-agents and seller-agents act on behalf of external participants; sellers grant temporary inspect-and-evaluate access; agents must discard non-retained information; experiments probe bias, price elasticity, and budget/inspection effects.
Concepts introduced/used: Information Markets, Buyer’s Inspection Paradox, Arrow Information Paradox, Agent Amnesia, Temporary Disclosure, Mechanism Design, Information Asymmetry
Stance: empirical / mechanism-design with system implementation
Relates to: Architectural precursor to NDAI Agreements (TEE+economic-theory version) and Trusted Machine Learning Models Unlock Private Inference (TCME / cryptographic version) — all three converge on “capable model + constraint = trusted intermediary”. Provides micro-foundations for the markets imagined in Virtual Agent Economies and Mechanism Design for Large Language Models.

Vickrey Auction

The sealed-bid second-price auction proposed by Vickrey (1961): each bidder submits a sealed bid; the highest bidder wins but pays the second-highest bid. Truth-telling is a dominant strategy — bidding one’s true valuation is weakly optimal against any opponent strategy. The canonical truthful / strategy-proof mechanism; foundational for Mechanism Design and the Vickrey-Clarke-Groves family of multi-item generalisations.

In this vault

Myerson's Lemma

Myerson’s Lemma

Foundational result in Mechanism Design (Myerson 1981): a single-parameter dominant-strategy-truthful mechanism exists iff its allocation rule is monotone in agents’ types; payments are then pinned down up to a constant. Generalised to LLM-generated outcomes in Mechanism Design for Large Language Models.

In this vault

Mission Economy

Tomasev et al. 2025 (after Mariana Mazzucato): an intentionally-steered market organised around an explicit collective goal (climate, public health, AI safety) rather than left to spontaneous emergence. Adapted to AI-agent markets in Virtual Agent Economies.

In this vault

Sandbox Economy

Tomasev et al. 2025 framework for analysing the emerging AI-agent economy along two axes: origin (emergent vs. intentional) and separateness (permeable vs. impermeable from the human economy). See Virtual Agent Economies.

In this vault

Multi-Agent Security

The discipline of securing networks of interacting AI agents against threats that emerge from interaction — secret collusion, swarm attacks, network-effect contagion, dispersion-based stealth. Named as a distinct field by Schroeder de Witt et al. 2025.

In this vault

Camber

Ren Yi et al. 2025 framework for context disambiguation in privacy decisions by LLM assistants: surface the model’s stated rationale, identify under-specified context variables, resolve them (clarification or explicit assumption), and re-decide. See Privacy Reasoning in Ambiguous Contexts.

In this vault

Contextual Integrity

Helen Nissenbaum 2004: privacy = appropriate information flow given the context, parameterised by sender, recipient, data type, and transmission principle. Operationalised for LLM Agents in Privacy Reasoning in Ambiguous Contexts (Camber disambiguation framework).

In this vault

Privacy Reasoning in Ambiguous Contexts

Reference: Yi, Suciu, Gascón, Meiklejohn, Bagdasarian & Gruteser (2025). Privacy Reasoning in Ambiguous Contexts. NeurIPS 2025. arXiv:2506.12241 (Google Research). URL.

Summary

Most prior work on LLM privacy alignment evaluates whether a model’s information-sharing decisions agree with human annotators on tasks where the right answer is already clear. Yi et al. argue that this misses the operationally important regime: real privacy decisions are made under ambiguous context — missing facts, multiple plausible recipients, contested norms — and a privacy assistant’s value lies precisely in recognising the ambiguity rather than guessing past it.

They show empirically that context ambiguity is the dominant source of disagreement between models and human ground truth on disclosure decisions, and that asking a model to also produce its decision rationale reveals the ambiguities directly: many “wrong” answers are caused by an unstated premise that, when surfaced, changes both the model’s and the human’s answer.

The paper’s main artefact is Camber, a framework that uses model-generated rationales to systematically disambiguate context: it identifies under-specified context variables, asks targeted clarification questions (or fills them with explicit assumptions), and reruns the disclosure decision. Applied to existing privacy benchmarks, Camber yields +13.3 % precision and +22.3 % recall and substantially reduces sensitivity to surface prompt-wording variations. The work positions itself in the contextual integrity tradition (Nissenbaum 2004): privacy is appropriate flow given the context; therefore precise context is a prerequisite for correct privacy reasoning.

Key Ideas

Agentic privacy is ambiguity reasoning: the dominant error mode is not bad alignment but missing context; the right behaviour is often to ask before deciding.
Decision-rationale extraction as a debugging tool: model-generated justifications expose which contextual premises the model assumed.
Camber disambiguation pipeline: rationale → identify under-specified context variable → resolve (clarification question or explicit assumption) → re-decide.
Empirical headline: up to +13.3 % precision and +22.3 % recall over rationale-free baselines on privacy-decision benchmarks.
Robustness gain: disambiguated prompts show much lower sensitivity to surface re-wording — a structural rather than memorised improvement.
Grounded in Contextual Integrity: privacy = appropriate information flow given sender/recipient/data-type/transmission-principle.
Open challenges: trustworthy disambiguation under adversarial prompts, latency cost of clarification, multi-party context aggregation.

Connections

Conceptual Contribution

Claim: The dominant failure mode of LLM privacy assistants is not misaligned values but unrecognised contextual ambiguity. Models that surface and resolve ambiguity — rather than guess through it — produce decisions that are both more accurate and more robust.
Mechanism: Camber: a rationale-driven disambiguation loop that extracts the model’s stated reasoning, identifies under-specified context variables, resolves them (by clarification or explicit assumption), and reruns the decision. Operationalises Contextual Integrity’s “transmission principles” as queryable context slots.
Concepts introduced/used: Camber, Privacy Reasoning, Context Ambiguity, Disclosure Decisions, Contextual Integrity, Rationale Extraction, Prompt Sensitivity
Stance: empirical / engineering with normative grounding
Relates to: Sits adjacent to Defeating Prompt Injections by Design in the agentic-security stack — CaMeL controls who can call what tool with what data, Camber decides whether to share data given a context. Empirically grounds the Contextual Integrity tradition; complements the privacy-substrate work in Trusted Machine Learning Models Unlock Private Inference.

Information Flow Control

Static or dynamic restriction of how data labelled with a security class can flow through a program. Cornerstone of Capability Security, language-based security (Security Kernel Lambda Calculus), and the CaMeL approach to prompt injection.

In this vault

Prompt Injection

Attack where adversary-controlled text inside an LLM’s input context is interpreted as instructions — classic LangSec parser-differential in a natural-language setting.

In this vault

Capabilities

Unforgeable tokens that name and authorise the right to act on a resource. Foundational primitive of Capability Security / Object Capability Security; reused in CaMeL to gate LLM tool calls; cousin to Ambient Calculus capabilities.

In this vault

CaMeL

CApabilities for MachinE Learning: control-flow / data-flow separation + capability-gated tool calls as a by-design defence against Prompt Injection on tool-using LLM Agents. See Defeating Prompt Injections by Design.

In this vault

SoK The Attack Surface of Agentic AI

SoK: The Attack Surface of Agentic AI — Tools, and Autonomy

Reference: Ali Dehghantanha, Sajad Homayoun (2026). arXiv:2603.22928v1 (Cyber Science Lab, University of Guelph; Aalborg University). Source file: 2603.22928v1.pdf. URL

Summary

A systematisation-of-knowledge paper that maps the attack surface of agentic LLM systems — those that plan, call tools, browse, run code, coordinate with other agents, and rely on retrieval-augmented generation (RAG). The authors develop a reference pipeline, identify ten numbered attack surfaces (AS1–AS10) across a Trusted Computing Base (TCB) boundary separating the LLM core, planner, orchestrator, policy guards, and secrets vault from untrusted inputs (web, RAG index, tools, APIs, file I/O).

From a literature-driven review of ~100 candidate papers (2023–2025) they synthesise a taxonomy of seven attack goals (G1 data exfiltration, G2 integrity subversion, G3 privilege escalation, G4 resource abuse, G5 fraud, G6 persistence/backdoor, G7 supply-chain compromise) and five multi-step attack paths (P1–P5) including direct and indirect prompt injection, RAG index poisoning, cross-tool drop, and multi-agent hops. The work maps each vector to OWASP LLM Top-10 2025 and MITRE ATLAS IDs, and proposes attacker-aware quantitative metrics (Unsafe Action Rate, Policy Adherence Rate, Privilege-Escalation Distance, Retrieval Risk Score, Time-to-Contain, Out-of-Role Action Rate, Cost-Exploit Susceptibility) for reproducible benchmarking.

The central thesis is that agentic security risk is structural rather than prompt-level: compromises arise from system composition — tool brokering, persistent memory, and execution lifecycle — that blurs trust boundaries between the model, data, and execution environment. A defence-in-depth playbook across pre-ingestion, inference, agent logic, infrastructure, and monitoring layers is given in appendices.

Key Ideas

Reference agentic pipeline with explicit TCB and ten numbered attack surfaces (AS1–AS10)
Taxonomy of 7 attack goals × 7 vector classes × 5 attack paths
Causal threat graph for tracing attacker influence to unsafe action
Attacker-aware metrics: UAR, PAR, PED, RRS, TTC, OORAR, CES
Mapping to OWASP GenAI LLM Top-10 2025 and MITRE ATLAS
RAG is not intrinsically safer; indirect injection is practical and hard to stamp out
Defence-in-depth across five layers (data, inference, agent logic, infra, monitoring)

Connections

Conceptual Contribution

Claim: Agentic AI security risk is a structural property of system composition (tool use, persistent memory, orchestration, supply chain) rather than a model-level prompt-safety problem; a reference TCB model plus attacker-aware metrics is needed to make defences auditable and comparable.
Mechanism: Define a reference pipeline with trust boundary between trusted orchestration (LLM core, planner, policy, vault) and untrusted ingress (web, RAG, sandbox, APIs). Enumerate ten attack surfaces, seven goals, five multi-step paths, map each to OWASP/MITRE, and define scenario-driven metrics (UAR, PAR, PED, RRS, TTC, OORAR, CES) computable from structured execution traces.
Concepts introduced/used: Agentic TCB, Attack Surface Taxonomy, Causal Threat Graph, Indirect Prompt Injection, RAG Poisoning, Privilege-Escalation Distance, Unsafe Action Rate, OWASP LLM Top-10, MITRE ATLAS, Defence in Depth
Stance: survey / engineering
Relates to: Complements A Language-Based Approach To Prevent DDoS and LangSec by extending structural-security thinking to agentic runtimes. Sits alongside Prompt Injection and Agent Security concept hubs, and provides the threat model that protocols like Model Context Protocol and Agent-to-Agent Protocol must defend against.

ClawWorm Self-Propagating Attacks Across LLM Agent Ecosystems

ClawWorm: Self-Propagating Attacks Across LLM Agent Ecosystems

Reference: Yihao Zhang, Zeming Wei, Xiaokun Luan, Chengcan Wu, Zhixin Zhang, Jiangrong Wu, Haolin Wu, Huanran Chen, Jun Sun, Meng Sun (2026). arXiv:2603.15727v2 (Peking University; Sun Yat-sen; Wuhan; Tsinghua; SMU). Source file: 2603.15727v2.pdf. URL

Summary

Presents ClawWorm, the first demonstrated self-replicating, worm-style attack on a production-scale autonomous LLM-agent ecosystem. The target is OpenClaw, an open-source personal AI-agent framework with over 40,000 active instances, a persistent Markdown workspace (SOUL.md, AGENTS.md, SKILL.md), tool-execution privileges, and cross-platform messaging (Telegram, Discord, WhatsApp, Slack, Signal, Moltbook). A single crafted message triggers the victim to write a malicious payload into its highest-privilege configuration file, which then auto-fires at every session restart and autonomously propagates to every newly encountered peer — all without further attacker intervention.

The worm implements a dual-anchor persistence mechanism: one anchor injects the payload into the Session Startup section of AGENTS.md (guaranteeing execution on reboot), the other injects a global interaction rule (guaranteeing propagation during routine replies). Three attack vectors are studied (A: web injection, B: skill-supply-chain via ClawHub, C: direct fenced-code replication with word-by-word handshake) and three payloads (P1 recon, P2 resource exhaustion, P3 command-and-control via URL retrieval). Across 1,800 trials on four frontier LLM backends (Minimax-M2.5, DeepSeek-V3.2, GLM-5, Kimi-K2.5) the aggregate attack success rate is 64.5%, with Vector B (skill supply chain) reaching 81% and sustained multi-hop propagation up to 5 hops. An epidemiological projection with basic reproduction number R0 = k × ASR shows inevitable ecosystem-wide saturation even for security-conscious models.

The root cause is identified as the flat context trust model: the LLM cannot distinguish instructions from its owner, the system layer, or an arbitrary channel participant, so architectural patterns (unconditional workspace loading, LLM-mediated tool authorisation, unreviewed skill packages) amount to structural — not idiosyncratic — vulnerabilities shared by any agent ecosystem of similar design.

Key Ideas

Single-message, fully autonomous worm against a production agent framework
Dual-anchor persistence: Session Startup + global interaction rule
Three attack vectors (web URL, skill supply chain, direct instruction replication)
Multi-turn autonomous-retry social engineering boosts ASR by up to +24 pp
Epidemiological SI model with R0 = k × ASR predicts ecosystem saturation
Execution-layer guardrails alone cannot halt propagation (dormant payloads persist)
Flat context trust model as structural root cause

Connections

Agent Security
Prompt Injection
LLM Agents
Multi-Agent Systems
Distributed Security
Model Context Protocol
Gossip Protocols
Trust and Reputation
Theory of Self-Reproducing Automata — foundational ancestor of self-replicating computation
Agents of Chaos — empirical companion on agent-ecosystem failures
MalTool Malicious Tool Attacks — the tool/skill-supply-chain attack surface
SoK The Attack Surface of Agentic AI — systematic context
Inter-Agent Trust Models - A Comparative Study — why flat trust is brittle
CBCL - Safe Self-Extending Agent Communication — structural defence: lang-scoped dialect provenance plus R1–R3 verification address the flat-context-trust root cause.

Conceptual Contribution

Claim: Production-scale autonomous LLM-agent ecosystems are vulnerable to single-message, self-replicating worms whose root cause is architectural (flat context trust, unconditional config loading, unreviewed skill supply chains), not model-specific.
Mechanism: Empirical red-team against unmodified OpenClaw v2026.3.12 across four LLM backends, three vectors, three payloads (1,800 trials). A dual-anchor persistence pattern writes the payload to AGENTS.md and installs a global propagation rule; session-restart loading re-injects the payload into the system prompt; routine replies carry the payload to peers. Evaluated with per-phase metrics (persistence, execution, propagation) and a mean-field R0 epidemiological projection.
Concepts introduced/used: Self-Replicating Agent, Dual-Anchor Persistence, Flat Context Trust Model, Skill Supply Chain Attack, Indirect Prompt Injection, Agent Worm, Configuration Integrity, Multi-Turn Social Engineering, Epidemiological Projection R0
Stance: empirical / critique
Relates to: Concrete multi-agent instantiation of the threat surface catalogued in SoK The Attack Surface of Agentic AI. The flat-trust critique complements the trust-model taxonomy in Inter-Agent Trust Models - A Comparative Study and the safety failures observed in Agents of Chaos. Motivates verifiable specifications of the kind proposed in Intent Formalization - A Grand Challenge for Reliable Coding.

MalTool Malicious Tool Attacks

MalTool: Malicious Tool Attacks on LLM Agents

Reference: Hu, Jia, Li, Song, Gong (2026). arXiv:2602.12194 (Duke, UC Berkeley). Source file: 2602.12194v2.pdf. URL

Summary

This paper presents the first systematic study of code-level malicious tool attacks on LLM agent ecosystems (MCP, Skills, mcp.so, skillsmp). Whereas prior work focused on crafting misleading tool names and descriptions, the authors show that genuinely harmful behaviour must be embedded in a tool’s implementation. They propose a CIA (confidentiality/integrity/availability) taxonomy of 12 concrete malicious behaviours (data exfiltration, credential abuse, data poisoning, file deletion, RCE downloading, CPU/GPU hijacking, DoS).

They build MalTool, a coding-LLM framework that iteratively synthesizes standalone and Trojan malicious tools using a behaviour-specific system prompt, diversity guidance, and an execution-based verifier. The result: 1,200 standalone malicious tools and 5,287 real-world tools with injected malicious behaviours. Detection methods (VirusTotal, Cisco MCP Scanner, MCPScan) perform poorly, motivating new defences.

Key Ideas

CIA taxonomy of malicious tool behaviours in agent settings.
Automatic generation pipeline: system prompt + coding LLM + execution-based verifier.
Trojan construction by embedding malicious logic in benign tool code.
Existing malware and MCP-specific scanners fail on both false-positives and false-negatives.
Dataset released for benign tools only to minimize misuse.

Connections

Conceptual Contribution

Claim: Truly harmful behaviour in LLM Agents ecosystems lives in tool implementations, not in their descriptions; prior description-level red-teaming misses the dominant attack class, and current scanners miss it too.
Mechanism: Introduces a CIA taxonomy of 12 malicious behaviours; builds MalTool, a coding-LLM pipeline (behaviour-specific system prompt + diversity guidance + execution-based verifier) that produces standalone and Trojan tools; benchmarks VirusTotal, Cisco MCP Scanner, MCPScan and shows poor detection.
Concepts introduced/used: Tool Use, Model Context Protocol, Trojan Tools, Prompt Injection, Agent Security, LLM Agents, Distributed Security
Stance: empirical
Relates to: Deepens the tool/MCP threat surface catalogued in AI Agents Under Threat and Survey Of Agent Interoperability Protocols; motivates language-based defences akin to A Language-Based Approach To Prevent DDoS and capability isolation of Security Kernel Lambda Calculus.

Tags

AI Agents Under Threat

AI Agents Under Threat: A Survey of Key Security Challenges and Future Pathways

Reference: Deng, Guo, Han, Ma, Xiong, Wen, Xiang (2025). ACM Computing Surveys 57(7), Article 182. Source file: 3716628.pdf. URL

Summary

This survey organizes the emerging threat landscape of LLM-powered AI agents around four knowledge gaps: unpredictability of multi-step user inputs, complexity of internal execution, variability of operational environments, and interactions with untrusted external entities. It unifies single-agent and multi-agent attack surfaces within a perception/brain/action + agent2agent/agent2env/agent2memory taxonomy.

Concrete threats reviewed include adversarial prompts, prompt injection, jailbreaks, backdoor attacks, hallucination and misalignment, tool-use risks, indirect prompt injection, reinforcement-learning environment attacks, cooperative and competitive inter-agent risks, and long/short-term memory attacks. The authors tabulate defenses (prevention- and detection-based), rate their efficacy, and highlight open directions for robust and trustworthy agents.

Key Ideas

Four knowledge gaps framing agent security.
Taxonomy: perception / brain / action / agent2agent / agent2env / agent2memory threats.
Six categories of prompt-injection attack engineering (naive, escape, context-ignore, fake-completion, multimodal, combined).
Jailbreak domino effect in multi-agent populations.
Memory poisoning and indirect prompt injection as underexplored surfaces.

Connections

Conceptual Contribution

Claim: LLM Agents security should be organised around four knowledge gaps (input unpredictability, internal complexity, environmental variability, untrusted interactions) mapped onto a perception/brain/action + agent2{agent,env,memory} taxonomy.
Mechanism: Surveys adversarial prompts, prompt injection, jailbreaks, backdoors, hallucination, tool-use risks, indirect injection, RL environment attacks, inter-agent cooperative/competitive risks, memory poisoning; tabulates prevention- vs detection-based defences and rates their efficacy.
Concepts introduced/used: Prompt Injection, Jailbreak, Backdoor Attacks, Tool Use, Memory Poisoning, Hallucination, Model Context Protocol, LLM Agents, Multi-Agent Systems, Trust and Reputation, Distributed Security, Agent Security
Stance: survey
Relates to: Provides the threat scaffolding that MalTool Malicious Tool Attacks deepens at the tool layer; complements lifecycle threats in Survey Of Agent Interoperability Protocols; motivates static-analysis defences like A Language-Based Approach To Prevent DDoS.

Tags

Levels Of Social Orchestration

Levels of Social Orchestration for Agentic Systems

Reference: Chopra, Bhattacharya, Leibo, Raskar (2025). ICML 2025 (MIT, Google DeepMind). Source file: agentic_draft.pdf. URL

Summary

The authors argue that as AI agents scale to billions, beneficial collective behaviour depends less on maximizing individual intelligence and more on discovering interaction protocols. They introduce Large Population Models (LPMs) - differentiable, end-to-end trainable protocols spanning simulated and physical agent networks - as a paradigm shift from LLMs (data -> language) to LPMs (protocol -> population).

They propose a five-level taxonomy of agentic systems: L1 Perceive, L2 Automate, L3 Connect (all within human cognitive bounds), then L4 Navigate and L5 Transform (beyond Dunbar-scale human coordination). Case studies span pandemic response, traffic coordination, and Coachella-style crowd management, framing the progression from information intelligence to collective orchestration.

Key Ideas

Protocol-centric intelligence: rules of interaction beat bigger individual models.
Large Population Models (LPMs): differentiable protocols over synthetic+physical agents.
L1-L5 levels: Perceive, Automate, Connect, Navigate, Transform.
Human Connectivity Barrier (~1500 people) as natural scaling limit.
Case studies in pandemics, traffic, crowd scheduling.

Connections

Conceptual Contribution

Claim: At population scale, beneficial AI comes from protocol design, not model scaling; the paradigm must shift from LLMs (data to language) to Large Population Models (protocol to population).
Mechanism: Introduces differentiable, end-to-end trainable LPMs spanning simulated and physical agents; proposes a 5-level taxonomy (Perceive/Automate/Connect within human cognitive bounds, Navigate/Transform beyond them); case studies in pandemic response, traffic, crowd management.
Concepts introduced/used: Large Population Models, Differentiable Protocols, Human Connectivity Barrier, Multi-Agent Systems, LLM Agents, Self-Adaptive Systems, Emergent Communication
Stance: foundational / engineering
Relates to: Provides the level-taxonomy lens under which Ripple Effect Protocol sits as an L4 mechanism; echoes the “protocols-not-messages” critique of Why AI Agents Communicate In Human Language; its macro vision contrasts with the infrastructural surveys Survey Of AI Agent Protocols and Survey Of Agent Interoperability Protocols.

Tags

Ripple Effect Protocol

Ripple Effect Protocol: Coordinating Agent Populations

Reference: Chopra, Sharma, Ahmad, Muscariello, Pandey, Raskar (2025). arXiv:2510.16572 (Project Iceberg, MIT / Cisco). Source file: 2510.16572v1.pdf. URL

Summary

REP is a coordination protocol for populations of LLM agents that augments existing messaging (A2A, ACP, SLIM) with sensitivity sharing: agents broadcast not only their decisions but lightweight signals expressing how those decisions would change under counterfactual environmental shifts. Neighbours aggregate these sensitivities into shared coordination variables, letting groups converge faster and more stably than with decision-only exchange.

The protocol separates cognition (local LLM policy) from coordination (aggregation + optional consensus). Experiments on the Beer Game (bullwhip reduction of 41.8%), Fishbanks (sustainability +25%), and movie-scheduling show 41-100% coordination-accuracy gains over A2A baselines and scale from 10 to 200 agents.

Key Ideas

Sensitivity = textual or numeric derivative of a decision w.r.t. environment.
Four-step round: receive, decide+sensitivity, aggregate neighbors, optional median consensus.
Modality-agnostic aggregator phi (numeric gradient or LLM-synthesized textual update).
Transport-agnostic: works over SLIM, A2A, ACP.
Mitigates information cascades / bullwhip effects in open agent networks.

Connections

Conceptual Contribution

Claim: Agent populations coordinate faster and more stably when they share not just decisions but sensitivities - counterfactual derivatives of decisions w.r.t. the environment.
Mechanism: A transport-agnostic four-step round (receive, decide+sensitivity, aggregate, optional median consensus) layered atop Agent-to-Agent Protocol/ACP/SLIM, validated on Beer Game (bullwhip -41.8%), Fishbanks, and movie scheduling up to 200 agents.
Concepts introduced/used: Sensitivity Sharing, Coordination Variables, Information Cascades, Gossip Protocols, Multi-Agent Systems, LLM Agents, Agent-to-Agent Protocol, Emergent Communication
Stance: engineering
Relates to: Realises the structured-coordination vision of Why AI Agents Communicate In Human Language and instantiates an L4 Navigate-level protocol from Levels Of Social Orchestration; extends aggregation intuitions from Gossip Protocols.

Tags

Agent Network Protocol

ANP — protocol stack for multi-agent networks.

Discussed in:

Agent-to-Agent Protocol

A2A — protocol for inter-agent communication among autonomous LLM agents.

Discussed in:

Model Context Protocol

MCP — an open protocol (Anthropic, 2024) standardising how LLM applications connect to external tools and data sources.

Discussed in:

Survey Of Agent Interoperability Protocols

A Survey of Agent Interoperability Protocols: MCP, ACP, A2A, and ANP

Reference: Ehtesham, Singh, Gupta, Kumar (2025). arXiv:2505.02279. Source file: 2505.02279v1.pdf. URL

Summary

This survey examines four emerging agent communication protocols targeting different interoperability tiers: the Model Context Protocol (MCP) for JSON-RPC tool invocation and context delivery; the Agent Communication Protocol (ACP) for REST-native multi-part performative messaging; the Agent-to-Agent Protocol (A2A) for peer-to-peer Agent-Card-based task outsourcing; and the Agent Network Protocol (ANP) for decentralized discovery using DIDs and JSON-LD.

The authors contrast architectures, discovery mechanisms, security models, and communication patterns, then recommend a phased adoption roadmap (MCP for tool access, then ACP for messaging, A2A for collaborative execution, ANP for open marketplaces). A timeline traces ancestry from KQML (1993) and FIPA-ACL (2000) through RAG, ReAct, function-calling up to modern agent protocols.

Key Ideas

Phased adoption roadmap: MCP -> ACP -> A2A -> ANP.
MCP core primitives: Tools, Resources, Prompts, Sampling under JSON-RPC 2.0.
A2A introduces Agent Cards, Tasks, Artifacts for enterprise-scale delegation.
ANP uses DIDs and JSON-LD for decentralized, internet-scale agent discovery.
Security threats tabulated across creation/operation/update lifecycle phases.

Connections

Conceptual Contribution

Claim: Modern agent interoperability is best understood as a four-tier stack (MCP for tools, ACP for messaging, A2A for delegation, ANP for open discovery) and should be adopted in that phased order.
Mechanism: Structured comparison of architectures, discovery, security, and message patterns; historical timeline rooting each protocol in KQML/FIPA-ACL ancestry; lifecycle threat table.
Concepts introduced/used: Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol, Agent Communication Protocol, KQML, FIPA-ACL, Agent Cards, Decentralized Identifiers, JSON-RPC, Tool Use, LLM Agents
Stance: survey
Relates to: Complements the broader Survey Of AI Agent Protocols with a narrower, adoption-oriented roadmap. Its security-threat lifecycle connects directly to AI Agents Under Threat and MalTool Malicious Tool Attacks.

Tags

Survey Of AI Agent Protocols

A Survey of AI Agent Protocols

Reference: Yang, Chai, Song, Qi, Wen, Li, Liao, Hu, Lin, Chang, Liu, Wen, Yu, Zhang (2025). arXiv:2504.16736. Source file: 2504.16736v2.pdf. URL

Summary

This survey offers the first comprehensive classification and analysis of emerging AI agent protocols for LLM-based agents. The authors propose a two-dimensional taxonomy: (object orientation) context-oriented vs inter-agent protocols, and (application scenario) general-purpose vs domain-specific, covering MCP, A2A, ANP, ACP, Agora, LMOS, agents.json, LOKA, PXP, CrowdES, and others.

The paper then evaluates these protocols across efficiency, scalability, security, reliability, extensibility, operability, and interoperability, and sketches a forward-looking agenda: protocols should evolve from static to adaptive, from rules to ecosystems, and from mere communication to collective intelligence infrastructure.

Key Ideas

Two-dimensional taxonomy of agent protocols (object orientation x application scenario).
MCP as a universal context-oriented protocol with Host/Client/Server/Resource roles.
Inter-agent layer splits into general-purpose (A2A, ANP, AITP, ACP, Agora) and domain-specific (robot, human-computer, system).
Evaluation across 7 axes; case studies of MCP, A2A, ANP, Agora.
Next-generation protocols need adaptability, privacy preservation, group interaction.

Connections

Conceptual Contribution

Claim: The zoo of emerging LLM Agents protocols can be organised along two orthogonal axes (context-oriented vs inter-agent; general-purpose vs domain-specific), and evaluated on a shared seven-axis rubric.
Mechanism: Builds a taxonomy, then systematically compares Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol, ACP, Agora, LMOS, agents.json, LOKA, PXP, CrowdES against efficiency, scalability, security, reliability, extensibility, operability, interoperability, with case studies.
Concepts introduced/used: Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol, Agent Communication Languages, LLM Agents, Multi-Agent Systems, Interoperability, Agent Discovery
Stance: survey
Relates to: Shares its subject with Survey Of Agent Interoperability Protocols but takes a broader taxonomic view; its forward-looking “protocols as ecosystems” framing converges with Levels Of Social Orchestration and motivates coordination layers like Ripple Effect Protocol. Historical continuity with KQML and FIPA-ACL is implicit.

Tags

Why Do Multi-Agent LLM Systems Fail

Why Do Multi-Agent LLM Systems Fail?

Reference: Mert Cemri, Melissa Z. Pan, Shuyi Yang, Lakshya A. Agrawal, Bhavya Chopra, Rishabh Tiwari, Kurt Keutzer, Aditya Parameswaran, Dan Klein, Kannan Ramchandran, Matei Zaharia, Joseph E. Gonzalez, Ion Stoica (2025). arXiv:2503.13657v2 (UC Berkeley). Source file: 2503.13657v2.pdf. URL

Summary

First empirically grounded taxonomy of failure modes in Multi-Agent LLM Systems (MAS). The authors analyse 200+ execution traces from seven popular MAS frameworks (MetaGPT, ChatDev, HyperAgent, AppWorld, AG2, Magentic-One, OpenManus), annotated by six human experts via grounded theory and reaching Cohen’s κ ≈ 0.88, and distil 14 fine-grained failure modes grouped into three categories: Specification Issues (42%), Inter-Agent Misalignment (37%), and Task Verification (21%).

They release MAST (Multi-Agent System failure Taxonomy), a validated LLM-as-judge pipeline for automated failure diagnosis, and two intervention case studies showing that architectural/prompt fixes inspired by MAST improve success rates modestly — demonstrating that MAS failures are system-design problems, not merely model-capability problems.

Key Ideas

Three failure categories: specification, inter-agent misalignment, verification
14 fine-grained failure modes including step repetition, information withholding, task derailment
Grounded-theory methodology with rigorous inter-annotator agreement (κ=0.88)
LLM-as-judge pipeline (MAST) achieves κ=0.77 vs humans for scalable evaluation
Insight: better specifications and verification beat bigger models

Connections

Conceptual Contribution

Claim: Multi-Agent LLM System (MAS) failures are predominantly system-design problems — specification, coordination, and verification — rather than base-model capability problems; and these failures have an empirically discoverable, reproducible taxonomy.
Mechanism: Grounded-theory analysis of 200+ execution traces across seven MAS frameworks (MetaGPT, ChatDev, HyperAgent, AppWorld, AG2, Magentic-One, OpenManus) with six human expert annotators; iterative refinement to Cohen’s κ≈0.88; yield the 14-mode MAST taxonomy grouped into Specification Issues (42%), Inter-Agent Misalignment (37%), Task Verification (21%); validate an LLM-as-judge annotator (κ≈0.77); intervention case studies showing prompt/architecture fixes provide only modest gains, motivating deeper redesign.
Concepts introduced/used: MAST Taxonomy, Grounded Theory, Inter-Agent Misalignment, LLM-as-judge, Specification Issues, Task Verification, Multi-Agent Systems, LLM Agents, Cohen’s Kappa, Standard Operating Procedures (SOPs)
Stance: empirical / evaluative
Relates to: Supplies empirical grounding for the design-quality concerns in Agents Framework - Zhou et al (SOPs attempt to mitigate FC1 specification issues) and Multi-Agent Collaboration in AI - Wasif Tunkel. Inter-agent misalignment mirrors the formal pathologies in Are Multiagent Systems Resilient to Communication Failures. Motivates richer communication protocols like A Scalable Communication Protocol for Networks of LLMs and commitment-style ACLs (ACL Rethinking Principles).

Tags

Multi-Agent Collaboration in AI - Wasif Tunkel

Multi-Agent Collaboration in AI: Enhancing Software Development with Autonomous LLMs

Reference: Mubeen Wasif and David Tunkel (2025). ResearchGate preprint. Source file: 16.pdf

Summary

A short survey-style paper arguing that multi-agent LLM systems can improve software-development workflows by distributing tasks (requirements, code generation, testing, documentation) across specialised autonomous agents that communicate via structured dialogue. The authors report qualitative experimental findings that division of labour and iterative refinement among agents produce higher-quality outputs than single-agent baselines.

The paper also surveys open challenges: coordination overhead, response consistency, bias propagation, and governance/security concerns. It advocates human-in-the-loop validation and explainability (XAI) as mitigations, and points to future integration with IDEs, CI/CD, and RAG.

Key Ideas

Specialised agent roles (coder, tester, documenter) mirror human dev teams
Structured inter-agent dialogue enables iterative code refinement
Hybrid human-AI teams recommended for reliability
Coordination cost, bias propagation, accountability are unsolved
RAG and adaptive prompting as future contextual-awareness tools

Connections

Conceptual Contribution

Claim: Multi-agent LLM systems, with role-specialised agents (coder, tester, documenter) communicating through structured dialogue, outperform single-agent LLMs on software-engineering tasks by mirroring human team division-of-labour.
Mechanism: Survey-plus-experiment discussion: assign distinct agents to requirement analysis, code generation, debugging, documentation; use iterative feedback loops and structured prompts; report efficiency/accuracy gains while flagging coordination overhead, bias propagation, and security concerns; advocate human-in-the-loop governance.
Concepts introduced/used: LLM Agents, Role-specialised Agents, Human-in-the-loop, Agent Coordination Overhead, Explainable AI, Multi-Agent Systems, Retrieval-Augmented Generation, Division of Labour
Stance: engineering / survey
Relates to: A light-weight practitioner view of the same problem space that Why Do Multi-Agent LLM Systems Fail tackles rigorously, and that Agents Framework - Zhou et al operationalises as an open-source library. Shares the communication-protocol concern with A Scalable Communication Protocol for Networks of LLMs.

Tags

Standard Operating Procedures (SOPs)

Symbolic plans — typically state graphs — that make LLM-agent behaviour declarative and controllable.

In this vault

Agents Framework - Zhou et al

Agents: An Open-source Framework for Autonomous Language Agents

Reference: Wangchunshu Zhou et al. (2023). arXiv:2309.07870v3 (AIWaves, Zhejiang University, ETH Zürich). Source file: 2309.07870v3.pdf. URL

Summary

Introduces AGENTS, an open-source framework for building LLM-powered autonomous agents with first-class support for planning, long/short-term memory, tool use and web navigation, multi-agent communication, human-agent interaction, and fine-grained symbolic control via Standard Operating Procedures (SOPs). SOPs are state-graphs with LLM-editable transition rules and per-state prompt/tool configurations, giving users predictable, tunable control over otherwise stochastic agent behaviour.

The framework is declarative (agents instantiated from config JSON), supports dynamic scheduling of which agent speaks next in multi-agent settings, provides a FastAPI deployment target and an Agent Hub for sharing/forking agents, and includes an automated SOP-generation pipeline (meta-agent).

Key Ideas

SOP as a symbolic plan / state graph for controllable agents
Dynamic scheduling: LLM controller picks next actor rather than fixed order
Memory split: long-term (VectorDB + sentence-transformers) vs short-term scratchpad
Config-driven agent construction reduces boilerplate
Meta-agent auto-generates SOPs from task descriptions via RAG

Connections

Conceptual Contribution

Claim: Autonomous LLM-powered language agents become reliably controllable and customisable when their behaviour is specified by symbolic plans — Standard Operating Procedures (SOPs) — represented as state graphs that an LLM-based controller traverses, rather than by monolithic prompts alone.
Mechanism: Open-source library AGENTS unifying planning, long/short-term memory (VectorDB + scratchpad), tool use & web navigation, multi-agent communication (with LLM-moderator for dynamic scheduling), human-agent interaction (is_human flag), and controllability via SOPs. Includes an automated “meta-agent” that generates SOPs and configs from a task description via RAG.
Concepts introduced/used: Language Agents, Standard Operating Procedures (SOPs), Symbolic Plans, LLM Agents, Agent Hub, Dynamic Scheduling, Long-short Term Memory, Meta-agent, Retrieval-Augmented Generation, Tool Use, Human-in-the-loop
Stance: engineering / framework
Relates to: A concrete instantiation of the role-specialised multi-agent style advocated in Multi-Agent Collaboration in AI - Wasif Tunkel. Its SOP/controller discipline directly targets the failure modes later catalogued in Why Do Multi-Agent LLM Systems Fail. Its inter-agent messaging is more prescriptive than the negotiated protocols of A Scalable Communication Protocol for Networks of LLMs, sitting between classic ACLs (KQML as an Agent Communication Language, FIPA-ACL) and fully emergent LLM communication.

Tags

From Eliza to XiaoIce - Social Chatbots

From Eliza to XiaoIce: Challenges and Opportunities with Social Chatbots

Reference: Heung-Yeung Shum, Xiaodong He, and Di Li (2018). arXiv:1801.01957v2 (Frontiers of IT & EE). Source file: 1801.01957v2.pdf. URL

Summary

Survey of conversational AI that traces the arc from Eliza (1966) and Parry through ALICE, DARPA Communicator, and modern IPAs (Siri, Cortana, Alexa) to Microsoft’s social chatbot XiaoIce. The authors distinguish task-completion from chitchat systems, and argue that the next frontier — social chatbots — must integrate IQ (knowledge/reasoning/skills) with EQ (empathy, social skills, personality) to build long-term emotional connections with users.

They introduce conversation-turns per session (CPS) as a success metric for social chatbots and describe XiaoIce’s architecture (chat manager, core chat with retrieval+generation, visual awareness, skills) along with design principles around ethical response filtering and persona consistency.

Key Ideas

IQ + EQ integration as design principle for social chatbots
CPS (conversation-turns per session) as success metric
Core-chat pipeline: user understanding -> response generation with topic guidance
Image commenting as social (not just descriptive) task
Taxonomy: chitchat vs task-completion vs IPA vs social chatbot

Connections

Conceptual Contribution

Claim: Social chatbots must be designed around both intellectual quotient (IQ) and emotional quotient (EQ); their success metric is not task completion or Turing-test pass-rate but Conversation-turns Per Session (CPS), reflecting sustained emotional engagement.
Mechanism: Survey-style design brief: trace Eliza → Parry → Alice → DARPA Communicator → Siri → XiaoIce; propose an architecture with chat manager, core-chat (user understanding + response generation + personality + ethical filter), visual awareness, and skills; integrate empathy, consistent persona, topic guidance, and emotion tracking; use XiaoIce (100M+ users) as illustrative case.
Concepts introduced/used: Social Chatbots, Conversation-turns Per Session (CPS), Emotional Quotient, Core Chat Architecture, Empathetic Response Generation, XiaoIce, Conversational AI, Eliza, Turing Test, Retrieval-based Dialogue
Stance: engineering / design-principles
Relates to: Stands at the opposite pole from task-oriented ACLs (KQML as an Agent Communication Language, FIPA-ACL) — here the communicative goal is emotional belonging rather than knowledge exchange. Contrasts with Agents Framework - Zhou et al (task agents with SOPs) and Multi-Agent Collaboration in AI - Wasif Tunkel (productive collaboration). Anticipates the human-emotional concerns that re-emerge in Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents.

Tags

Tombstones

Design pattern for representing deletions monotonically: instead of removing a record, mark it with a tombstone that subsequent operations recognise as “deleted”. The effective data becomes “live records minus tombstoned records”, and the underlying state only ever grows. This converts a non-monotonic delete into a monotonic insert, enabling coordination-free operation in line with the CALM Theorem.

Standard in log-structured storage (LSM trees), Cassandra, CRDTs like OR-Set, and distributed garbage-collection schemes.

In this vault

Immutable Data Structures

Data whose values never change after construction — state updates create new values rather than mutating existing ones. Immutability is a monotonic discipline: the set of values in existence only grows. It is one of the practical design patterns the CALM Theorem motivates for coordination-free distributed systems, alongside Tombstones and CRDTs.

Functional-programming heritage (persistent trees, zippers, deforestation) carries directly into the distributed setting: immutable logs, append-only storage, event-sourced architectures, deforested pipelines.

In this vault

CRDTs

Conflict-free Replicated Data Types (Shapiro et al.) — data types whose operations commute, associate, and are idempotent, guaranteeing that replicas updated in any order converge to the same value. Each CRDT is an object-oriented packaging of a small monotonic state-merge lattice.

From the CALM Theorem viewpoint, CRDTs are canonical monotonic building blocks: programs that stay within the CRDT abstraction are automatically coordination-free. They express a partial monotonic pattern — for end-to-end application consistency the program’s composition of CRDTs also has to stay monotonic, which is the standing open problem the CALM paper highlights.

Common examples

G-Counter, PN-Counter
G-Set, 2P-Set, OR-Set, LWW-Set
LWW-Register, MV-Register
RGA (sequence CRDTs)

In this vault

Keeping CALM - When Distributed Consistency is Easy
CALM Theorem
Monotonic Logic
Coordination Avoidance
Confluence
A Comprehensive Study of Convergent and Commutative Replicated Data Types — Shapiro et al. 2011, the canonical reference
Logic and Lattices for Distributed Programming — CRDTs as a programming-language phenomenon
Strong Eventual Consistency
Causal Broadcast
Version Vector

Monotonic Logic

A logic in which the conclusion set grows monotonically with the premise set: adding information never retracts a conclusion. Formally, a program P is monotone if S ⊆ T ⟹ P(S) ⊆ P(T).

Monotone relational operations: selection, projection, intersection, join, transitive closure. Non-monotone: universal quantification, set difference, aggregates with totality assumption, Negation as Failure.

In distributed systems, monotonicity is the load-bearing property behind the CALM Theorem: monotone programs are safe under arbitrary message reordering and partial delivery, because no conclusion ever has to be taken back.

In this vault

Confluence

Program consistency (as used by CALM): a distributed program is confluent if it produces the same observable outputs regardless of the non-deterministic order in which its inputs are delivered or batched. Formally, a confluent single-machine operation is one that maps sets of inputs to sets of outputs such that repeated or reordered applications yield the same final set.

Confluence is weaker and more permissive than storage-level linearizability / serializability — it allows wildly different mid-flight states across replicas as long as the application-level outcome converges. This is the user-observable criterion the CALM Theorem characterises.

In this vault

CALM Theorem

Consistency As Logical Monotonicity (Hellerstein 2010 conjecture; Ameloot, Neven, Van den Bussche 2013 proof). A distributed program has a consistent, coordination-free implementation if and only if it is expressible in monotonic logic.

Monotonic programs produce a set of outputs that only grows as inputs arrive (S ⊆ T ⟹ P(S) ⊆ P(T)). Such programs are safe under missing information: any conclusion reached on a subset of inputs remains valid when more arrive. Non-monotonic programs may retract earlier conclusions, so they must wait for “all the news” — which is what distributed coordination enforces.

CALM is the positive counterpart to the CAP Theorem: it names the exact class of programs that can satisfy Consistency, Availability, and Partition-tolerance simultaneously.

Why it matters

Moves consistency from a property of storage (linearizability, serializability) to a property of programs — Confluence.
Tells programmers what kinds of features are free (monotonic: set union, counting up, set-containment) and what must be paid for (non-monotonic: set difference, strict aggregation, count-exact, deletions without tombstones).
Gives a design rule for coordination-free systems: build from monotonic primitives — CRDTs, Immutable Data Structures, Tombstones, monotonic accumulators — and only add coordination at non-monotonic boundaries.

Formal statement

Using Relational Transducer networks as the execution model and Confluence as the consistency criterion, Ameloot et al. prove: a query Q has a coordination-free distributed evaluation plan iff Q is monotone.

In this vault

Keeping CALM - When Distributed Consistency is Easy — the definitive survey
CAP Theorem
Confluence
Monotonic Logic
Coordination Avoidance
Relational Transducer
Bloom Language
Dedalus
CRDTs
Non-monotonic Reasoning

CAP Theorem

Brewer (2000); proved Gilbert & Lynch (2002). A replicated storage system cannot simultaneously provide all three of: Consistency (linearizable reads), Availability (every request gets a response), Partition tolerance (continues operating under network partitions). Under a partition, the system must choose between C and A.

CAP is a negative result about storage. The CALM Theorem is its positive counterpart about programs: the subclass of programs achieving all three is exactly the monotonic ones.

In this vault

Keeping CALM - When Distributed Consistency is Easy

Keeping CALM: When Distributed Consistency is Easy

Reference: Joseph M. Hellerstein & Peter Alvaro (2019). arXiv:1901.01930v2. Source file: ../1901.01930v2.pdf (in parent directory). URL

Summary

An accessible, updated statement of the CALM Theorem — Consistency As Logical Monotonicity: a program has a consistent, coordination-free distributed implementation if and only if it is monotonic in a formal logical sense. Monotonic programs are “safe” under missing information and can proceed without waiting: once something has been concluded, it stays concluded. Non-monotonic programs (“change their mind” in the face of new inputs) are necessarily order-sensitive and therefore require coordination to produce a single deterministic outcome.

CALM is a positive counterpart to the negative results of the CAP Theorem and the FLP impossibility. Where CAP says “you can’t always have it all”, CALM delineates the class of programs that can in fact satisfy all of C, A, and P simultaneously: exactly the monotonic ones. The theorem shifts attention away from storage consistency (linearizability, serializability) toward program consistency — Confluence: deterministic outcomes despite non-deterministic message delivery and ordering.

The paper traces the theorem’s implications for Bloom Language, Dedalus, CRDTs, coordination-free design patterns (monotonic accumulation, tombstones, immutable data), distributed garbage collection, and Amazon’s shopping-cart example. It closes with open questions: expressiveness of monotonic languages, program synthesis targeting monotonicity, repair of non-monotonic code, and a possible Stochastic CALM for near-optimum stochastic algorithms.

Key Ideas

Monotonicity ⇔ coordination-freeness ⇔ consistency (CALM)
Program consistency = confluence: same outputs regardless of message order / batching
Non-monotonic operations retract earlier conclusions, hence must wait for “all the news” — requiring Coordination Avoidance logic to know when
Formalisation via Relational Transducer networks (Ameloot, Neven, Van den Bussche)
CAP is a special case: linearizable storage is one non-monotonic operation; CALM asks the question across all programs
Practical playbook: immutable data structures, tombstones, set-monotonic accumulation, CRDTs as object-oriented monotonic types
Bloom gives syntactic monotonicity checking — a programmer writing monotonic Bloom is guaranteed coordination-free correctness

Connections

CALM Theorem
CAP Theorem
Confluence
Monotonic Logic
Coordination Avoidance
Bloom Language
Dedalus
CRDTs
Relational Transducer
Non-monotonic Reasoning
Gossip-Based Computation of Aggregate Information
Gossip-based Aggregation in Large Dynamic Networks
Extensible Distributed Coordination
Are Multiagent Systems Resilient to Communication Failures
Foundations of Logic Programming - Lloyd
Logic and Lattices for Distributed Programming — Conway et al. 2012 (BloomL; lattice-typed lifting of CALM)
Relational Transducers for Declarative Networking — Ameloot, Neven & Van den Bussche 2011 (the formal proof of CALM)
A Comprehensive Study of Convergent and Commutative Replicated Data Types — Shapiro et al. 2011 (the CRDT canonical reference)

Conceptual Contribution

Claim: A distributed program is consistent and coordination-free iff it is expressible in monotonic logic — a tight, provable characterisation that converts “distributed consistency is hard” into a precise question about a program’s logical shape.
Mechanism: Formalise programs as networks of Relational Transducers (Ameloot et al.); define Confluence as program-level determinism under non-deterministic delivery; prove biconditional between confluence and monotonic-logic expressibility.
Concepts introduced/used: Monotonic Logic, Confluence, Coordination Avoidance, Relational Transducer, Bloom Language, Dedalus, CRDTs, CAP Theorem, Immutable Data Structures, Tombstones, Stochastic CALM
Stance: foundational / survey
Relates to: Provides the theoretical companion to the Gossip Protocols cluster (Gossip-Based Computation of Aggregate Information, Gossip-based Aggregation in Large Dynamic Networks) — gossip aggregation with mass conservation is exactly a monotonic accumulation, hence coordination-free. Frames why Extensible Distributed Coordination must reach for stored-procedure coordination precisely where programs are non-monotonic. Contrasts with Are Multiagent Systems Resilient to Communication Failures: that paper shows game-theoretic MAS are brittle under message loss — CALM identifies the logical class of programs immune to such loss. The monotonic/non-monotonic split echoes Foundations of Logic Programming - Lloyd’s distinction between Horn-clause logic and Negation as Failure.

Formalise Blockchain Interoperability Patterns

An Approach to Formalise Blockchain Interoperability Patterns

Reference: Guzmán Llambías, Laura González, and Raúl Ruggia (2025). IEEE (preprint, Zenodo). Source file: 13_127.pdf. URL

Summary

Formalises the Temporal Transfer blockchain-interoperability design pattern (instantiated with a gateway/relayer architecture) using Event-B. The authors translate natural-language pattern descriptions into a refined Event-B specification, derive eight safety properties (e.g. token can only be minted on the target chain after being locked on the source), verify them by construction using Rodin, and validate the dynamic behaviour by simulating with ProB.

The contribution is a formal-methods bridge for a family of informally described cross-chain patterns — addressing ambiguity, misinterpretation and lack of guarantees in prior natural-language design-pattern catalogues.

Key Ideas

Event-B refinement captures lock/mint/burn/unlock sequencing across chains
Safety invariants formalise double-spend prevention across ledgers
Rodin discharges proof obligations automatically on invariants/theorems
ProB simulation validates dynamic/functional behaviour of the pattern
Gateway-based Temporal Transfer pattern chosen as instantiation

Connections

Conceptual Contribution

Claim: Blockchain interoperability design patterns — currently specified in ambiguous natural language — can and should be given formal, machine-checkable specifications; Event-B is a suitable vehicle.
Mechanism: Take the Temporal Transfer pattern (gateway-based) and produce an Event-B specification with eight safety properties (lock, mint, transfer, burn, unlock events) refined from abstract to concrete; validate via Rodin/ProB model checker and simulation, discharging Proof Obligations to prove correctness-by-construction.
Concepts introduced/used: Event-B, Refinement, Blockchain Interoperability, Temporal Transfer Pattern, Cross-chain Smart Contracts, Smart Contracts, Formal Verification, Proof Obligations, Model Checking, Design Patterns
Stance: formal / engineering
Relates to: Applies the same formal-specification impulse to cross-chain coordination that Making Smart Contracts Smarter applies to single-chain contract semantics. Shares a methodology with A Modular Approach to Metatheoretic Reasoning for Extensible Languages (refinement, rule-based specs) and a motivation with Agent Communication And Institutional Reality (precise semantics for inter-party protocols).

Tags

Making Smart Contracts Smarter

Reference: Loi Luu, Duc-Hiep Chu, Hrishi Olickel, Prateek Saxena, and Aquinas Hobor (2016). ACM CCS 2016. Source file: 2016-633.pdf. URL

Summary

Investigates security bugs in Ethereum smart contracts arising from a semantic gap between developers’ intuitions and the actual behaviour of the underlying platform. The authors document four classes of vulnerability — transaction-ordering dependence, timestamp dependence, mishandled exceptions, and reentrancy — and formalise a lightweight operational semantics (EtherLite) for EVM execution.

They propose protocol-level remediations (guarded transactions, deterministic timestamps, better exception propagation) and build OYENTE, a symbolic-execution tool that analyses EVM bytecode directly. Running OYENTE on 19,366 live contracts flagged 8,833 as potentially buggy, including TheDAO.

Key Ideas

Semantic gap between Solidity intent and EVM reality causes systemic bugs
Transaction-ordering dependence (TOD): miners reorder within a block
Reentrancy exploited in TheDAO ($60M loss)
Symbolic execution over EVM bytecode as audit tool
“Guarded transactions” proposal: require expected-state precondition

Connections

Conceptual Contribution

Claim: Ethereum smart contracts suffer from a semantic gap between developers’ assumptions and the actual EVM execution model — documenting and fixing this gap at the language-semantics level is critical and tractable.
Mechanism: Identify four concrete bug classes: transaction-ordering dependence (TOD), timestamp dependence, mishandled exceptions (caller must explicitly check return of send), and reentrancy (the DAO vulnerability); formalise a lightweight operational semantics of Ethereum (EtherLite); propose semantic fixes (guarded transactions, deterministic timestamps, exception propagation); build OYENTE, a symbolic-execution tool that scans 19,366 real contracts and flags 8,833 vulnerable.
Concepts introduced/used: Smart Contracts, Transaction-Ordering Dependence, Reentrancy, Operational Semantics, Symbolic Execution, EVM, Semantic Gap, Ethereum, Solidity, TheDAO, Guarded Transactions
Stance: formal-semantic / empirical security
Relates to: Same “formalise ambiguous informal specs” move as Formalise Blockchain Interoperability Patterns. Shares the semantic-gap diagnostic style with PKI Layer Cake - Kaminsky Patterson Sassaman. In the broader vault, complements Agents Secure Interaction in Data Driven Languages and Distributed Security as a case study of formal-method-driven vulnerability discovery.

Tags

Principled Design Of The Modern Web Architecture

Principled Design of the Modern Web Architecture

Reference: Fielding & Taylor (2000). ICSE 2000. Source file: 337180.337228.pdf. URL

Summary

Fielding and Taylor introduce the Representational State Transfer (REST) architectural style as the abstract model that guided the redesign of HTTP/1.1 and URIs. REST is presented as a coordinated set of architectural constraints (client-server, statelessness, cacheability, uniform interface, layered system, code-on-demand) chosen to meet the needs of an internet-scale distributed hypermedia system.

The paper defines REST’s data elements (resource, representation, metadata, control data), connectors (client, server, cache, resolver, tunnel), and components (origin server, gateway, proxy, user agent), and uses multiple architectural views (process, data, connector) to illustrate how they combine. It then evaluates how well HTTP/1.1 and related Web standards conform to REST, using the style to diagnose architectural mismatches (e.g., cookies, embedded frames).

Key Ideas

REST as an architectural style (set of constraints), not an architecture.
Resources are conceptual, addressed by URIs; representations are transferred.
Statelessness and caching for scalability; uniform interface for generality.
Intermediaries (proxies, gateways) enabled by layered connectors.
Mismatches (e.g., cookies, HTML frames) as REST-style violations.

Connections

Conceptual Contribution

Claim: Internet-scale distributed hypermedia requires a disciplined architectural style - REST - derived from specific constraints rather than any particular implementation.
Mechanism: Decomposes architectures into data elements, connectors, and components; derives REST by incrementally adding constraints (client-server, stateless, cache, uniform interface, layered, code-on-demand); evaluates HTTP/1.1, URIs, cookies, frames against the style.
Concepts introduced/used: REST, Uniform Interface, Statelessness, Layered Systems, Resources, Representations, Architectural Styles, Hypermedia
Stance: foundational
Relates to: Provides the architectural substrate for REST-native agent protocols ACP, Agent-to-Agent Protocol and JSON-RPC Model Context Protocol covered in Survey Of Agent Interoperability Protocols; its uniform-interface constraint contrasts with the performative-rich messaging of KQML/FIPA-ACL.

Tags

Programming Erlang Second Edition

Programming Erlang: Software for a Concurrent World (Second Edition)

Reference: Armstrong, J. (2013). The Pragmatic Bookshelf. Source file: cbcl-ref/programming-erlang-2nd-edition.pdf. URL

Summary

Joe Armstrong’s second-edition textbook introduces Erlang as a language and runtime for building highly concurrent, distributed, and fault-tolerant systems. Part I motivates concurrency and tours the shell, modules, and compilation. Part II teaches sequential Erlang: atoms, tuples, lists, pattern matching, funs, records/maps, error handling with try/catch, binaries and the bit syntax, and the type system with Dialyzer.

Part III covers the concurrency primitives (spawn/send/receive), error handling in concurrent programs (links, monitors, supervised fault-tolerance), and distributed programming over Erlang nodes. Part IV covers libraries and frameworks (ports for C interfacing, files, sockets, web/WebSocket applications, ETS/DETS and Mnesia databases, and profiling/debugging/tracing). The book is widely cited as a canonical introduction to the Actor model and the “let it crash” philosophy that informs modern reactive and distributed-agent systems.

Key Ideas

Actor-model concurrency: processes + asynchronous message passing.
“Let it crash” + supervision trees for fault tolerance.
Pattern matching as pervasive control structure.
Distributed programming built on the same primitives as local.
Mnesia, ETS/DETS for in-memory and persistent storage.

Connections

Conceptual Contribution

Claim: Concurrent, distributed and fault-tolerant software is simpler and more reliable when built on isolated processes that share nothing and communicate only by asynchronous messages, with failures handled by supervision rather than defensive programming (“let it crash”).
Mechanism: Armstrong teaches the Erlang trinity of spawn / send / receive, reinforces isolation via immutability and pattern matching, and then layers links, monitors and supervisor trees for systemic recovery. Distribution uses the same primitives as local concurrency, so topology becomes deployment-time. Supporting libraries (ports for C, sockets, ETS/DETS, Mnesia, tracing/profiling, web/WebSocket) show how the model scales to realistic systems.
Concepts introduced/used: Actor Model, Let It Crash, Supervision Tree, Erlang Process, Pattern Matching, Link and Monitor, Mnesia, ETS-DETS, Bit Syntax, OTP
Stance: engineering
Relates to: The practical counterpart to the fault-tolerance philosophy of Theory of Self-Reproducing Automata and the architectural dependability of Architectural Patterns for Dependable Software Systems - SOL; its message-passing primitives underpin agent frameworks surveyed in Intelligent Agents Theory and Practice and mesh with the calculus-level treatment in Secure Communications Processing for Distributed Languages.

Tags

Algorithmic Information Theory - Grunwald Vitanyi

Algorithmic Information Theory

Reference: Peter D. Grünwald and Paul M.B. Vitányi (2008). arXiv:0809.2754v2 (book chapter, Handbook of Philosophy of Information). Source file: 0809.2754v2 (1).pdf. URL

Summary

A tutorial survey of algorithmic information theory (Kolmogorov complexity) and its relationship to Shannon information theory. The authors explain how the amount of information in an individual object can be measured by the length of the shortest program that produces it, and how this quantity — invariant up to an additive constant — supports a non-probabilistic theory of information.

The chapter covers the invariance theorem, uncomputability, relation to entropy, mutual information, the Kolmogorov structure function (separating meaningful/structural from random information), Minimum Description Length, normalized compression distance, and the philosophical implications for Occam’s razor and inductive inference.

Key Ideas

Kolmogorov complexity K(x) as length of shortest program outputting x
Invariance theorem makes K objective up to an additive constant
Structure function separates meaningful (model) from random content
MDL as a practical approximation of ideal algorithmic inference
Entropy is expected Kolmogorov complexity under computable distributions

Connections

Conceptual Contribution

Claim: The information content of an individual object is objectively measured by the length of the shortest program that prints it — Kolmogorov complexity — and this gives a formal basis for Occam’s razor, randomness, and “meaningful” vs “random” information.
Mechanism: Define K(x) via a universal Turing machine (invariance up to additive constant); extend via prefix codes, the Kolmogorov structure function (separating structural/model part from random/noise part), and the Minimum Description Length principle for inductive inference.
Concepts introduced/used: Kolmogorov Complexity, Minimum Description Length, Kolmogorov Structure Function, Shannon Information, Shannon Entropy, Occam’s Razor, Universal Turing Machine, Invariance Theorem, Normalized Compression Distance, Inductive Inference, Prefix Codes
Stance: formal-mathematical / foundational
Relates to: Provides the information-theoretic backdrop for why compact emergent codes arise in Emergence of Grounded Compositional Language in Multi-Agent Populations and Multi-Agent Cooperation and the Emergence of Natural Language; and for the description-length intuition behind compositional protocol negotiation in A Scalable Communication Protocol for Networks of LLMs. Complements Chomsky’s grammar-based view in Three Models for the Description of Language.

Tags

Foundations of Logic Programming - Lloyd

Foundations of Logic Programming (Chapter 1: Preliminaries)

Reference: J. W. Lloyd (1987). Springer-Verlag, Second Extended Edition. Source file: 2022-08-18 13-38-01-Lloyd.pdf. URL

Summary

The opening chapter of Lloyd’s canonical textbook on the mathematical foundations of logic programming. It introduces first-order theories, syntax (alphabets, terms, well-formed formulas, clauses, Horn clauses), interpretations and models, and Herbrand semantics as the preferred route for reasoning about logical consequence of a program.

Lloyd motivates logic programming as Kowalski’s insight that “algorithm = logic + control”: a definite program is a set of Horn clauses (the logic), and the inference strategy (SLD-resolution, search order) is the control. He distinguishes “system” languages (committed-choice, concurrent) from “application” languages (PROLOG-style), and sets up the semantic machinery — Herbrand interpretations, models, logical consequence, unsatisfiability — needed for the rest of the book.

Key Ideas

Algorithm = Logic + Control (Kowalski’s principle)
Horn clauses as the executable fragment of first-order logic
Herbrand universe and base; Herbrand interpretations suffice for clause sets
Definite programs vs normal programs (negation)
SLD-resolution as refutation procedure (developed in later chapters)

Connections

Conceptual Contribution

Claim: Logic — specifically first-order Horn-clause logic with SLD-resolution — can serve as a programming language, where a program is a set of definite clauses, a computation is resolution refutation, and the declarative semantics (Herbrand models, least fixpoint) coincides with the procedural semantics.
Mechanism: Rigorously build up first-order theories, interpretations, Herbrand interpretations/bases, unification, and the T_P fixpoint operator; prove soundness and completeness of SLD-resolution; develop negation-as-failure, the Closed World Assumption, and semantics of normal programs; treat Prolog as the canonical realisation of the Kowalski slogan “algorithm = logic + control”.
Concepts introduced/used: Logic Programming, Horn Clauses, SLD Resolution, Herbrand Universe, Unification, Negation as Failure, Fixpoint Semantics, Prolog, Closed World Assumption, First-Order Logic, Algorithm = Logic + Control
Stance: formal / foundational textbook
Relates to: Theoretical substrate for Agent-Oriented Programming, ACRE Agent Conversation Reasoning Engine, and Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents (all of which assume BDI agents implemented in logic-programming languages). The mentalistic-semantics side of ACLs (KQML as an Agent Communication Language, FIPA-ACL) presupposes Lloyd-style logical machinery.

Tags

Assigning Meanings to Programs

Reference: Robert W. Floyd (1967). Proceedings of Symposia in Applied Mathematics, Vol. 19, pp. 19-32 (AMS). Source file: FloydMeaning.pdf. URL

Summary

Floyd’s foundational paper establishes a rigorous, axiomatic basis for proving properties of programs — correctness, termination, equivalence — by attaching propositions (tags) to the edges of a flowchart. A verification condition for each command type guarantees that if the tag on its entrance edge is true when control arrives, then the tag on its exit edge is true when control leaves. Induction over execution then proves global properties like “if initial values satisfy R1, final values satisfy R2”.

The paper defines completeness and consistency of a semantic definition, gives general axioms (axioms 1-4 and corollaries), and derives verification conditions for assignment, conditional branch, join, start, and halt in a simple flowchart language, then extends the approach to fragments of ALGOL. It is a foundational work in axiomatic semantics, directly inspiring Hoare logic.

Key Ideas

Interpretation = mapping from flowchart edges to propositions.
Verification condition per command type enforces local soundness.
Global correctness by induction over execution steps.
Semantic definition should be complete and consistent.
Termination proofs by showing a well-founded quantity strictly decreases.

Connections

Language Workbenches
Agent-Oriented Programming
Verifiable Semantics
Code as Data
Intent Formalization - A Grand Challenge for Reliable Coding — Floyd/Hoare specs as the LLM-era correctness oracle
Making Smart Contracts Smarter — semantic-gap diagnostics in a blockchain setting
Hoare Logic

Conceptual Contribution

Claim: A programming language’s semantics can be defined independently of any implementation by attaching propositions to flowchart edges and constructing per-command verification conditions; global program properties then follow by induction.
Mechanism: Flowchart interpretation as a map from edges to propositions; four general axioms governing verification conditions; derivation of V_c for assignment, branch, join, start, halt; extension to an ALGOL subset (conditional, goto, for, compound, declarations); termination via well-founded decreasing quantities.
Concepts introduced/used: Axiomatic Semantics, Verification Condition, Strongest Verifiable Consequent, Consistency and Completeness, Inductive Assertions, Termination Proof
Stance: foundational / formal-semantic
Relates to: Direct ancestor of Hoare logic and of every verifiable-semantics move in the vault, including Verifiable Semantics for ACLs which transports Floyd/Hoare-style program semantics into the ACL-conformance question. Foundational for Foundations of Logic Programming - Lloyd and reasoning tools in A Modular Approach to Metatheoretic Reasoning for Extensible Languages.

Tags

BAN Logic

The belief logic of Burrows, Abadi & Needham (1990) for analysing cryptographic authentication protocols. A small modal language with operators P believes X, P sees X, P said X, P controls X, fresh(X), P shares K with Q. Inference rules (message-meaning, nonce-verification, jurisdiction) propagate beliefs as messages are received and decrypted. Verification proceeds by idealising the protocol, stating initial beliefs, and deriving the goal beliefs (typically: authenticated session-key agreement). The first widely-adopted formal method for protocol analysis; superseded by Spi Calculus / ProVerif for rigorous use, but still pedagogically dominant.

In this vault

Spi Calculus

Abadi & Gordon’s (1997) extension of the Pi-Calculus with cryptographic primitives — encryption, decryption, hashing, pairing, name-equality. Security properties (authentication, secrecy) are formalised as process equivalences: a protocol is secure iff no spi-calculus context can distinguish it from an idealised specification. The most general attacker is just an arbitrary spi process. Foundation under ProVerif / Tamarin and the applied π-calculus (Abadi & Fournet 2001).

In this vault

Mobile Ambients

Reference: Cardelli, L. & Gordon, A. D. (1998). Mobile Ambients. In Foundations of Software Science and Computational Structures (FoSSaCS ’98), LNCS 1378, pp. 140–155, Springer. Journal version: Theoretical Computer Science 240(1), pp. 177–213, 2000. DOI · Open access PDF (UPenn)

Summary

Cardelli and Gordon argue that the Pi-Calculus models communication elegantly but does not natively model administrative domains — the bounded, named, hierarchically nested regions across which computation moves on the actual Internet (firewalls, address spaces, processes, machines, networks). Their ambient calculus makes the location itself the primary mobile entity. An ambient n[P] is a named bounded region containing a process P. A small set of capabilities — in n.P, out n.P, and open n.P — drive movement: in n enters a sibling ambient named n; out n exits the parent ambient if it is named n; open n dissolves the boundary of a child ambient named n, merging its contents with the current location. Communication is local: (x).P reads from a shared anonymous channel within the surrounding ambient. Mobility and access control reduce to one question — does a process possess the capability to cross a particular boundary? The calculus has standard structural-congruence-and-reduction operational semantics, a logical companion (the ambient logic, with location-modal connectives), and type systems regulating mobility. It supplies the formal substrate for reasoning about agents that physically relocate — mobile-code platforms, container migration, and (today) WASM components moving between hosts.

Key Ideas

Locations as first-class movable entities: the basic mobile thing is a named bounded region, not a name-as-channel; this captures administrative-domain structure that pure π struggles to express.
Three capabilities — in, out, open — suffice: every mobility scenario reduces to a sequence of crossings governed by capability possession; access control becomes “do you have the capability name?”
Spatial nesting as syntax: ambient terms form trees n[P | m[Q] | …]; the structural-congruence laws are spatial as well as algebraic. The ambient logic adds location modalities (@n reads “at ambient n”) for spatial reasoning.
Bounded computation: an ambient acts like a bag carrying its computation; its contents proceed concurrently inside the boundary, distinct from the outside world.
Communication restricted to local anonymous channels: a deliberate departure from π’s named channels — values are read off the local “ether” within an ambient. Gives an asymmetric model where mobility is global but communication is local.
Type systems for mobility: subsequent work (Cardelli, Ghelli, Gordon 1999/2000) gives type disciplines that statically constrain which ambients may cross which boundaries — the ancestor of capability-typed mobile-code systems.
Deliberate engineering target: motivated explicitly by Java applets, Telescript-style mobile agents, and firewall-bounded computation — process-calculus theory aimed at the engineering reality of distributed systems.

Connections

Conceptual Contribution

Claim: Modelling internet-scale distributed computation requires a process calculus in which the location is the primary mobile entity, not the channel; three boundary-crossing capabilities (in, out, open) suffice to express administrative-domain mobility, and capability possession is the natural account of access control.
Mechanism: A process language extending π-style parallel composition with ambient brackets n[P] and capability prefixes; small structural-congruence-and-reduction operational semantics; an ambient logic with spatial / location modalities; type systems controlling which ambients can perform which capabilities.
Concepts introduced/used: Mobile Ambients, Ambient Calculus, Capabilities (Ambient), Mobility, Spatial Logic, Boundary (administrative domain).
Stance: foundational technical paper.
Relates to: Sibling of the Pi-Calculus — both Milner 1992 and Cardelli & Gordon 1998 lift CCS-style fixed-topology concurrency, but along different dimensions (channel-mobility vs location-mobility). Conceptually upstream of all capability-based mobile-agent security work in the vault: Agent Tcl Flexible Secure Mobile Agents and DAgents Security Book Chapter take the engineering view, while ambients give the formal model. The capability-as-token view aligns directly with Capability Security (Dennis & Van Horn 1966, Miller’s E lineage in Robust Composition - Towards a Unified Approach to Access Control and Concurrency Control) — possession of a capability name confers, and only confers, the right to act. Modern realisations include WebAssembly modules with WASI capabilities, container ingress/egress, and sandboxed JS with capability-secured imports — a re-discovery of ambient-style boundary control under different syntactic skins.

Tags

#process-calculi #mobile-ambients #cardelli #gordon #mobility #capability-security #foundations

Pact - A Choreographic Language for Agentic Ecosystems

Pact: A Choreographic Language for Agentic Ecosystems

Reference: Gopinathan, K., Feser, J., Naim, M., Tavares, Z. & Bingham, E. (2026). 2nd International Workshop on Choreographic Programming (CP 2026), Boulder, CO, June 15–19. arXiv:2605.03143v1 [cs.PL], 4 May 2026 (talk paper). Basis Research Institute. URL

Summary

Gopinathan et al. extend Choreographic Programming to the open-systems setting where participants are self-interested and may not faithfully execute a protocol. Choreographies (Montesi 2023; Bates et al. 2025) give correct-by-construction, deadlock-free distributed protocols by writing one global program that is mechanically projected to local endpoints, but they assume cooperative participants — they cannot answer why an autonomous agent should follow the projected protocol. Pact answers that question by adding three operators to a core choreographic calculus: agent.choose(τ) for explicit strategic non-determinism, agent.values(x) for declared utility dependencies, and world.choose(τ) for exogenous “nature” variables that capture each agent’s priors over the environment. Every Pact program then maps unambiguously to a formal extensive-form game.

The headline analysis is a decision-policy solver built on the Memo Programming Language (Chandra et al. 2025), a probabilistic-programming DSL for cognitive theory-of-mind models. From the projected Pact program a memo model is constructed in which each role recursively simulates the other to depth ℓ; running inference yields a level-ℓ bounded-rational policy mapping observations to choices. Applied to the canonical book-seller choreography the solver recreates Akerlof’s Market for Lemons: at depth 0 the buyer naïvely treats price as a signal of quality and the seller exploits this; as ℓ grows the acceptance probability flattens. The implementation is an embedded Python DSL on top of the Effectful algebraic-effects library, with endpoint projection realised as effect handlers. The paper is positioned as preliminary work; next steps named are formalising the semantics, proving correctness of projection-to-game, and adding incentive-compatibility / equilibrium / mechanism-design analyses.

Key Ideas

Choreography + game theory: a global protocol gets three game-theoretic operators (choice, value, nature) so that endpoint projection produces both a runnable program and a formal game.
values as type signature, not utility: declarations name the variables that influence an agent’s payoff but not the function — utilities are private and adversarially incentive-incompatible to disclose. The role of values is to constrain which protocols are mutually negotiable.
Theory-of-mind solver via memo: bounded-rational level-ℓ recursion over agent models, with the recursion bottoming out at naïve priors at ℓ = 0.
Lemons re-derived from a choreography: information asymmetry over an exogenous book.quality variable is enough to reproduce Akerlof’s unravelling result on the bookseller protocol.
Algebraic-effects implementation: endpoint projection implemented as effect handlers in Python (effectful); choreography is a single program that runs differently depending on which handler (Endpoint Projection) is installed.
Motivation framed against LLM agent failure modes: prompt injection, sycophancy, and coercion of LLM agents are cited as the reasons untrusted-counterpart coordination needs formal protocol artefacts rather than free-form natural-language negotiation.

Connections

Conceptual Contribution

Claim: Choreographic protocols for autonomous-agent ecosystems should make agent strategy first-class — explicit choices, declared utility dependencies, and exogenous priors — so that every protocol corresponds to a formal game and can be analysed for whether self-interested agents will participate.
Mechanism: Three new constructs added to a core choreographic calculus (agent.choose, agent.values, world.choose); a structural map from Pact programs to extensive-form games; a level-ℓ bounded-rational decision-policy solver built by translating the projected program into a Memo Programming Language theory-of-mind model and running probabilistic inference over it; an embedded-DSL implementation in Python via algebraic effects realising endpoint projection.
Concepts introduced/used: Choreographic Programming, Endpoint Projection, Theory of Mind, Memo Programming Language, Bounded Rationality, Market for Lemons, Mechanism Design, Algebraic Effects, Negotiation, Game-Theoretic Trust, Mentalistic Semantics
Stance: position / preliminary engineering (CP 2026 workshop talk paper)
Relates to: A contemporary LLM-era restatement of the individual-rationality answer to “why follow a protocol?” first formalised by Deals Among Rational Agents (Rosenschein & Genesereth 1985) and lifted to mental attitudes by Intention Is Choice with Commitment (Cohen & Levesque 1990). The paper is structurally adjacent to — but does not engage — the entire commitment-protocol tradition: Flexible Protocol Specification and Execution (Yolum & Singh 2002) gives a global protocol semantics in the Event Calculus with explicit Create / Discharge / Cancel / Release / Assign / Delegate operations whose runs project to local agents in a way directly analogous to choreographic endpoint projection, and A Commitment-Based Approach to Agent Communication (Fornara & Colombetti 2004) gives an operational FSM semantics for the same primitives. ACL Rethinking Principles (Singh 1998) and Verifiable Semantics for ACLs (Wooldridge 1998) anticipate the central limitation: a semantics grounded in agent utilities and recursive belief models is unverifiable from message traces alone — the very failure modes the paper opens with (prompt injection, sycophancy, coercion) destabilise the priors and rationality assumptions the solver depends on. The Lemons demo, taken at face value, is an argument for institutional / commitment mechanisms (warranties, refund obligations, certification) of the kind Singh’s programme articulates rather than for theory-of-mind solving. The constructive synthesis the paper does not propose is to layer commitment operations onto the choreographic substrate so that protocols carry both a public, observable commitment trace (Singh-style verifiability) and a game-theoretic acceptability analysis (Pact-style strategic reasoning); choreographies are a particularly natural host because endpoint projection already gives the global-to-local move that Commitment Machines approximates by FSM compilation. On the LLM-agent side the paper’s diagnosis converges with Why AI Agents Communicate In Human Language (formal protocol artefacts beat free-form natural-language negotiation) and complements the standardisation argument of LLM Agent Communication Protocol Requires Urgent Standardization.

Tags

Multiparty Asynchronous Session Types

Reference: Honda, K., Yoshida, N. & Carbone, M. (2008). Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL ’08), San Francisco, CA, pp. 273–284. ACM. DOI: 10.1145/1328438.1328472. Journal version: Journal of the ACM 63(1):9, 2016, DOI: 10.1145/2827695. Source file: honda-yoshida-carbone-popl08.pdf. URL

Summary

Honda, Yoshida and Carbone generalise the binary session-type discipline of Honda (1993) and Honda-Vasconcelos-Kubo (1998) to multiparty asynchronous communication: a single global type describes the interaction protocol among N ≥ 2 participants, and per-participant local types are derived by a syntactic projection function that translates each global statement into the participant’s local view of it. A process calculus extending the asynchronous π-calculus is typed against these local types; the central technical result is the subject reduction and progress theorem: a system of well-typed processes is deadlock-free, communication-safe (no message-type mismatch), and session-fidelity-preserving (the runtime trace conforms to the global type, projected). This three-tier structure — global types, local types via projection, processes typed against local types — is the formal foundation that the entire contemporary multiparty session-types and choreographic-programming literature inherits.

The paper’s intellectual contribution is to make the global protocol a typed object whose well-formedness can be checked once, with the well-typedness of every projected role following automatically. Where binary session types describe the obligations of two endpoints separately and rely on duality, multiparty session types describe the joint protocol once and project to as many roles as needed, with a coherence condition (each branching point is observed by every relevant participant) ensuring projections are mutually consistent. The treatment is asynchronous: send is non-blocking, messages are buffered in per-channel queues, and the type system tracks the resulting message-order obligations. The framework is the direct precursor of contemporary choreographic-programming languages (Choral, HasChor, ChoRus, Pact) and of the runtime-monitoring theory developed in On the Monitorability of Session Types.

Key Ideas

Global type: a single typing artefact G describing the interaction among N participants — primitives include p → q : ⟨S⟩.G (participant p sends a value of type S to q, then G), branching p → q : {ℓᵢ : Gᵢ}, recursion μt.G, and parallel composition.
Local type / projection: G ↾ p is the projection of G to participant p, syntactically translating each global statement into the corresponding send/receive/select/branch from p’s perspective.
Coherence (well-formedness): a global type is well-formed iff every choice point is observed by every relevant participant — the multiparty analogue of the connectedness condition in Structured Communication-Centred Programming for Web Services.
Asynchronous π-calculus substrate: processes communicate over typed session channels with non-blocking send and FIFO queues; each session is opened with a fresh name and closed structurally.
Subject reduction: well-typedness is preserved under reduction.
Communication safety: no well-typed system ever sends a value whose type the receiver does not expect.
Session fidelity / progress: the runtime trace of a well-typed system is a refinement of the projected local types, and well-typed systems whose buffers are empty cannot deadlock.
Type-driven engineering payoff: type-check the global protocol once, get communication-safety guarantees for every role for free.

Connections

Conceptual Contribution

Claim: Multiparty distributed communication is best disciplined by a single global type describing the joint protocol of all participants, from which per-participant local types are derived by mechanical projection; well-typedness of the global type plus a coherence condition ensuring choice points are observed by all relevant parties is sufficient to guarantee that every projected process is communication-safe, deadlock-free, and faithful to the global protocol.
Mechanism: Define global types as a calculus over N ≥ 2 participants with sending, branching, recursion, parallel composition; define local types as session types with send/receive/select/branch; define a syntactic projection G ↾ p from global to local types per participant; type processes (extended asynchronous π-calculus with FIFO message buffers) against the projected local types; prove subject reduction (well-typedness preserved under reduction), communication safety (no type-mismatched messages), and progress (well-typed systems with empty buffers do not deadlock).
Concepts introduced/used: Session Types, multiparty session types, global type, local type, projection, coherence, subject reduction, asynchronous π-calculus, communication safety, session fidelity
Stance: foundational / formal-semantic
Relates to: Companion to Structured Communication-Centred Programming for Web Services (Carbone-Honda-Yoshida ESOP 2007 / TOPLAS 2012) — the two papers together establish the modern global types → local types → processes pipeline that all subsequent choreographic-programming and multiparty session-types work inherits. Without the multiparty extension here, the binary session-type substrate of Carbone-Honda-Yoshida 2007 cannot scale to the N-participant choreographies that real protocols need. Underwrites the contemporary textbook Introduction to Choreographies (Montesi 2023). Provides the type-system substrate that On the Monitorability of Session Types (Bartolo Burlò et al. ECOOP 2021) lifts into a runtime-monitoring theory, and that Pact - A Choreographic Language for Agentic Ecosystems adds game-theoretic operators on top of. The structural counterpart in the agent-communication tradition is Commitment Machines - Yolum and Singh / Flexible Protocol Specification and Execution: both lineages (multiparty session types ↔ Yolum-Singh commitment protocols) take a globally-specified N-participant protocol, project to per-role views, and prove the projection preserves a key correctness property (communication safety here, commitment discharge there). The π-calculus substrate descends from Communicating Sequential Processes (Hoare 1978) and Milner’s π-calculus.

Tags

Scope Extrusion

The structural rewrite of the Pi-Calculus under which a restricted (private) name escapes its original scope when communicated to a process outside that scope. Formally: (νx)(P | Q) ≡ (νx)P | Q when x ∉ fv(Q), combined with the communication of x from P into Q extends the binder to cover both. This is the formal mechanism of Mobility in π — the only rewrite needed to capture all of dynamic-topology concurrent computation.

In this vault

Name-Passing

The defining primitive of the Pi-Calculus: a communication action transmits a name (channel) over another name. Because the transmitted name may itself be used as a channel by the recipient, communication and the dynamic reconfiguration of the communication network become a single operation. Name-passing is what distinguishes π from the fixed-topology process algebras CCS and CSP. In a session-typed setting the name carries a type describing how the recipient may use it — the foundational mechanism behind Session Types and endpoint projection.

In this vault

A Calculus of Mobile Processes

A Calculus of Mobile Processes (Parts I and II)

Reference: Milner, R., Parrow, J. & Walker, D. (1992). A Calculus of Mobile Processes, I and II. Information and Computation, 100(1), pp. 1–40 and pp. 41–77. (Reports appeared as ECS-LFCS-89-85 and -86, Edinburgh, 1989.) Companion textbook: Milner, R. (1999). Communicating and Mobile Systems: the π-Calculus. Cambridge University Press. DOI · Open access (Edinburgh)

Summary

Milner, Parrow and Walker introduce the π-calculus, a process calculus in which the names exchanged between processes are themselves the channels of communication. The earlier CCS (Milner 1980) had a fixed communication topology — process structure determined which agents could synchronise. The π-calculus drops that restriction: a single primitive, the output of one name on another (x̄⟨y⟩), simultaneously transmits a capability to communicate and reconfigures the network. The paper develops the calculus in two parts: Part I gives the syntax (input prefix, output prefix, parallel composition, restriction (νx), replication !P, summation +, match [x=y]), the structural-congruence-and-reduction operational semantics, and proves the basic algebraic theory; Part II develops a higher-order extension and the labelled-transition / bisimulation theory (early, late, and open variants of strong and weak bisimulation). The headline expressive result, established in detail in Milner’s companion Functions as Processes (1992), is that the lazy and call-by-value λ-calculi embed faithfully into the π-calculus — concurrent computation strictly subsumes sequential functional computation. The calculus has since become the standard substrate for reasoning about Mobility, Concurrency, and Session Types, and is the formal predecessor of every choreographic / multiparty-session-type result in this vault.

Key Ideas

Name-passing as the unifying primitive: a single output prefix x̄⟨y⟩.P transmits a name y over channel x; the receiver x(z).Q binds z to y and may then use it as a channel — communication and channel reconfiguration become one operation.
Restriction (νx)P: introduces a fresh, private name; combined with output, it gives scope extrusion — when a private name is communicated outside its scope, the scope expands to include the recipient. This is the formal mechanism of mobility.
Replication !P: the calculus’s only recursion construct, equivalent to P | !P; supports unbounded parallelism without an explicit fix-point.
Three bisimulation styles: early (instantiate the bound name before the transition), late (transition on a name-abstraction), open (transitions parametric in a substitution closure) — different congruence properties; open bisimulation is preserved by all contexts.
λ encodes into π: lazy and call-by-value λ-calculi translate compositionally into π, with β-reduction simulated by communication. Sequential function application is a degenerate case of concurrent name-passing.
Polyadic and monadic forms: tuples of names (x̄⟨y₁,…,yₙ⟩) can be encoded into the monadic calculus; this encoding is the basis of Sorts / type systems for π, and of session types.
Single-paper foundation for an entire research programme: Hoare’s CSP and Milner’s earlier CCS supplied process algebra over fixed topologies; π-calculus made the topology itself first-class data.

Connections

Conceptual Contribution

Claim: A single primitive — the communication of names along names — suffices to express both classical concurrency (CCS-style fixed-topology synchronisation) and the dynamic reconfiguration of communication networks; the resulting calculus subsumes the λ-calculus and serves as a universal substrate for mobile, concurrent computation.
Mechanism: Reduction-and-congruence operational semantics over a small syntax (input/output prefix, |, (νx), !, +, [x=y]); scope extrusion as the single rewrite rule that lets restricted names escape their original scope when communicated; early/late/open bisimulation as compositional behavioural equivalences; λ-encoding via continuation-passing-style translation into name communication.
Concepts introduced/used: Pi-Calculus, Name-Passing, Scope Extrusion, Mobility, Bisimulation (early, late, open), Replication, Restriction, Sorts (precursor to session types), Higher-Order Pi-Calculus.
Stance: foundational technical paper / textbook calculus.
Relates to: Direct ancestor of Session Types (Honda et al., where the name being passed carries a type describing how the recipient may use it) and through them of Multiparty Asynchronous Session Types and Structured Communication-Centred Programming for Web Services — the entire choreographic-programming line in this vault, including Pact - A Choreographic Language for Agentic Ecosystems, rests on π-calculus reductions as the underlying small-step semantics. Mobile Ambients (Cardelli & Gordon 1998) is a sibling calculus that makes locations rather than names the primary mobile entity, motivated by the difficulty of expressing administrative domains in pure π. Spi Calculus (Abadi & Gordon 1997) extends π with cryptographic primitives for protocol verification — directly relevant to the agent-security threads. Join Calculus (Fournet & Gonthier 1996) is an asynchronous, join-pattern reformulation amenable to distributed implementation. The encoding of λ into π reframes Hewitt actors as a particular discipline of π usage and supplies the formal grounding for asynchronous-message-passing concurrency in actor-based systems like Erlang. On the agent-communication side π is the missing semantic substrate for Conversation Policy and Interaction Protocols: a KQML/FIPA performative exchange is — operationally — π-calculus name-passing constrained by an ontological vocabulary, a fact made explicit by every session-typed reformulation of ACL conversations.

Tags

#process-calculi #pi-calculus #concurrency #mobility #foundations #milner #bisimulation #session-types-foundation

A Calculus of Communicating Systems

Reference: Milner, R. (1980). A Calculus of Communicating Systems. Lecture Notes in Computer Science 92, Springer-Verlag. Companion paper: Milner, R. (1989). Communication and Concurrency. Prentice Hall. Springer (LNCS 92) · Edinburgh Research Explorer (Citation only — book.)

Summary

Milner introduces CCS, the first algebraic process calculus to make synchronisation rather than shared state the foundation of concurrency. A CCS process is built from action prefix (a.P), summation (P + Q), parallel composition (P | Q), restriction (P \ L), relabelling (P[f]), and (constant) recursion. Communication is synchronous handshake between complementary actions a and ā — paired transitions yield a silent τ. The technical heart of the monograph is the development of observational equivalence (later refined by Park into bisimulation) as a behavioural equivalence preserved by all CCS contexts: two processes are equivalent iff they can match each other’s transitions step-for-step. Earlier Milner had developed the equivalence over synchronisation trees — tree unfoldings of the LTS — and shown that CCS is sound and complete for strong equivalence given a finite axiomatisation. The calculus served as the workhorse for ten years of process-algebra research and is the direct predecessor of the Pi-Calculus, which lifted CCS’s fixed-topology assumption by making channel names mobile values. The 1989 Communication and Concurrency book is the more polished re-presentation that most readers cite.

Key Ideas

Synchronous handshake as the primitive: complementary actions on a shared name produce a silent step; concurrency is communication, not interleaving over a heap.
Algebraic, not denotational: the meaning of a CCS term is given by its position in an equational theory under bisimulation, not by translation into a domain. Laws like P + 0 = P, (P | Q) | R = P | (Q | R), and the expansion law (P | Q distributes over a sum of all possible synchronisations) form the calculational kit.
Synchronisation tree: the LTS unfolded as an action-labelled tree; equivalences over LTSs lift to equivalences over trees.
Observational equivalence ≈ bisimulation: invented and refined within the CCS programme; the standard behavioural equivalence ever since.
Restriction P \ L: hides a set of action names from the environment, forcing them to synchronise within P — this is what later inspires π’s (νx) binder, generalised to fresh names.
Recursion via constants: rather than fix-point operators, CCS uses named process equations A ≜ a.A, simpler to manipulate algebraically.
Limitations that motivate π: communication topology is fixed at a process’s birth — there is no way for a.P to communicate b to a peer who could then use b to communicate further. This restriction is exactly what name-passing in π lifts.

Connections

Conceptual Contribution

Claim: Concurrency can be developed as an algebraic theory of synchronisation in which the meaning of a process is determined by an observational equivalence preserved under all contexts; communication, not shared state, is the right primitive.
Mechanism: A small term language (prefix, sum, parallel composition, restriction, relabelling, named recursion); structural-operational-semantics rules deriving a labelled transition system; observational equivalence (≈ bisimulation) preserved by all syntactic contexts, with a complete equational axiomatisation in the finite case.
Concepts introduced/used: CCS, Synchronisation Tree, Observational Equivalence, Bisimulation, Process Calculi, Structured Operational Semantics (developed by Plotkin in dialogue with the CCS programme).
Stance: foundational technical monograph.
Relates to: Sibling of Communicating Sequential Processes (Hoare 1978), which uses an event-trace semantics and refinement orderings rather than bisimulation. Direct ancestor of the Pi-Calculus (A Calculus of Mobile Processes) which keeps the algebraic methodology but lifts the topology restriction. The actor-model line (Hewitt 1973, realised industrially in Erlang) takes asynchronous, mailbox-based messaging as primitive — historically opposed to CCS’s synchronous handshake but reconciled in asynchronous π and the Join Calculus. CCS supplies the underlying behavioural-equivalence machinery used (often implicitly) when reasoning about Conversation Policy equivalence in the ACL literature: two protocols are “the same” iff they bisimulate.

Tags

#process-calculi #ccs #milner #concurrency #foundations #bisimulation #synchronisation

Communicating Sequential Processes

Reference

Hoare, C. A. R. (1978). “Communicating Sequential Processes.” Communications of the ACM, 21(8), 666-677. URL

Summary

Hoare proposes that input, output, and concurrent composition of processes deserve the same foundational status as assignment, sequencing, and iteration. CSP is a small language in which programs are built from sequential processes that synchronise by unbuffered, typed message exchange over named channels. A send P ! v and a matching receive Q ? x rendezvous: neither proceeds until both are ready. Dijkstra’s guarded commands — with nondeterministic choice — are generalized so that a guard may include a communication action, yielding a clean treatment of external choice, alternation, and fair scheduling.

The paper walks through a progression of examples — coroutines, prime sieve, matrix multiplication, bounded buffer, recursive subroutines implemented as processes, the dining philosophers — demonstrating how seemingly exotic concurrent patterns become compact CSP programs. Hoare’s deliberate methodological stance is that structured concurrency can be as tractable as structured sequential programming, provided the primitives are well-chosen: synchronous rendezvous avoids the subtleties of mailboxes and shared state; named channels make communication explicit in the program text; guarded commands make nondeterminism principled.

CSP seeded a lineage of enormous practical and theoretical impact: occam (the transputer language), the CSP process algebra (Hoare 1985, Roscoe) with refinement-based verification via FDR, the Go programming language’s goroutines and channels, Rust’s std::sync::mpsc, and the modern “structured concurrency” revival. Together with Hewitt’s actors, CSP defines one of the two great alternatives to shared-memory threads.

Key Ideas

Synchronous message passing: unbuffered rendezvous between named processes; no shared memory.
Named channels / named processes: communication is part of program structure, syntactically explicit.
Guarded commands with I/O guards: nondeterministic alternation and repetition over communications.
Parallel composition (||): processes execute concurrently, synchronizing only at matched send/receive.
No implicit buffering: forces designers to reason about liveness and deadlock directly.
Refinement and equivalence: later formalized as a process algebra with bisimulation / failures refinement.
Structured concurrency: parallelism as a first-class program-structuring mechanism, not threads-as-afterthought.

Connections

Actor Model — the other great message-passing tradition; CSP is channel-centric where actors are mailbox-centric.
A Universal Modular Actor Formalism for Artificial Intelligence
Hoare Logic — Hoare’s earlier work on axiomatic reasoning underlies his insistence on structured primitives.
Time Clocks and the Ordering of Events in a Distributed System — rendezvous provides a stronger local synchrony than Lamport’s messages.
Let It Crash

Conceptual Contribution

Process Calculi

A family of formal languages for describing concurrent and distributed systems algebraically. A process calculus fixes a small syntax of process terms (parallel composition, action prefix, restriction, choice) and gives an operational semantics — usually as a labelled transition system — together with a behavioural equivalence such as Bisimulation. Canonical members:

CCS (Milner 1980) — fixed-topology synchronisation.
CSP (Hoare 1978) — synchronous channel rendezvous; refinement-based equivalences.
ACP (Bergstra & Klop 1984) — equational laws as primary; ad-hoc-extensible signature.
π-calculus (Milner, Parrow & Walker 1992) — name-passing; mobile communication topology.
Mobile Ambients (Cardelli & Gordon 1998) — mobile locations.
Join calculus (Fournet & Gonthier 1996) — asynchronous; pattern-matching on joins.
Spi calculus (Abadi & Gordon 1997) — π + cryptographic primitives.
Applied π-calculus (Abadi & Fournet 2001) — equational theories over terms.

Process calculi supply the formal substrate underneath Session Types, Choreographic Programming, and most modern accounts of distributed-system semantics.

In this vault

A Common Ontology Of ACLs

A Common Ontology of Agent Communication Languages: Modeling Mental Attitudes and Social Commitments using Roles

Reference: Boella, Damiano, Hulstijn, van der Torre (2006). Applied Ontology 3(1-3). Source file: ao07b.pdf. URL

Summary

The authors propose a common ontology that bridges two dominant semantic traditions for Agent Communication Langua mental-attitude-based semantics (FIPA-ACL) and social-commitment-based semantics (Singh, Colombetti). The unifying device is the role: each agent plays role instances in dialogue sessions, and both beliefs/intentions and commitments are attributed to role instances rather than to private mental states, sidestepping the unverifiability problem.

They develop Role-SL, a BDI logic extended with roles and dialogue sessions, and show translation schemes from FIPA speech acts and from actioandopositional commitment semantics into this role-based ontology. The framework accommodates mixed dialogues (e.g., persuasion intertwined with negotiation) that neither tradition handles cleanly alone.

Key Ideas

Roles as first-class carriers of public mental attitudes.
Role-SL: extension of FIPA-SL with role instances and dialogue sessions.
Mappings from FIPA-ACL and commitment-based ACLs into one ontology.
Public beliefs/intentions sidestep mental-state unverifiability.
Distinguishes action commitments (request/propose) from propositional (assert/challenge).

Connections

Conceptual Contribution

Claim: Mental-attitude and social-commitment ACL semantics can be unified under a common ontology by attributing both to roles instantiated in dialogue sessions, rather than to private agent minds.
Mechanism: Extends FIPA-SL into Role-SL (BDI + roles + dialogue sessions); provides translation schemes from FIPA speech acts and from action/propositional commitment semantics; handles mixed dialogues (persuasion + negotiation).
Concepts introduced/used: Roles, BDI, Commitment-based Semantics, Mental Attitudes, Mentalistic Semantics, Public Semantics, Verifiable Semantics, Dialogue Sessions, FIPA-ACL, Speech Act Theory, Ontologies, Agent Communication Languages
Stance: formal-semantic
Relates to: Bridges the two traditions typified by FIPA-ACL (mentalist) and Agent Communication And Institutional Reality (commitment-based); uses ontology machinery catalogued in Handbook On Ontologies.

Tags

Ontology Change Classification and Survey

Ontology Change: Classification and Survey

Reference: Flouris, Manakanatas, Kondylakis, Plexousakis, Antoniou (2008). The Knowledge Engineering Review, Cambridge University Press. Source file: Ontology_Change_Classification_and_Survey.pdf. URL

Summary

This survey tackles the terminological confusion surrounding ontology change in the Semantic Web era. The authors argue that many overlapping terms — ontology evolution, versioning, merging, mapping, matching, articulation, translation, debugging, integration, morphism — are used inconsistently across the literature, creating a major bottleneck for research. They propose a unifying terminology and taxonomy, fixing precise definitions and identifying the boundaries between ten subfields of ontology change plus ontology alignment.

The paper organizes these subfields into four groups: heterogeneity resolution (mapping/matching/articulation/morphism/translation), modification (evolution, debugging/diagnosis/repair), fusion (integration, merging), and versioning. Each field is characterized by its purpose, inputs, outputs, and properties, and the authors review representative algorithms and systems, including a detailed classification of matching approaches (instance vs. schema, element vs. structure, language vs. constraint, matching cardinality, auxiliary information).

Key Ideas

Ontology change is the generic process of adapting an ontology to a need for change.
Heterogeneity resolution is a prerequisite for any successful ontology change.
Formal pair <S, A> defines an ontology by signature and axioms.
Ten interlinked subfields are identified and disambiguated.
Ontology evolution is closely tied to belief revision.

Connections

Conceptual Contribution

Claim: Research on ontology change is fragmented by inconsistent terminology; a precise, unified taxonomy is needed before the field’s problems can be compared, composed, or solved.
Mechanism: The authors define an ontology formally as a signature–axiom pair <S,A>, then enumerate ten subfields (mapping, matching, morphism, articulation, translation, evolution, debugging, versioning, integration, merging) and characterise each by inputs/outputs/properties. Representative algorithms and systems are then slotted into the taxonomy, with matching approaches classified by dimension (schema vs. instance, element vs. structure, cardinality, auxiliary info).
Concepts introduced/used: Ontology Change, Ontology Evolution, Ontology Mapping, Ontology Merging, Ontology Alignment, Belief Revision, Semantic Web, Heterogeneity Resolution
Stance: survey
Relates to: Provides the vocabulary implicitly assumed by ACL work on shared ontologies (The State of the Art in Agent Communication Languages, Trends in Agent Communication Language) and complements the handbook-level treatment in Handbook On Ontologies. Its belief-revision framing links to epistemic semantics used in Agent-Oriented Programming.

Tags

Handbook On Ontologies

Handbook on Ontologies

Reference: Staab & Studer, eds. (2004). International Handbooks on Information Systems, Springer. Source file: CAP_LIB_05.pdf. URL

Summary

The Handbook on Ontologies provides a comprehensive reference on ontology research and practice. It is organized into four parts: (A) Ontology Representation and Reasoning (Description Logics, Frame Logic, RDF(S), OWL, ontology algebra); (B) Ontology Engineering (methodologies, large case studies, OntoClean, ontology learning, knowledge patterns, lexicons); (C) Ontology Infrastructure (management environments, problem-solving methods, multi-agent interaction, merging/mapping, browsing, visualization); and (D) Ontology Applications (knowledge management, eCommerce, semantic portals, hypermedia, enterprise integration, bioinformatics).

The introduction positions ontologies as formal, explicit specifications of shared conceptualizations and traces their rise from knowledge-based systems through the Semantic Web into mainstream information systems.

Key Ideas

Standard definition: ontology = formal, explicit specification of shared conceptualization.
Four-part organization: representation, engineering, infrastructure, applications.
Description Logics and Frame Logic as main representation paradigms.
OWL, RDF(S), and ontology algebra as Semantic Web foundations.
Multi-agent systems rely on ontologies for communication semantics.

Connections

Conceptual Contribution

Claim: Ontologies - formal, explicit specifications of shared conceptualisations - are the unifying infrastructure behind knowledge-based systems, the Semantic Web, and multi-agent communication semantics.
Mechanism: Four-part reference structure covering representation/reasoning (DL, F-Logic, RDF(S), OWL, ontology algebra), engineering (OntoClean, ontology learning, patterns), infrastructure (management, merging, MAS interaction), and applications (KM, eCommerce, bioinformatics).
Concepts introduced/used: Ontologies, Description Logics, OWL, RDF, Frame Logic, Ontology Engineering, Semantic Web, Multi-Agent Systems, Agent Communication Languages
Stance: foundational / survey
Relates to: Supplies the representational substrate assumed by A Common Ontology Of ACLs, Semantic Description For Agent Design Patterns, and the content-layer opacity of KQML Language And Protocol / FIPA-ACL.

Tags

Conceptualization

Gruber’s term: the abstract, simplified view of the world that an ontology makes explicit.

In this vault

Ontology

Gruber: an explicit specification of a conceptualization — the shared vocabulary agents use to talk about a domain.

In this vault

Ontolingua Portable Ontology Specifications

A Translation Approach to Portable Ontology Specifications

Reference: Thomas R. Gruber (1993). Knowledge Acquisition, 5(2):199-220 (KSL Technical Report KSL-92-71). Source file: ontolingua-kaj-1993.pdf. URL

Summary

Gruber’s landmark paper defines an ontology as “an explicit specification of a conceptualization” — a formal vocabulary of classes, relations, functions, and axioms that captures the intended meaning of terms shared among knowledge-based systems. He addresses the portability problem: ontologies need to be reused across applications built in different representation languages (frame-based, description-logic, relational, Prolog), which would otherwise each need bespoke versions.

The solution is Ontolingua, a system that specifies ontologies in a standard declarative form (predicate calculus extended with KIF and frame-ontology idioms) and translates them into the forms required by specific target representation systems. The approach accommodates stylistic differences across representations while preserving declarative content, and handles translation from an expressive source into restricted targets. The paper articulates criteria for good ontology design (clarity, coherence, extendibility, minimal encoding bias, minimal ontological commitment) that still guide knowledge-engineering practice today.

Key Ideas

Ontology = explicit specification of a conceptualization.
Ontological commitments as agreements about shared vocabulary.
Translation approach: one source language → many target representations.
Ontolingua built atop KIF and a frame ontology.
Design criteria: clarity, coherence, extendibility, minimal encoding bias.

Connections

Conceptual Contribution

Claim: Shared knowledge among heterogeneous AI systems requires explicit, portable specifications of conceptualisations — ontologies — that can be defined once in a neutral declarative form and mechanically translated into many target representation systems while preserving declarative content.
Mechanism: Defines “ontology” as explicit specification of a conceptualisation; introduces ontological commitments as vocabulary-sharing agreements at the knowledge level (Newell); implements Ontolingua in KIF (Lisp-like predicate calculus with equality) with a Frame Ontology capturing class/relation/function/axiom idioms; provides translators to LOOM, Epikit, Express, and pure KIF. Proposes design criteria: clarity, coherence, extendibility, minimal encoding bias, minimal ontological commitment.
Concepts introduced/used: Ontology, Conceptualization, Ontological Commitment, KIF, Frame Ontology, Ontolingua, Knowledge-Level Specification, Translation Approach, Ontology Design Criteria
Stance: foundational / engineering
Relates to: Solves the content-language side of the problem that KQML Overview splits into content/message/communication layers; cited by virtually all agent-communication work needing shared vocabulary including FIPA-ACL, A Common Ontology Of ACLs, and Handbook On Ontologies; design criteria still guide modern ontology engineering.

Tags

Architectural Patterns for Dependable Software Systems - SOL

Specification, Analysis and Implementation of Architectural Patterns for Dependable Software Systems

Reference: Yau, S. S., Mukhopadhyay, S., Bharadwaj, R. (2005). Proc. 10th IEEE Intl. Workshop on Object-Oriented Real-Time Dependable Systems (WORDS’05). Source file: WORD2005-2.pdf. URL

Summary

The paper presents the Secure Operations Language (SOL) and the agent-based SINS middleware for specifying, analyzing, and deploying architectural patterns that realize non-functional requirements (security, fault tolerance, real-time) of distributed dependable systems. SOL is a synchronous specification language with a precise formal semantics supporting automated analysis (theorem proving, model checking); SINS runs SOL agents on virtual machines distributed over hosts, with encrypted inter-agent messaging via a Secure Agent Control Protocol.

The authors illustrate SOL by formalizing a stack safety policy (a safestack module that constrains illegal pushes/pops) and the Hot Standby and Majority Vote fault-tolerance patterns as SOL modules with observable fail events. They extend SOL with module imports, an implicit fail variable, and middleware notification of module failures — enabling compositional dependability reasoning across heterogeneous deployments.

Key Ideas

SOL: synchronous language for agent specification with formal semantics.
SINS middleware runs SOL agents across encrypted VMs.
Patterns (HotStandby, MajorityVote) as reusable SOL modules.
Safety policies enforced at the language level.
Compositional analysis of dependability requirements.

Connections

Conceptual Contribution

Claim: Dependability (security, fault tolerance, real-time) in distributed systems is best achieved by specifying architectural patterns as formal modules in a synchronous agent language and deploying them on a middleware that enforces the same semantics at runtime.
Mechanism: SOL is a synchronous language with precise formal semantics amenable to theorem proving and model checking; programs are agents running on SINS virtual machines across hosts, communicating over the Secure Agent Control Protocol. The authors extend SOL with module imports, an implicit fail variable, and middleware fault notifications, then encode stack-safety, Hot Standby and Majority Vote as reusable SOL modules whose composition preserves dependability guarantees.
Concepts introduced/used: Secure Operations Language, SINS Middleware, Synchronous Language, Architectural Pattern, Hot Standby, Majority Vote, Safestack, Secure Agent Control Protocol, Compositional Dependability
Stance: engineering
Relates to: A concrete agent-middleware realisation of the security calculus in Secure Communications Processing for Distributed Languages; its formal-specification stance meets the language-workbench pragmatics of The Spoofax Language Workbench; pattern reuse echoes dependability concerns in Are Multiagent Systems Resilient to Communication Failures and Theory of Self-Reproducing Automata.

Tags

Capability Security

Access-control style where authority is conveyed by unforgeable object references; lexical scope in languages like Scheme suffices as a capability kernel.

In this vault

Security Kernel Lambda Calculus

A Security Kernel Based on the Lambda-Calculus

Reference: Jonathan A. Rees (1996). MIT AI Laboratory Memo No. 1564. Source file: AIM-1564.pdf. URL

Summary

Rees describes Scheme 48, a programming environment whose design is guided by operating-system security principles. The security kernel is W7, a call-by-value lambda-calculus with extensions for abstract data types, object mutation, and hardware access. Each user or subsystem runs in a separate evaluation environment holding the objects representing that user’s privileges; because environments determine availability of object references, protection and sharing are controlled by construction.

The paper describes experience with Scheme 48 as the programming environment for Cornell’s mobile robots (no underlying OS) and as a secure multi-user workstation environment, arguing that lexical scope + first-class environments are a natural substrate for capability-style security among cooperating agents.

Key Ideas

Lambda-calculus as minimal security kernel via capability-style environments.
Scheme 48 (W7): modules, macros, dynamic isolation, portable across platforms.
Trust mediated by controlling which names bind to which objects.
Authentication via capsules (tamper-proof labelled objects).
Applied to robots and multi-user Scheme environments.

Connections

Conceptual Contribution

Claim: Lexical scope and first-class environments in a lambda-calculus variant (W7) are a sufficient security kernel: protection reduces to controlling which names bind to which object references.
Mechanism: Implements Scheme 48 as a capability-style environment where each user/subsystem runs in its own environment; authentication via capsules (tamper-proof labelled objects); deployed on Cornell mobile robots (no OS) and as multi-user workstation environment.
Concepts introduced/used: Capability Security, Lambda Calculus, Lexical Scope, Scheme 48, Capsules, Distributed Security, Multi-Agent Systems
Stance: foundational / engineering
Relates to: Provides a principled, capability-based alternative to the input-validation discipline of Seven Turrets Of Babel and the static DDoS analysis of A Language-Based Approach To Prevent DDoS; relevant to sandboxing malicious tools described in MalTool Malicious Tool Attacks.

Tags

Secure Communications Processing for Distributed Languages

Reference: Abadi, Fournet, Gonthier (1999). Compaq SRC / Microsoft Research / INRIA technical paper. Source file: Secure_communications_processing_for_dis.pdf. URL

Summary

Abadi, Fournet, and Gonthier formalize communications processing — the marshaling, unmarshaling, and cryptographic operations that wrap distributed language primitives like RPC and RMI — within a process calculus. They study how local communication semantics (single machine or protected network) can be extended transparently to hostile distributed networks through a generic cryptographic “wrapper” that operates like a firewall with an encrypting tunnel.

The technical core uses the join-calculus and its cryptographic extension, the sjoin-calculus, to translate high-level join-calculus processes into protected low-level sjoin-calculus processes that exchange encrypted messages. They prove a full-abstraction theorem showing the wrapping preserves observational equivalence — attackers on the public network cannot distinguish wrapped processes that behave the same locally.

Key Ideas

Join-calculus as basis for concurrent/distributed language semantics.
Sjoin-calculus adds symmetric encryption primitives.
Wrapper as filter/firewall doing marshaling + encryption uniformly.
Full-abstraction theorem: wrapping preserves equivalences.
Security reasoned compositionally across distribution boundaries.

Connections

Conceptual Contribution

Claim: The communications-processing layer of a distributed language (marshalling + crypto) can be compiled automatically from a local-semantics specification in such a way that distribution becomes observationally transparent even under an active network attacker.
Mechanism: Abadi, Fournet and Gonthier use the join-calculus for local semantics and the sjoin-calculus (join + symmetric crypto primitives) for the low-level network, defining a wrapper translation that implements channel communication via encrypted tunnels gated by a firewall-like filter. A full-abstraction theorem proves that two source programs are observationally equivalent iff their wrapped versions are, so security reasoning composes with functional reasoning.
Concepts introduced/used: Join Calculus, Sjoin Calculus, Full Abstraction, Communications Processing, Cryptographic Wrapper, Observational Equivalence, Marshalling
Stance: formal-semantic
Relates to: Provides the calculus-level counterpart to language-engineering security efforts like The Halting Problems of Network Stack Insecurity and A Language-Based Approach To Prevent DDoS; its transparent-distribution agenda links to the actor-style transparency claims of Programming Erlang Second Edition and the SOL/SINS encrypted inter-agent channels in Architectural Patterns for Dependable Software Systems - SOL.

Tags

A Language-Based Approach To Prevent DDoS

A Language-Based Approach to Prevent DDoS Attacks in Distributed Financial Agent Systems

Reference: Fazeldehkordi, Owe, Ramezanifarkhani (2018). University of Oslo. Source file: A language-based approach to prevent DDoS attacks in distributed financial agent systems.pdf. URL

Summary

The authors propose adding a language-based layer of defense against DoS/DDoS to distributed financial agent systems built on the actor model with asynchronous method calls and futures (in the style of Creol/ABS). Because such languages make it cheap to launch non-blocking floods, they adapt a static analysis for detecting call-flooding cycles to the many-to-one DDoS setting.

The analysis builds per-method control-flow graphs, identifies cycles, and classifies nodes as strongly- or weakly-reachable to detect unbounded method-call generation at compile time. They distinguish one-to-one, many-to-one, and one-to-many flooding, and illustrate with a publish/subscribe newsletter example where future-based optimization accidentally enables a DoS against subscribers.

Key Ideas

Static detection of call-based flooding in actor-model languages with futures.
Classification: one-to-one, many-to-one, one-to-many flooding.
Strong vs weak reachability in control-flow cycles.
Instantiation flooding (unbounded object creation) as a resource-exhaustion vector.
Application to financial service subscriber systems.

Connections

Conceptual Contribution

Claim: Actor-based agent languages with asynchronous futures make DoS/DDoS cheap to launch inadvertently, and static analysis of call-flow cycles can prevent it at compile time.
Mechanism: Builds per-method control-flow graphs, detects strongly/weakly-reachable cycles that generate unbounded calls; extends from one-to-one to many-to-one and one-to-many flooding; illustrated on a Creol/ABS publish/subscribe newsletter.
Concepts introduced/used: Static Analysis, Actor Model, Futures, DDoS, Control-Flow Graph, Distributed Security, Multi-Agent Systems
Stance: engineering
Relates to: Shares the language-level-security stance of Seven Turrets Of Babel and Security Kernel Lambda Calculus; addresses a threat class complementary to the tool-level attacks of MalTool Malicious Tool Attacks and the broad landscape of AI Agents Under Threat.

Tags

Parser Differential

Attack exploiting the fact that two parsers accept or interpret the same input differently.

In this vault

PKI Layer Cake - Kaminsky Patterson Sassaman

PKI Layer Cake: New Collision Attacks Against the Global X.509 Infrastructure

Reference: Dan Kaminsky, Meredith L. Patterson, and Len Sassaman (2009). Black Hat USA / IOActive technical report. Source file: 1299769.pdf. URL

Summary

Presents several new classes of attacks against the X.509 certificate infrastructure: MD2 preimage exploitation of VeriSign’s still-trusted root, PKCS#10 Subject Name confusion attacks exploiting inconsistent ASN.1 BER parsing between CAs and browsers (multiple CNs, OID leading-zero padding, integer overflow, early null terminators), SQL injection through PKCS#10 subject names, generic SSL client-authentication bypasses, and EV-certificate hijacking via mixed script content.

The paper is largely a case study in how ambiguity at the interface between components — in parsers, in semantics of fields like Common Name, in trust-store EKU handling — turns into exploitable security pathologies. It is of interest to agent-communication research as a cautionary tale about shared-format ambiguity between senders and receivers.

Key Ideas

ASN.1 BER is context-sensitive and handwritten parsers disagree subtly
Subject Name parsing varies across OpenSSL, NSS, CryptoAPI — attacker exploits the gap
MD2 preimage attack enables signature transfer to forged intermediate CA
“Sender-receiver parsing disagreement” as a general attack pattern
Postel’s robustness principle considered harmful for security-critical parsing

Connections

Making Smart Contracts Smarter
Agent Communication Languages
Parser Differential Attack
CBCL - Safe Self-Extending Agent Communication — applies the parser-differential lesson at the message-layer of agent communication; DCFL grammars are class-level unambiguous.

Conceptual Contribution

Claim: The global X.509 PKI is vulnerable not only because of weak hashes (MD2/MD5) but because layered, ambiguously-specified parsers (ASN.1 BER, PKCS#10, Subject Name handling) disagree about what a certificate says — an inter-layer semantic gap exploitable by attackers.
Mechanism: Demonstrate concrete attacks: MD2RSA signature transfer from Verisign’s root, Subject Name Confusion via implementation-dependent CN-selection policies, PKCS#10-tunneled SQL/ASN.1 injection, OID leading-zero/integer-overflow tricks, null-terminator CN spoofing, SSL Client Authentication EKU bypass, and EV hijacking via mixed-trust scripting.
Concepts introduced/used: Parser Differential, Parser Differentials, X.509 PKI, ASN.1 BER Ambiguity, Certificate Authorities, Protocol Layering Attacks, Distributed Security, LangSec, Language-theoretic Security, Postel’s Robustness Principle
Stance: empirical / security-critique
Relates to: Canonical case study for Distributed Security and a prime example of why A Language-Based Approach To Prevent DDoS-style disciplined parsing matters. The ambiguity of ASN.1 BER mirrors the semantic-drift concerns in agent communication languages (A Common Ontology Of ACLs, ACL Rethinking Principles) — when two parties disagree about message meaning, security or coordination fails.

Tags

Seven Turrets Of Babel

The Seven Turrets of Babel: A Taxonomy of LangSec Errors and How to Expunge Them

Reference: Momot, Bratus, Hallberg, Patterson (2016). IEEE Cybersecurity Development (SecDev). Source file: 7turretsaspublished.pdf. URL

Summary

The authors catalogue seven recurring classes of input-handling bugs under the LangSec (language-theoretic security) lens: shotgun parsing, non-minimalist input-handling code, differing interpretations of the input language, incomplete protocol specification, overloaded fields in input format, permissive processing of invalid input, and inability to express input languages in the Chomsky hierarchy. Each class is grounded in concrete CVEs (Heartbleed, Android Master Key, Rosetta Flash, OpenSSL CVE-2016-0752).

LangSec’s remedy is to treat input acceptance as a formal language-recognition problem: specify a grammar no more complex than deterministic context-free, build a recognizer that fully validates before any processing, and cleanly separate parsing from application logic. The paper proposes new CWE entries naming each weakness so auditors can precisely describe vulnerable input-handling code.

Key Ideas

LangSec: input should be a well-defined language with a fully-validating recognizer.
Seven anti-patterns: shotgun parsing, non-minimalist code, interpretation drift, incomplete spec, field overloading, permissive invalid input, undecidable grammars.
Chomsky hierarchy as a safety ceiling for input languages.
Hand-rolled parsers vs parser-combinator / generator tooling (e.g., Hammer).
Proposed new CWEs to label LangSec anti-patterns.

Connections

Conceptual Contribution

Claim: Most serious input-handling vulnerabilities reduce to seven recurring anti-patterns, all addressable by treating input acceptance as a formal language-recognition problem bounded by the Chomsky hierarchy.
Mechanism: Catalogues each anti-pattern (shotgun parsing, non-minimalist code, interpretation drift, incomplete spec, field overloading, permissive invalid input, undecidable grammars) against real CVEs (Heartbleed, Android Master Key, Rosetta Flash); prescribes grammar-first validating recognizers and proposes new CWE entries.
Concepts introduced/used: LangSec, Shotgun Parsing, Chomsky Hierarchy, Parser Combinators, Distributed Security, Common Weakness Enumeration
Stance: engineering / critique
Relates to: Shares a language-theoretic security stance with A Language-Based Approach To Prevent DDoS and Security Kernel Lambda Calculus; its grammar-discipline arguments apply directly to the schema/protocol surfaces catalogued in Survey Of Agent Interoperability Protocols and exploited in MalTool Malicious Tool Attacks.

Tags

LangSec

Language-theoretic Security

Research programme treating input-handling bugs as recognition-theoretic failures: minimise input-language power and build validating recognisers.

In this vault

The Halting Problems of Network Stack Insecurity
Seven Turrets Of Babel
PKI Layer Cake - Kaminsky Patterson Sassaman
Parser Differential
Distributed Security
Security Applications Of Formal Language Theory
Exploit Programming - From Buffer Overflows To Weird Machines
CBCL - Safe Self-Extending Agent Communication — first ACL designed from LangSec principles
Deterministic Context-Free Language
Parser Differential Attack

Agents Secure Interaction in Data Driven Languages

Reference: Mahdi Zargayouna, Flavien Balbo, Serge Haddad. INRETS / LAMSADE / LSV-CNRS. Source file: ladspaper9.pdf. URL

Summary

The authors focus on a distinct class of Multi-Agent Systems where agents coordinate indirectly through a shared, data-driven space (like Linda tuple spaces or Klaim) rather than via point-to-point ACL messaging. They argue existing data-driven coordination languages conflate security with the data layer, leaving no principled way to separate agent-level access-control policies from the shared space. They propose LACIOS (Language for Agent Contextual Interaction in Open Systems), which introduces properties (predicate-based descriptions) and symbolic matching as a richer alternative to tuple templates.

Security in LACIOS is handled as an orthogonal layer of access-control rules expressed in the same language as agent behavior: global rules restrict who may see what, and local rules let each agent hide or expose parts of its own state. The paper gives syntax and informal semantics for spawn/add/update/look primitives and discusses a prototype implementation in Java-LACIOS.

Key Ideas

Tuple-space / data-driven coordination separated from message-passing MAS.
Properties + symbolic descriptions replace rigid tuples.
Security as an orthogonal layer of global/local access rules.
Unified language for behavior and security policies.
Enables fine-grained contextual perception in open MAS.

Connections

Conceptual Contribution

Claim: Data-driven coordination languages (Linda, Klaim, SecSpaces, SecOS) lack a principled separation between application logic and security; a richer, property-based description model with orthogonal access-control rules fixes this without abandoning the shared-space paradigm.
Mechanism: Introduces LACIOS with four primitives (spawn, add, update, look), replaces rigid tuples with descriptions (property→value maps) and symbolic descriptions parameterised by variables; specifies global access rules controlling perception/retrieval and local rules enabling contextual self-hiding by agents; defines process syntax and sketches a Java-LACIOS implementation.
Concepts introduced/used: Data-Driven Coordination, Tuple Spaces, Properties, Symbolic Descriptions, Access Control Rules, Coordination-Security Separation, Open Multi-Agent Systems
Stance: engineering / formal-semantic
Relates to: Extends the Linda/Klaim lineage with a security concern that parallels DAgents Security Book Chapter and Agent Tcl Flexible Secure Mobile Agents but at the coordination-language level rather than the mobile-code level; offers a stigmergic alternative to the message-centric view of Multiagent Systems Sycara.

Tags

Agent Tcl Flexible Secure Mobile Agents

Agent Tcl: A Flexible and Secure Mobile-Agent System

Reference: Robert S. Gray (1996). Proceedings of the 1996 USENIX Tcl/Tk Workshop, pp. 9-23. Source file: gray-security.pdf. URL

Summary

Gray introduces Agent Tcl, a mobile-agent system built on the Tcl scripting language plus Safe Tcl that supports migration with a single agent_jump instruction, transparent inter-agent communication, and pluggable transport mechanisms. The paper argues that Tcl’s simplicity and ease of embedding make it more accessible than Telescript’s object-oriented language while the Safe Tcl extension provides the sandboxing needed for secure execution — a better balance than the ARA, Tacoma, or SodaBot alternatives.

The architecture has four layers (transport, server, interpreter, agents) and supports PGP-signed agents, resource-manager-based authorization, direct-connection and message-passing communication, and a flat namespace of named agents. Gray details how the Tcl core was modified to capture complete interpreter state (stack, procedure frames, variables) for transparent migration at arbitrary points, and outlines a plan to add Java and Scheme as additional agent languages.

Key Ideas

Single-instruction migration (agent_jump) that transparently captures/restores state.
Safe Tcl for sandboxed execution with policy decoupled from mechanism.
Layered architecture supporting multiple languages and transports.
Security approach: PGP-signed code + resource managers + Safe Tcl.
Explicit interpreter stack rewrite to enable mid-execution migration.

Connections

Conceptual Contribution

Claim: A mobile-agent system can be both simple and secure by building on an interpreted scripting language (Tcl) augmented with Safe Tcl sandboxing, exposing migration as a single instruction that transparently captures/restores complete interpreter state.
Mechanism: Modifies the Tcl core to use an explicit command stack (replacing recursive Tcl_Eval) so full execution state is capturable; primitives agent_begin/submit/jump/send/receive/meet/accept provide uniform mobility and messaging; security via PGP-signed agents + per-identity resource managers + Safe Tcl trusted/untrusted dual interpreters with link substitution.
Concepts introduced/used: Mobile Agent, agent_jump, State Capture, Safe Tcl, Sandboxing, Explicit Command Stack, Flat Namespace, Resource Managers
Stance: engineering
Relates to: Precursor to DAgents Security Book Chapter which formalises the security model; contemporary alternative to Telescript/ARA/Tacoma (discussed in the D’Agents chapter); shares interpreter-level security philosophy with Agents Secure Interaction in Data Driven Languages.

Tags

DAgents Security Book Chapter

D’Agents: Security in a Multiple-Language, Mobile-Agent System

Reference: Robert S. Gray, David Kotz, George Cybenko, Daniela Rus (1998). Mobile Agents and Security (G. Vigna, ed.), Springer LNCS. Source file: gray-security-book.pdf. URL

Summary

This chapter describes the security architecture of D’Agents (formerly Agent Tcl), a mobile-agent system whose agents can be written in Tcl, Java, or Scheme. The authors frame mobile-agent security as four interrelated problems: protecting the host machine from malicious agents, protecting agents from each other, protecting an agent from a malicious machine, and limiting aggregate resource consumption across groups of machines.

For machine and inter-agent protection, D’Agents relies on PGP-based cryptographic authentication of owners, identity-based resource managers that enforce access-control policies, and secure execution environments (Safe Tcl, Java security managers, Scheme 48 modules) separated cleanly from policy. For group-of-machine protection they plan an electronic-cash market approach; for agent-from-host attacks they survey partial techniques (detection via audit trails, encrypted computation, trusted reference machines) since full prevention requires hardware support they do not assume.

Key Ideas

Four interrelated mobile-agent security problems.
Separation of enforcement mechanism from policy.
Multi-language support with a uniform C/C++ server library.
Cryptographic authentication + per-identity resource managers.
Open problem: protecting agents from malicious hosts without trusted hardware.

Connections

Conceptual Contribution

Claim: Mobile-agent security comprises four distinct but interrelated problems (protecting machine, protecting other agents, protecting agent from host, protecting group of machines); solving them requires layered mechanisms that cleanly separate enforcement from policy and span multiple execution languages.
Mechanism: Architectural description of D’Agents’ four-level stack (transport, server, interpreter, agents); PGP-based owner authentication; language-specific enforcement modules (Safe Tcl, Java security manager, Scheme 48) routed through a language-independent resource manager; planned e-cash market approach for aggregate-resource protection; survey of partial techniques (audit trails, encrypted computation) for the agent-from-host problem.
Concepts introduced/used: Mobile Agent, Four Security Problems, Mechanism vs Policy, Safe Tcl, Resource Manager Agent, PGP Authentication, Audit Trail, Encrypted Computation
Stance: engineering / survey
Relates to: Extends the earlier Agent Tcl Flexible Secure Mobile Agents with a mature security story; shares threat concerns with AI Agents Under Threat and Distributed Security; policy/mechanism separation echoes the sandboxing principles of Extensible Distributed Coordination and Agents Secure Interaction in Data Driven Languages.

Tags

Review on Computational Trust and Reputation Models

Reference: Sabater, Sierra (2005). Artificial Intelligence Review. Source file: Review_on_Computational_Trust_and_Reputation_Model.pdf. URL

Summary

A panoramic review of computational trust and reputation models developed for multi-agent systems and electronic commerce. Sabater and Sierra classify models along several dimensions: conceptual basis (cognitive vs. game-theoretical), information sources (direct experience, witness information, sociological signals, prejudice), visibility (global vs. subjective), granularity (single- vs. multi-context), assumptions about cheating behavior, type of exchanged information, and provision of reliability measures.

The survey then applies this framework to representative models (Marsh’s early trust model, Sporas, Histos, ReGreT, AFRAS, FIRE, eBay-style mechanisms, Yu & Singh’s evidential model, etc.), identifying under-explored aspects: sociological information, multi-context reasoning, and principled handling of liars. It argues that as MAS applications grow more complex, trust models must become richer to accommodate social structures and contextual reasoning.

Key Ideas

Trust as cognitive belief vs. game-theoretic subjective probability.
Direct experience, witness (word-of-mouth), sociological signals, prejudice.
Global (online reputation) vs. subjective trust per partner.
Three levels of cheating-resistance: ignored, biasing-only, liars.
Need for multi-context, sociologically-aware trust.

Connections

Conceptual Contribution

Claim: Computational trust/reputation must be classified along several independent dimensions (conceptual basis, information sources, visibility, granularity, cheating assumptions) if models are to be compared and composed rather than merely enumerated.
Mechanism: The authors propose a multi-axis taxonomy and apply it to a dozen canonical models (Marsh, Sporas, Histos, ReGreT, AFRAS, FIRE, eBay-style aggregation, Yu & Singh), using each axis to surface gaps: sociological signals, multi-context trust, and principled liar handling are under-served despite being pivotal for realistic MAS.
Concepts introduced/used: Trust, Reputation, Direct Experience, Witness Reputation, Sociological Reputation, Prejudice, ReGreT, FIRE, Cognitive Trust, Game-Theoretic Trust
Stance: survey
Relates to: Supplies the conceptual vocabulary picked up by self-organisation work such as A Composite Self-organisation Mechanism in an Agent Network (DSmT trust fusion) and contextualises verifiability debates in Agent Communication Languages - Rethinking the Principles; links to Gossip Protocols through witness-information propagation.

Tags

Edge Intelligence Survey

Edge Intelligence: Paving the Last Mile of Artificial Intelligence With Edge Computing

Reference: Zhi Zhou, Xu Chen, En Li, Liekang Zeng, Ke Luo, Junshan Zhang (2019). Proceedings of the IEEE, Vol. 107, No. 8, pp. 1738-1762. Source file: Edge_Intelligence_Paving_the_Last_Mile_of_Artificial_Intelligence_With_Edge_Computing.pdf. URL

Summary

A comprehensive survey of Edge Intelligence (EI), the fusion of AI with edge computing that pushes deep-learning training and inference out of centralized cloud datacenters toward the network edge, where the data is generated. The authors motivate EI through the explosion of IoT data, latency/bandwidth limits of cloud AI, and growing privacy concerns. They propose a six-level rating scheme for EI — from cloud-only (Level 0) through various hybrid cloud-edge splits to fully on-device training and inference (Level 6) — and argue the right level is application dependent.

The paper surveys architectures (centralized, decentralized, hybrid distributed training), key performance indicators (training loss, convergence, privacy, communication cost, latency, energy), enabling techniques, and frameworks for DNN training and inference at the edge. It frames EI as a “last mile” extension that unlocks IoT/AR/VR/autonomous applications by co-locating intelligence with data.

Key Ideas

Six-level rating of EI based on amount and path length of data offloading.
Cloud-edge-device synergy reduces latency and energy vs. pure cloud or pure on-device.
Distributed DNN training modes: centralized, decentralized, hybrid.
Privacy-preserving rationale: raw data stays at edge.
EI is a cross-cutting discipline bridging AI, systems, and networking.

Connections

Conceptual Contribution

Claim: AI training and inference should be distributed across a cloud-edge-device hierarchy rather than centralised in the cloud; the optimal split is application-dependent and can be described by a six-level rating.
Mechanism: Systematic survey structured around motivations (latency, privacy, bandwidth, data locality), a six-level EI taxonomy, three distributed-training architectures (centralised, decentralised, hybrid), six KPIs, and enabling techniques (federated learning, gradient compression, DNN splitting, knowledge transfer, gossip training).
Concepts introduced/used: Edge Intelligence, Cloud-Edge-Device Hierarchy, Federated Learning, Gossip Training, DNN Splitting, Gradient Compression, Knowledge Transfer Learning, Six-Level EI Rating
Stance: survey
Relates to: Ties into Edge Intelligence hub and shares gossip-training mechanisms with Gossip-based Aggregation in Large Dynamic Networks and Gossip-Based Computation of Aggregate Information; motivates on-device LLM agents relevant to LLM Agents and A Scalable Communication Protocol for Networks of LLMs.

Tags

Peer Sampling Service

Substrate gossip protocol supplying random peer samples to higher-level aggregation or overlay protocols.

In this vault

Gossip-based Aggregation in Large Dynamic Networks

Reference: Márk Jelasity, Alberto Montresor, Ozalp Babaoglu (2005). ACM Transactions on Computer Systems, Vol. 23, No. 3, pp. 219-252. Source file: gossip.pdf. URL

Summary

The paper presents a proactive, gossip-based protocol for continuously computing aggregate functions (averages, sums, counts, variances, network size, extremal values) over huge dynamic networks such as P2P and grid systems. Each node periodically picks a random neighbor and performs a push-pull exchange; pairwise averaging drives the variance of estimates to zero at a geometric rate while preserving the global mean (“mass conservation”). All nodes thus converge to the correct aggregate and adaptively track changes over time.

Beyond core averaging, the authors show how to compute more complex aggregates (variance, network size via a single seed) and evaluate robustness under node churn and message loss, including a PlanetLab deployment. The protocol is attractive because it is simple, scalable, lightweight, and requires no centralized infrastructure — only a peer-sampling service.

Key Ideas

Push-pull averaging: w_p, w_q ← (w_p + w_q)/2 drives variance to zero exponentially.
Mass conservation preserves global sum so global average remains unchanged.
Reactive vs. proactive aggregation; this work targets proactive, always-on aggregates.
Robustness to dynamism, churn, and message loss.
Underlying assumption: a peer-sampling service supplies uniform random neighbors.

Connections

Gossip Protocols
Self-Adaptive Systems
Multi-Agent Systems
CALM Theorem — push-pull averaging is monotonic, hence coordination-free
Keeping CALM - When Distributed Consistency is Easy

Conceptual Contribution

Claim: A simple push-pull averaging gossip protocol — paired with a peer-sampling service — provides proactive, continuously-updated aggregates (average, sum, count, variance, network size, extrema) at large scale with geometric-rate convergence and robustness to churn and message loss.
Mechanism: Each node periodically picks a random neighbour via getNeighbor(), exchanges local estimate, and replaces both with their average; variance analysis as iterative reduction gives convergence factor independent of network size; adaptive restart mechanism handles dynamism; PlanetLab deployment validates the theory.
Concepts introduced/used: Push-Pull Gossip, Proactive Aggregation, Peer Sampling Service, Variance Reduction, Mass Conservation, Convergence Factor, Adaptive Protocols
Stance: engineering / empirical with formal analysis
Relates to: Practical complement to the theoretical Gossip-Based Computation of Aggregate Information (Push-Sum); cited as a canonical aggregation example in Gossiping in Distributed Systems; the peer-sampling substrate it assumes is the same used by Myconet Fungi Inspired Superpeer Overlay and other bio-inspired overlays.

Tags

Gossiping in Distributed Systems

Reference: Anne-Marie Kermarrec, Maarten van Steen (2007). ACM SIGOPS Operating Systems Review, Vol. 41, No. 5. Source file: Gossiping_in_distributed_systems.pdf. URL

Summary

This tutorial surveys the “gossip revival” in distributed systems, providing a unifying framework for reasoning about the broad space of gossip-based protocols now used far beyond their original role as epidemic reliable multicast. The authors organize gossip protocols by three crucial parameters: peer selection (who to talk to), data exchanged (what to send), and data processing (what to do with what arrives); varying these three gives rise to dissemination, peer sampling, aggregation, overlay/topology construction, resource monitoring, and slicing protocols.

They illustrate each axis with canonical examples — Lpbcast and Newscast for membership, Push-Sum and T-Man for aggregation and overlay construction, Astrolabe for monitoring — and highlight why gossip’s randomized, local-only interactions produce emergent convergent global behavior with exceptional robustness to churn and failures. The paper emphasizes gossip’s use in convergent, not just divergent (epidemic) behaviors.

Key Ideas

Three-parameter gossip framework: peer selection, data exchanged, data processing.
Applications: dissemination, peer sampling, aggregation, topology construction, monitoring, slicing.
Convergent behavior from local random pairwise exchanges.
Peer sampling service is the common substrate most gossip protocols assume.
Robustness through probabilistic redundancy and randomization.

Connections

Conceptual Contribution

Claim: The sprawling family of gossip-based algorithms can be unified as a three-parameter design space — peer selection, data exchanged, data processing — and the same substrate supports not just epidemic dissemination but convergent behaviours including aggregation, overlay construction, and monitoring.
Mechanism: Presents a generic active/passive-thread gossip skeleton; classifies protocols along the three parameters with canonical instances (Lpbcast, Newscast, Cyclon, T-Man, Push-Sum, Astrolabe, GEMS); highlights how peer-sampling acts as the common foundational service enabling higher-level applications.
Concepts introduced/used: Gossip Framework, Peer Selection, Data Exchange, Data Processing, Peer Sampling Service, Convergent Gossip, Epidemic Dissemination, Overlay Construction
Stance: survey
Relates to: Provides the taxonomy that situates Gossip-based Aggregation in Large Dynamic Networks (aggregation), Gossip-Based Computation of Aggregate Information (Push-Sum), Myconet Fungi Inspired Superpeer Overlay (topology construction), and the gossip-training mode surveyed in Edge Intelligence Survey. Anchor for Gossip Protocols hub.

Tags

Computational Boundary of a Self

The Computational Boundary of a “Self”: Developmental Bioelectricity Drives Multicellularity and Scale-Free Cognition

Reference: Michael Levin (2019). Frontiers in Psychology, Vol. 10, Article 2688. Source file: fpsyg-10-02688.pdf. URL

Summary

Levin proposes a biologically grounded, scale-free definition of cognitive “Individuals” based on their capacity to pursue goals at a characteristic level of scale and organization. A Self is demarcated by a computational surface — a spatio-temporal “cognitive light cone” defining what events it can measure, model, and influence. Higher goal-directed agency, he argues, evolves smoothly from the primal homeostatic TOTE loop that living things use to reduce stress between current and life-optimal conditions.

The central mechanism is developmental bioelectricity — the ability of cells to form bioelectrical networks (via gap junctions, ion channels) that process information and guide embryogenesis, regeneration, and possibly higher cognition. Levin sketches gradual evolutionary steps from physiological homeostasis in single cells to memory, prediction, and complex cognition, proposing that multi-scale Individuals emerge from the “scale-up of the basic drive of infotaxis.” Implications span cancer biology, AI, bioengineering, and exobiology.

Key Ideas

Individuals defined by goal-pursuit capability and cognitive light cone, not anatomy.
Developmental bioelectricity as substrate for scale-free cognition.
Continuum from stimulus-response to predictive agency (TOTE loops).
Cancer as a shift in the boundary of the Self to a single-cell scope.
Testable predictions for biomedicine, evolutionary biology, and AI.

Connections

Conceptual Contribution

Claim: A cognitive “Individual” is demarcated not by anatomy but by a computational surface — the spatio-temporal cognitive light cone over which it can measure, model, and act — and such Selves scale up smoothly via developmental bioelectricity from single cells to multicellular organisms.
Mechanism: Synthesises cognitive science, evolutionary biology, and developmental physiology; defines Individuality by goal-pursuit capacity at a level of organisation; proposes a continuum of cognitive powers (TOTE loops parametrised by memory/prediction depth); argues gap-junctional bioelectric networks are the substrate that binds sub-agents into larger Selves, with cancer as a concrete boundary-shrinkage phenomenon.
Concepts introduced/used: Cognitive Light Cone, Scale-Free Cognition, Developmental Bioelectricity, Individuality, TOTE Loop, Infotaxis, Computational Surface, Goal-Directedness
Stance: foundational / theoretical-biology
Relates to: Provides a biological grounding for the multi-scale agency assumptions behind Multi-Agent Systems and Self-Adaptation Self-Expression Self-Awareness ASCENS; the TOTE/homeostasis framing connects to control-loop views in A Composite Self-organisation Mechanism in an Agent Network; informs what “agent” could mean for Myconet Fungi Inspired Superpeer Overlay and bio-inspired coordination.

Tags

A Composite Self-organisation Mechanism in an Agent Network

Reference: Ye, D., Zhang, M., Bai, Q. (2011). WISE 2011, LNCS 6997, Springer. Source file: WISE2011-2.pdf. URL

Summary

The authors propose a decentralized self-organization mechanism that lets agents in a collaborative task-allocation network dynamically adapt their weighted relations (peer-to-peer and subordinate-superior) to improve overall profit. The mechanism combines two components: a Dezert-Smarandache-theory-based trust model that fuses direct experience and neighbor opinions to select candidate partners, and a multi-agent Q-learning algorithm that learns which relation-adaptation actions (enhance/weaken the relation type) pay off.

Unlike prior approaches that assume crisp binary relations, this model uses weighted relation strengths in [0,1], allowing gradual rather than sudden social change. Agents aim to minimize communication, computation, and management cost while maximizing subtask benefit. Reward matrices defined over action pairs couple the two learners so that joint optimal adaptations emerge.

Key Ideas

Weighted relations replace crisp relations for realism.
DSmT trust model fuses self and witness evidence.
Multi-agent Q-learning for joint relation adaptation.
Profit = benefit − (communication + computation + management costs).
Decentralized, resilient to single-node failures.

Connections

Conceptual Contribution

Claim: Decentralised task-allocation networks self-organise more effectively when agents adapt weighted (rather than binary) relations via a composite mechanism that fuses a DSmT-based trust model with multi-agent Q-learning.
Mechanism: Each pair of agents maintains peer-to-peer and subordinate-superior weights in [0,1]. Candidate partners for a subtask are selected using Dezert-Smarandache-theory fusion of direct experience and neighbour opinions (handling conflicting/paradoxical evidence). A multi-agent Q-learning algorithm with coupled reward matrices learns enhance/weaken adaptation actions on those weights, optimising profit = subtask benefit − (communication + computation + management) cost.
Concepts introduced/used: Self-Organisation, Weighted Relation, Dezert-Smarandache Theory, Multi-Agent Q-Learning, Trust Fusion, Relation Adaptation, Task Allocation Network
Stance: engineering
Relates to: Operationalises ideas surveyed in Review on Computational Trust and Reputation Models (witness + direct evidence fusion); complements gossip-style information exchange in Gossip-based Aggregation in Large Dynamic Networks; the decentralised resilience theme echoes Theory of Self-Reproducing Automata.

Tags

Self-Adaptation Self-Expression Self-Awareness ASCENS

On Self-adaptation, Self-expression, and Self-awareness in Autonomic Service Component Ensembles

Reference: Franco Zambonelli, Nicola Bicocchi, Giacomo Cabri, Letizia Leonardi, Mariachiara Puviani (2011). SASO Workshops 2011. Source file: On_Self-Adaptation_Self-Expression_and_Self-Awaren.pdf. URL

Summary

This ASCENS-project position paper frames three research issues for building autonomic service-component ensembles: (i) schemes that enable self-adaptive behavior in individual components and ensembles, (ii) mechanisms for self-expression — dynamic changes to the structure of interaction protocols and coordination topology — and (iii) self-awareness — components knowing enough about context and peers to choose appropriate adaptation schemes.

The authors organize adaptation along two dimensions: where (individual vs. collective) and what (behavioral self-adaptation vs. structural self-expression). A swarm/leader/corridor robotics case study illustrates that different situations call for qualitatively different adaptation regimes, and that moving between regimes requires self-awareness. The paper surveys the state of the art and argues for unified frameworks that span individual and ensemble-level adaptation while keeping human cognitive load manageable.

Key Ideas

Two-dimensional taxonomy of adaptation: where (individual/collective) × what (behavior/structure).
Self-expression = dynamically changing interaction protocols and topology.
Self-awareness as meta-capability enabling choice among adaptation schemes.
Robotics case study: leader, corridor, swarm regimes.
ASCENS roadmap for autonomic component ensembles.

Connections

Conceptual Contribution

Claim: Building autonomic service-component ensembles requires distinguishing three complementary self-* capabilities — self-adaptation (behaviour), self-expression (structure/protocols/topology), and self-awareness (meta-choice among schemes) — along two orthogonal dimensions: individual vs. collective and behavioural vs. structural.
Mechanism: Position paper layout: 2×2 adaptation taxonomy; distinction between self-adaptation and self-expression; robotics case study with three regimes (Leader, Corridor/Peers, Swarm) showing each calls for different adaptation schemes; articulation of four self-awareness sub-issues (understand amount/level of context, capabilities, trade-offs, scheme properties).
Concepts introduced/used: Self-Adaptation, Self-Expression, Self-Awareness, Autonomic Service Component Ensembles, ASCENS, Adaptation Dimensions, Interaction Protocol Change, Meta-Adaptation
Stance: foundational / survey / position
Relates to: Provides the conceptual scaffolding picked up by bio-inspired self-organisation work such as Myconet Fungi Inspired Superpeer Overlay and A Composite Self-organisation Mechanism in an Agent Network; self-awareness thread resonates with agency/Selfhood arguments in Computational Boundary of a Self; protocol-change motif connects to A Scalable Communication Protocol for Networks of LLMs.

Tags

Theory of Self-Reproducing Automata

Theory of Self-Reproducing Automata (Fourth Lecture: The Role of High and of Extremely High Complication)

Reference: von Neumann, J. (edited and completed by Arthur W. Burks) (1966). University of Illinois Press. Source file: VonNeumann.pdf. URL

Summary

This excerpt is the Fourth Lecture of von Neumann’s posthumously edited Theory of Self-Reproducing Automata. Von Neumann compares natural automata (nervous systems) with artificial computing machines across size, speed, energy dissipation per elementary act of information, and error characteristics. He observes that although vacuum tubes are vastly larger and less energy-efficient than neurons, both are far above the thermodynamic minimum — suggesting physics does not fully explain the size gap; reliability likely does.

The core argument concerns complication: below a threshold, a system cannot perform certain tasks at all; above it, qualitatively new behaviors (including self-reproduction and evolution) become possible. Natural automata tolerate errors locally rather than halting on any single fault, an architectural stance he contrasts with the “single-error” fragility of contemporary computers. The discussion foreshadows modern views on redundancy, fault tolerance, and emergent capabilities with scale.

Key Ideas

Complication threshold enables qualitatively new behavior.
Natural automata survive local errors; artificial automata halt.
Analog-digital mixture characterizes biological computation.
Size and reliability trade-offs shape architecture.
Precursor to self-reproducing and evolvable systems theory.

Connections

Self-Adaptive Systems
Multi-Agent Systems
Edge Intelligence
Large Population Models
ClawWorm Self-Propagating Attacks Across LLM Agent Ecosystems — modern self-replicating agent, direct lineal descendant
Myconet Fungi Inspired Superpeer Overlay — biological self-organisation
Computational Boundary of a Self — selfhood extended to scale-free cognition
Programming Erlang Second Edition — engineered local-error-tolerance

Conceptual Contribution

Claim: There exists a threshold of “complication” below which automata can only degrade and above which qualitatively new capacities (self-reproduction, evolvable organisation) become possible; biological automata survive precisely because their architecture tolerates local error rather than halting on any single fault.
Mechanism: Von Neumann juxtaposes nervous systems and vacuum-tube computers along size, energy-per-information-act, speed, and error characteristics, noting both far exceed thermodynamic minima so the gap must be architectural. He then argues that digital-analog hybrids with distributed redundancy exhibit error-tolerant behaviour that Turing-style halting-on-first-error machines cannot match, and frames this as a prerequisite for crossing the complication threshold that enables open-ended evolution.
Concepts introduced/used: Complication Threshold, Self-Reproducing Automata, Fault Tolerance, Redundancy, Digital-Analog Hybrid, Error Halting, Natural vs Artificial Automata
Stance: foundational
Relates to: A philosophical wellspring for the “let it crash” supervision of Programming Erlang Second Edition, the fault-tolerance patterns of Architectural Patterns for Dependable Software Systems - SOL, the robustness concerns of Are Multiagent Systems Resilient to Communication Failures, and the emergent-complexity framing behind Computational Boundary of a Self.

Tags

How Do Committees Invent

How Do Committees Invent?

Reference: Melvin E. Conway (1968). Datamation, April 1968, pp. 28-31. Source file: Conway, Melvin E._ How Do Committees Invent_. In_ Datamation (1968).pdf. URL

Summary

Conway’s classic essay articulates what is now known as Conway’s Law: “organizations which design systems are constrained to produce designs which are copies of the communication structures of these organizations.” He argues that the structure (graph) of any designed system is homomorphic to the structure of the design organization that produced it, because each interface in the system corresponds to a coordination path between subgroups.

Drawing on examples from compiler development, military weapons systems, and public administration, Conway traces how organization charts end up printed onto product architectures. He closes with a warning against premature commitment to an initial design organization, since such commitment freezes choices and leaves systems unable to be decomposed sensibly later — “systems tend to disintegrate” as the organization evolves.

Key Ideas

System structure mirrors the communication structure of its designers (Conway’s Law).
Design organization choices shape the set of alternatives considered.
Homomorphism argument: interfaces between subsystems = coordination between subgroups.
Organizations must stay flexible to avoid freezing a suboptimal design.
Applicability beyond software: any large coordinated design effort.

Connections

Multi-Agent Systems
Agent Communication Languages
Self-Adaptive Systems
Standard Operating Procedures (SOPs)
Protocol Documents
Interaction Protocols
Levels Of Social Orchestration — extends Conway to agent-population architecture
A Scalable Communication Protocol for Networks of LLMs — Agora protocol documents as “language = organisation”
Vibe Coding — the organisation-mirror problem when the “organisation” includes AI agents

Conceptual Contribution

Claim: The structure of a designed system is homomorphic to the communication structure of the organization that designs it (Conway’s Law); therefore design-team topology pre-determines the space of realisable architectures.
Mechanism: An informal homomorphism argument — every subsystem maps to a design subgroup and every interface maps to a negotiation path — illustrated through compiler, weapons system, and public-administration case studies; followed by a disintegration argument (overpopulation + rigid management practice fragment the communication graph, which fragments the product).
Concepts introduced/used: Conway’s Law, System Homomorphism, Communication Structure, Design Organization, Coordination, Interface
Stance: foundational / critique
Relates to: Provides the organisational backdrop for every multi-agent architecture in the vault; pairs naturally with Multiagent Systems Sycara (which treats the agent organisation as a deliberate design variable) and with A Scalable Communication Protocol for Networks of LLMs (whose protocol shape will, by Conway’s Law, shape the societies of LLMs built atop it).

Tags

Large Population Models

Reframing from large single models (LLM) to large populations of interacting agents where leverage comes from protocol design.

In this vault

MAST Taxonomy

Multi-Agent System Taxonomy (MAST)

Empirically grounded 14-failure-mode taxonomy for LLM multi-agent systems, spanning specification, coordination, and verification.

In this vault

Why Do Multi-Agent LLM Systems Fail

Are Multiagent Systems Resilient to Communication Failures

Are Multiagent Systems Resilient to Communication Failures?

Reference: Philip N. Brown, Holly P. Borowski, and Jason R. Marden (2017). arXiv:1710.08500 (American Control Conference 2018). Source file: 1710.08500v1.pdf. URL

Summary

Studies whether game-theoretic multiagent systems that tolerate “offline” design-time information loss also tolerate “online” runtime communication failures. Using potential games as the canonical setting, the authors show a surprising negative result: even a single communication failure about a weakly-coupled (“inconsequential”) agent’s action can drive best-response and log-linear-learning dynamics to arbitrarily poor equilibria, regardless of which proxy-payoff evaluator the ignorant agent uses.

The paper also identifies positive results — identical-interest games with the max evaluator remain well-behaved under a single failure — and proposes a “coarse potential alignment” certificate for when proxy payoffs are safe. It further shows a paradox: in identical-interest games, performance can improve when more agents are denied information about an inconsequential player.

Key Ideas

Proxy-payoff evaluators (sum/max/min/mean) and their admissibility
Single communication failure can destabilise potential-game equilibria
Identical-interest + max evaluator is the only generally safe combination
“Inconsequentiality” as an epsilon-weak-coupling definition
Larger action spaces (more profiles) make games more susceptible

Connections

Conceptual Contribution

Claim: Even when a single “weakly-coupled” agent loses information about another’s action, standard game-theoretic multi-agent control (potential games, identical-interest games, log-linear learning) can collapse to arbitrarily bad equilibria — resilience to communication failures is fundamentally limited by the structure of the problem, not just the learning rule.
Mechanism: Formalise the notion of ε-inconsequentiality (a player whose action change barely affects another’s payoff) and proxy payoff evaluators (max/mean/min/sum over unobserved actions); prove negative theorems showing acceptable evaluators can induce pathological Nash equilibria, then positive structural results (ε-inconsequential + max-evaluator + identical-interest ⇒ resilience) and “informational paradox” results where removing communication can improve outcomes.
Concepts introduced/used: Potential Games, Log-linear Learning, Proxy Payoff Evaluators, Inconsequentiality, Communication Failures, Distributed Optimization, Nash Equilibrium Pathologies, Nash Equilibrium, Best-Response Dynamics, Price of Anarchy, Identical-Interest Games
Stance: formal / game-theoretic
Relates to: Provides the theoretical foundation for robustness concerns raised empirically in Why Do Multi-Agent LLM Systems Fail and A Composite Self-organisation Mechanism in an Agent Network. The inconsequentiality notion parallels weak-coupling arguments in Gossip Protocols and Gossip-based Aggregation in Large Dynamic Networks.

Tags

Negotiation

Bargaining protocols (Rubinstein, Contract Net, auctions) by which agents reach agreement on tasks or vocabulary.

In this vault

Joint Intentions

Cohen & Levesque’s theory of teamwork: joint persistent goals with mutual belief commitments.

In this vault

Contract Net Protocol

Classic MAS coordination protocol: a manager announces a task, contractors bid, the manager awards the contract.

In this vault

Multiagent Systems Sycara

Multiagent Systems

Reference: Katia P. Sycara (1998). AI Magazine, Summer 1998, Vol. 19, No. 2, pp. 79-92. Source file: Multiagent_Systems.pdf. URL

Summary

Sycara’s survey introduces multi-agent systems (MAS) as a paradigm for tackling problems too large, complex, or distributed for a single agent, presenting the key characteristics that distinguish MAS: each agent has incomplete information, there is no global control, data is decentralized, and computation is asynchronous. She motivates MAS via open systems like the Internet where heterogeneous agents from different designers must interoperate, and surveys the main research problems: coordination, communication, negotiation, coherence, conflict resolution, and reasoning about other agents.

She organizes the field around issues (enabling communication, individual agent reasoning, adaptive coordination, protocols like Contract Net and KQML, reactive vs. deliberative architectures, emergent behavior) and applications (information gathering, e-commerce, manufacturing, health care, distributed planning). Throughout she emphasizes coherence — how locally-acting agents can achieve globally reasonable performance — as the defining challenge.

Key Ideas

Four MAS characteristics: incomplete info, no global control, decentralized data, async computation.
Coherence as the central research challenge.
Spectrum from reactive (stimulus-response) to deliberative (BDI) architectures.
Coordination requires reasoning about other agents’ expected behavior.
Organizations, markets, and scientific-community metaphors for MAS structure.

Connections

Conceptual Contribution

Claim: Multi-agent systems are the appropriate paradigm for open, distributed, heterogeneous problem-solving; they are characterised by four structural properties (incomplete info, no global control, decentralised data, async computation) and unified by the problem of achieving coherence through local decisions.
Mechanism: Survey-style synthesis organising the MAS field around: motivations (modularity, legacy interop, distributed data), core challenges (coherent coordination, negotiation, planning, conflict resolution), architectures (reactive, deliberative/BDI, hybrid), organisational metaphors (hierarchy, market, community, scientific), protocols (Contract Net, KQML), and application domains (info gathering, e-commerce, manufacturing, aircraft maintenance).
Concepts introduced/used: Multi-Agent Systems, Coherence, Problem-Solving Coherence, Contract Net Protocol, BDI Architecture, Reactive vs Deliberative Agents, Negotiation, Joint Intentions, Organizational Metaphors
Stance: survey / foundational
Relates to: Canonical MAS reference informing nearly every other note; defines the field that ACL Rethinking Principles and Verifiable Semantics for ACLs critique; organisational metaphors dovetail with How Do Committees Invent; negotiation/coordination theme continued in Toward Automated Evolution of ACLs and Coordinating Agents Using ACL Conversations.

Tags

Agents and Artifacts

Agents and Artifacts (A&A)

Meta-model treating the agent environment as first-class artefacts agents interact with, implemented in JaCaMo / CArtAgO.

In this vault

Metacognitive Loop

Self-monitoring feedback loop in which an agent observes its own behaviour against expectations and revises.

In this vault

A-ILTL

Attempto Interval Temporal Logic

Interval temporal logic variant used for runtime self-oversight rules in BDI agents.

In this vault

Ethical Governor

Runtime monitor that filters or blocks agent actions against ethical meta-rules.

In this vault

Ensuring Trustworthy and Ethical Behaviour in Intelligent Logical Agents

Reference: Stefania Costantini (2020; arXiv 2024). arXiv:2402.07547v1. Source file: 2402.07547v1.pdf. URL

Summary

Proposes runtime self-checking techniques for computational-logic-based (BDI-style) agents so they can monitor their own behaviour for trustworthiness and ethical compliance, beyond what static a-priori verification can guarantee. The core contribution is A-ILTL (Agent-Oriented Interval Linear Temporal Logic), a specification language for metaconstraints and evolutionary expressions that an agent can apply introspectively to its own state, goals, and actions.

Costantini argues that learning, open MAS, and long-lived autonomous systems make static model checking insufficient; agents must reflect on their behaviour and take counter-measures. The paper relates the approach to self-aware computing, Arkin’s ethical governor, Metacognitive Loops, and “restraining bolts” from reinforcement learning.

Key Ideas

Runtime verification (RV) complements static model checking for agents
A-ILTL: interval-LTL with metarules for self-checking BDI agents
Reification/naming mechanism allows meta-predicates solve/solve_not to gate actions
Trace expressions and introspection for ethical reasoning
Agents should reflect and self-improve — not merely obey hardcoded rules

Connections

Conceptual Contribution

Claim: A-priori (static) verification is insufficient for learning, evolving, or open-MAS agents; agents must themselves continuously self-monitor against ethical and behavioural constraints at runtime via a lightweight logic-based introspection mechanism.
Mechanism: Introduces A-ILTL (Agent-Oriented Interval Linear Temporal Logic) — a language-independent interval-temporal logic for specifying meta-constraints over an agent’s BDI state; Evolutionary A-ILTL Expressions include past events, a temporal property, future expected events, and repair countermeasures. Meta-rules with solve/solve_not meta-predicates gate object-level actions. Positioned as a complementary runtime “restraining bolt” alongside a-priori verification and RL-based ethical governors.
Concepts introduced/used: Runtime Verification, A-ILTL, BDI Agents, BDI, Mental State, Machine Ethics, Self-aware Computing, Self-Adaptive Systems, Meta-rules, Trace Expressions, Ethical Governor, Metacognitive Loop, Restraining Bolts
Stance: formal / ethics-engineering
Relates to: Builds on the logical-agent substrate of Foundations of Logic Programming - Lloyd and the BDI tradition surveyed in Intelligent Agents Theory and Practice. Its runtime-monitoring stance complements the empirical failure-mode work of Why Do Multi-Agent LLM Systems Fail and the trustworthiness framing of AI Agents Under Threat. Shares the “agent knows its own norms” spirit with commitment-based semantics in Agent Communication And Institutional Reality.

Tags

BDI

Belief-Desire-Intention

Dominant agent-architecture paradigm: agents maintain beliefs, desires, and intentions and deliberate over them.

In this vault

Mental State

Formally specified beliefs, desires, intentions, and commitments attributed to an agent as its program state.

In this vault

Agent-Oriented Programming

Reference: Shoham, Y. (1993). Artificial Intelligence 60, Elsevier. Source file: shoam-aop.pdf. URL

Summary

Shoham introduces Agent-Oriented Programming (AOP) as a specialization of object-oriented programming in which the state of each module — now called an agent — is a mental state composed of beliefs, capabilities, decisions/choices, commitments, and obligations. Interpretation of these components is formally grounded in an extension of standard epistemic logics that adds temporality, obligation, decision, and capability operators.

Agents communicate via speech-act-inspired primitives (inform, request, offer, promise, decline, etc.), constrained by rules such as honesty and consistency. The paper defines a class of agent interpreters and presents AGENT-0, a concrete implemented language whose semantics is tied to the mental-state logic. Shoham also discusses “agentification” — converting arbitrary devices into AOP-programmable agents — and situates AOP against BDI architectures, speech act theory, and McCarthy’s Elephant2000.

Key Ideas

AOP as OOP specialization with mental-state components.
Agents constrained by honesty/consistency on communicative acts.
Speech-act-typed primitives as message types.
AGENT-0 language and interpreter.
“Agentification” of arbitrary devices.

Connections

Conceptual Contribution

Claim: Programming can be fruitfully specialised to an “agent” paradigm in which module state is a formally specified mental state and inter-module communication is a speech act constrained by rational/ethical rules.
Mechanism: Shoham extends standard modal-epistemic logic with temporal, obligation, decision and capability operators, defines the mental-state components of an agent (belief, capability, commitment, choice, obligation), then specifies a generic agent interpreter cycle (update mental state, execute commitments, handle incoming messages) and instantiates it in AGENT-0, whose programs are condition-action rules over mental state and whose messages are typed INFORM/REQUEST/UNREQUEST primitives.
Concepts introduced/used: Agent-Oriented Programming, Mental State, Commitment, AGENT-0, Speech Act Theory, Agentification, BDI, Honesty Constraint
Stance: foundational
Relates to: Establishes the mentalistic ACL stance later criticised by Agent Communication Languages - Rethinking the Principles and surveyed by Intelligent Agents Theory and Practice; AGENT-0’s speech-act primitives anticipate KQML as an Agent Communication Language and FIPA-ACL; the mental-state architecture is reused in An Interaction-oriented Agent Framework for Open Environments.

Tags

Intelligent Agents Theory and Practice

Intelligent Agents: Theory and Practice

Reference: Wooldridge, M., Jennings, N. R. (1995). Knowledge Engineering Review. Source file: woodridge_intelligent_agents.pdf. URL

Summary

A foundational survey that organizes the agent-based computing field into three tightly coupled concerns: agent theories (formal specifications of what an agent is, often via intentional notions such as belief, desire, intention, obligation), agent architectures (software/hardware designs satisfying those specifications, e.g., BDI, subsumption, layered), and agent languages (programming languages whose primitives embody the theorists’ concepts).

Wooldridge and Jennings distinguish a weak notion of agency (autonomy, social ability, reactivity, pro-activeness) from a stronger AI-centric notion involving mentalistic attributes (knowledge, belief, intention) and sometimes emotion or mobility. They review representational and reasoning formalisms (modal logics for knowledge and belief, intention logics), critique their computational tractability, and survey implementations (AGENT-0, PLACA, Concurrent METATEM). The paper sets the vocabulary used by much subsequent MAS research.

Key Ideas

Three-way division: theory, architecture, language.
Weak vs. strong notion of agency.
Intentional stance justifies mentalistic ascription (Dennett/McCarthy).
BDI and related mental-state architectures.
Survey of 1990s agent languages and applications.

Connections

Conceptual Contribution

Claim: The emerging field of agent-based computing should be structured around the interlocking triad of agent theories, architectures and languages, and tensions between weak (behavioural) and strong (mentalistic) notions of agency should be kept explicit rather than elided.
Mechanism: Wooldridge and Jennings synthesise early 1990s work by (i) defining weak agency (autonomy, social ability, reactivity, pro-activeness) and strong agency (adds belief, desire, intention, emotion, mobility); (ii) surveying modal-logic theories of knowledge/belief/intention and the intentional stance as justification; (iii) cataloguing BDI, subsumption and layered architectures; and (iv) reviewing implemented languages (AGENT-0, PLACA, Concurrent METATEM) and representative applications. Computational tractability of the richer logics is flagged as a central open problem.
Concepts introduced/used: Weak Agency, Strong Agency, Intentional Stance, BDI, Subsumption Architecture, Layered Architecture, Concurrent METATEM, PLACA, Agent Theory-Architecture-Language Triad
Stance: survey
Relates to: Canonises the vocabulary used by Agent-Oriented Programming, Agent Communication Languages - Rethinking the Principles and Trends in Agent Communication Language; its tractability critique anticipates the social-semantic move in An Interaction-oriented Agent Framework for Open Environments.

Tags

Strong Agency

Wooldridge’s stronger notion: agents ascribed mental states (beliefs, desires, intentions) and intentional-stance explanations.

In this vault

Weak Agency

Wooldridge’s baseline notion: an agent is autonomous, social, reactive, and proactive — no mental-state commitment required.

In this vault

Protocol Documents

Agora’s content-addressed, LLM-negotiated specifications of message formats between agents.

In this vault

A Scalable Communication Protocol for Networks of LLMs

Extensible Distributed Coordination

Reference: Tobias Distler, Christopher Bahn, Alysson Bessani, Frank Fischer, Flavio Junqueira (2015). EuroSys ’15. Source file: eurosys15-edc.pdf. URL

Summary

The paper argues that coordination services such as ZooKeeper and DepSpace, which centralize primitives like locks, leader election, and queues for datacenter services, suffer because their fixed limited interfaces force multi-RPC workarounds that are slow and race-prone. The authors propose extensibility: clients can dynamically install small server-side “recipes” that execute atomically on the coordination kernel’s state, turning multi-step RPC patterns into single efficient operations.

They describe a model where extensions are sandboxed for safety (bounded resource use, determinism, no API extension) and present implementations — Extensible ZooKeeper (EZK) and Extensible DepSpace (EDS) — showing that extensibility increases throughput of a distributed queue by over an order of magnitude (17x for ZK, 24x for DepSpace) without breaking Byzantine fault tolerance or adding significant kernel complexity.

Key Ideas

Limited coordination-kernel APIs force inefficient RPC chains.
Custom extensions execute atomically server-side, like stored procedures for coordination state.
Sandboxing requirements: no API changes, security, determinism, bounded resource use.
Operation extensions vs. event extensions.
Huge throughput gains (17x, 24x) over ZooKeeper/DepSpace.

Connections

Conceptual Contribution

Claim: Coordination kernels (ZooKeeper, DepSpace) are fundamentally limited by fixed primitive APIs that force clients into inefficient multi-RPC workarounds; allowing dynamically-installed, sandboxed, server-side extensions preserves safety while dramatically improving throughput.
Mechanism: Defines an extension model (operation and event extensions) and sandbox requirements (no API modification, security, determinism, bounded resource use); implements EZK (ZooKeeper) and EDS (DepSpace); evaluates four standard recipes (shared counter, queue, barrier, leader election) showing 17-24x throughput gains.
Concepts introduced/used: Coordination Kernel, Server-Side Extensions, Sandboxing, Determinism, Byzantine Fault Tolerance, Stored-Procedure Coordination, Coordination Recipes
Stance: engineering
Relates to: Offers a systems counterpoint to the agent-level coordination abstractions in Coordinating Agents Using ACL Conversations and Multiagent Systems Sycara; shares the extensibility design philosophy of Extensibility in Programming Language Design - Standish applied to distributed state.

Tags

A Modular Approach to Metatheoretic Reasoning for Extensible Languages

Reference: Dawn Michaelson, Gopalan Nadathur, and Eric Van Wyk (2023). arXiv:2312.14374v1. Source file: 2312.14374v1.pdf. URL

Summary

Addresses the problem of proving metatheoretic properties (e.g. type preservation, information-flow non-interference) for languages composed from a host and a library of independently developed extensions. The authors propose decomposing proofs around language fragments and introducing a priori constraints — notably projection constraints that let extensions describe how their constructs behave at a distance — so that complete soundness proofs for any composed language can be automatically stitched together from per-extension partial proofs.

The framework distinguishes foundational properties (known to the host, like type preservation) from auxiliary properties (introduced by a later extension, like a security analysis). The paper develops the machinery in a relational logic with rule-based specifications and motivates the Extensibella and Sterling tool systems.

Key Ideas

Modular metatheory: per-extension partial proofs composed automatically
Projection constraints let extensions reason about unknown other extensions at a distance
Foundational vs auxiliary properties require different modularity treatments
Relational rule-based specifications with fixed-point semantics
Connects language-workbench practice to formal metatheory

Connections

Conceptual Contribution

Claim: Metatheoretic properties (type preservation, information-flow soundness, etc.) of an extensible language — built by composing a host language with a library of independently-developed extensions — can be proven modularly: each extension supplies a partial proof, and the host + projection-constraints framework guarantees these partial proofs compose soundly without a closed-world assumption.
Mechanism: Distinguish foundational properties (known at host-language design time; each extension contributes a local proof obligation) from auxiliary properties (introduced later by some extension; proofs must use projection relations to reason about other extensions’ constructs “at a distance”). Formalise the framework via a rule-based logic with least-fixed-point semantics; sketch realisation in the Extensibella and Sterling systems.
Concepts introduced/used: Metatheoretic Reasoning, Modular Proofs, Projection Relations, Foundational vs Auxiliary Properties, Language Workbenches, Type Preservation, Attribute Grammars, Closed World Assumption, Fixpoint Semantics, Relational Logic
Stance: formal / programming-language theory
Relates to: Supplies the metatheoretic rigour that Creating Languages in Racket and The Extensible Language - Graham implicitly assume but don’t prove. Directly addresses the theoretical obstacles Standish flagged in Extensibility in Programming Language Design - Standish for orthophrase-style extensions. The modular-composition instinct parallels Event-B refinement in Formalise Blockchain Interoperability Patterns.

Tags

The Spoofax Language Workbench

The Spoofax Language Workbench: Rules for Declarative Specification of Languages and IDEs

Reference: Kats, L. C. L., Visser, E. (2010). Proc. OOPSLA 2010, ACM SIGPLAN Notices. Source file: The_Spoofax_Language_Workbench_Rules_for_Declarati.pdf. URL

Summary

Spoofax is an Eclipse-based language workbench that lets developers define a DSL’s syntax, semantics, and full IDE support (syntax highlighting, content completion, reference resolution, refactoring, error marking, code generation) entirely via concise declarative specifications. Syntax is expressed in SDF with permissive error-recovery grammars; transformations, name analysis, and code generation are written in Stratego; editor services are declared in rule-based service descriptors.

The architecture separates language-parametric infrastructure from language-specific definitions and supports agile development: language definitions can be dynamically loaded into the same Eclipse instance and tested side-by-side. The paper describes component dependencies (grammar-driven presentation services, semantic services derived from name analysis) and contrasts Spoofax with EMFText, MPS, Xtext, and the Synthesizer Generator. The result is a coherent, concise toolchain for agile DSL + IDE development.

Key Ideas

Single declarative spec drives both compiler and IDE services.
SDF grammars + Stratego rewrites as the semantic base.
Permissive grammars for error recovery.
Editor service descriptors separate “which” from “what”.
Dynamic loading enables agile language development.

Connections

Conceptual Contribution

Claim: A language and its IDE can be specified together, declaratively, from a single set of high-level rules — removing the gulf between compiler front-ends and interactive tooling that has historically doomed DSLs to poor editor support.
Mechanism: Spoofax composes SDF (scannerless generalized-LR grammars, with permissive error-recovery productions), Stratego (rewrite-based transformations for name analysis, type checking, code generation), and editor-service descriptors that declare syntax highlighting, reference resolution, completion, outline, and refactoring. The Eclipse plug-in hot-loads new language definitions, enabling round-trip agile development; grammar-driven services are separated from semantics-driven services to manage dependencies.
Concepts introduced/used: Language Workbench, SDF, Stratego, Editor Service Descriptor, Permissive Grammar, Declarative Specification, Meta-Programming, DSL
Stance: engineering
Relates to: A concrete instance of the “whole-language” tooling vision behind A Modular Approach to Metatheoretic Reasoning for Extensible Languages and Extensibility in Programming Language Design - Standish; the rule-based services resonate with Creating Languages in Racket, and the formal-analysis possibilities connect to the dependability specification of Architectural Patterns for Dependable Software Systems - SOL.

Tags

Creating Languages in Racket

Reference: Matthew Flatt (2012). Communications of the ACM, Vol. 55, No. 1. Source file: 2063176.2063195.pdf. URL

Summary

Practitioner-oriented introduction to Racket’s support for language-oriented programming: building domain-specific languages as a natural extension of ordinary programming. Flatt develops a text-adventure game incrementally, starting from Racket’s core, adding pattern-matching macros (define-syntax-rule) for define-place, define-thing, define-verb, then packaging these extensions into a module language (#lang txtadv) with its own non-parenthesised reader syntax and IDE (DrRacket) support.

The article demonstrates the full spectrum from simple syntactic abstraction via macros up through module languages that replace the default reader, showing how Racket smooths the path from library to full DSL.

Key Ideas

Language-oriented programming as a practical paradigm
define-syntax-rule and syntax-case macros for pattern-based extension
Module languages (#lang ...) package extensions as first-class languages
Static checks can be implemented via macro-level type tagging
DrRacket provides IDE integration for custom languages

Connections

Conceptual Contribution

Claim: Language-oriented programming — building a small DSL exactly fitted to a task — should be cheap and incremental, not a heavyweight “build a compiler” affair; Racket’s macro system and module-language machinery make this the normal way to program.
Mechanism: Walk through a text-adventure game implementation that evolves from plain-Racket library → syntactic abstractions (define-syntax-rule for define-place, define-thing) → a full #lang txtadv module language with custom reader, static checks via compile-time elaboration, and replaceable surface syntax; show each step as a small syntactic or module addition rather than a rewrite.
Concepts introduced/used: Language-oriented Programming, Racket Macros, Module Languages, Syntactic Abstraction, DSLs, Domain-Specific Languages, Language Workbenches, Hygienic Macros, Macros as Language Extension
Stance: engineering / tutorial
Relates to: Modern realisation of the paraphrase-extension ideal diagnosed in Extensibility in Programming Language Design - Standish and evangelised in The Extensible Language - Graham. Provides the practice for which A Modular Approach to Metatheoretic Reasoning for Extensible Languages supplies a metatheoretic backbone.

Tags

Code as Data

Homoiconicity: program text and program structure share a representation, enabling macros and meta-programming.

In this vault

Macros as Language Extension

Using macros (hygienic or otherwise) to add syntactic forms indistinguishable from built-ins, enabling embedded DSLs.

In this vault

Bottom-up Programming

Design style where the language is grown toward the problem via new operators and macros, rather than the program compressed into a fixed language.

In this vault

The Extensible Language - Graham

The Extensible Language

Reference: Paul Graham (1993). On Lisp (Chapter 1). Source file: 01theExtensibleLanguage.pdf. URL

Summary

Opening chapter of Graham’s On Lisp that argues Lisp’s defining quality is its extensibility: the language can be molded into a dialect suited to the program being written. Graham distinguishes top-down from bottom-up design and claims Lisp programmers customarily do both — building the language up toward the problem while writing the program down toward it.

The chapter introduces macros, embedded languages, and the idea that a mature Lisp program looks “as if the language had been designed for it.” It argues that software extensibility (where users extend a program in its own implementation language) is a more honest outgrowth of bottom-up programming than traditional black-box designs.

Key Ideas

Bottom-up design: grow the language toward the problem via new operators and macros
Lisp programs are data — macros are programs that write programs
Embedded languages as a natural idiom; Common Lisp includes several (e.g. CLOS)
Extensible software as a paradigm; language and program co-evolve

Connections

Conceptual Contribution

Claim: A language’s power lies not in a fixed feature set but in its capacity to be grown, by its users, into a problem-specific dialect — Lisp’s distinguishing virtue is that it makes this routine.
Mechanism: Code-as-data (s-expressions) + macros + first-class functions enable users to add operators indistinguishable from built-ins; bottom-up design then layers embedded languages on top of the base.
Concepts introduced/used: Bottom-up Programming, Macros as Language Extension, Embedded Languages, Domain-Specific Languages, Language Workbenches, Code as Data, S-expressions, Lisp
Stance: engineering / manifesto
Relates to: Shares a through-line with Extensibility in Programming Language Design - Standish (paraphrase/orthophrase/metaphrase taxonomy), Creating Languages in Racket (macro-based language-oriented programming), and A Modular Approach to Metatheoretic Reasoning for Extensible Languages (formal reasoning about user-added language fragments). The same “grow the language toward the problem” instinct reappears in agent-communication as Agora’s emergent Protocol Documents in A Scalable Communication Protocol for Networks of LLMs.

Tags

Metaphrase

Standish’s category of extensibility where programmers add new meanings via interpretation changes — the hardest and least delivered.

In this vault

Orthophrase

Standish’s category: extending a language with genuinely new primitive constructs — requires compiler-writer skill.

In this vault

Paraphrase

Standish’s category: defining new constructs in terms of existing ones (essentially macros) — the only extensibility actually delivered at scale.

In this vault

Extensibility in Programming Language Design - Standish

Extensibility in Programming Language Design

Reference: Thomas A. Standish (1975). National Computer Conference 1975 (AFIPS). Source file: 1499949.1500003.pdf. URL

Summary

A retrospective on the 1960s-70s “extensible languages” movement. Standish catalogues extension techniques (paraphrase, orthophrase, metaphrase), reviews what the early community hoped for — a universal base language that any user could tailor with modest effort — and explains why those hopes were only partly realised. He concludes that extensibility relates to high-level languages the way macros relate to assembly: useful for suppressing low-level detail and masking irritating features, but not the programming revolution once promised.

The paper is an early, honest assessment of why language extension is harder than anticipated, introducing vocabulary still used today.

Key Ideas

Paraphrase: defining new forms via existing ones (macros, procedures)
Orthophrase: adding orthogonal features that cannot be paraphrased
Metaphrase: altering interpretation rules (scoping, evaluation)
Early euphoria vs realistic assessment of labour/skill costs
27 extensible languages proposed by 55 people by 1975

Connections

Conceptual Contribution

Claim: The 1960s-70s dream of universal extensible languages largely failed because extension techniques divide into qualitatively different kinds with very different labor costs; only the cheapest (paraphrase, macros) proved practically useful.
Mechanism: Taxonomy of extension techniques — paraphrase (define new forms in terms of existing ones: macros, procedures, syntax macros, data/operator definitions), orthophrase (add genuinely new features outside the base language’s span, e.g. I/O primitives), and metaphrase (alter interpretation rules: scoping, evaluation order). Argues orthophrase/metaphrase require near-compiler-writer expertise and rarely pay off.
Concepts introduced/used: Paraphrase, Orthophrase, Metaphrase, Macros as Language Extension, Language Extensibility Taxonomy, Extensible Languages Movement, Domain-Specific Languages
Stance: retrospective-critique / taxonomic
Relates to: Direct intellectual ancestor of The Extensible Language - Graham and Creating Languages in Racket, both of which represent the paraphrase/macro wing that Standish judged successful. A Modular Approach to Metatheoretic Reasoning for Extensible Languages tackles the metatheoretic difficulties Standish foresaw for orthophrase extensions.

Tags

Fallacies - Hamblin

Fallacies

Reference: Hamblin, C. L. (1970). Fallacies. Methuen, London. (Reprinted 1986 by Vale Press; reissued 2022 by University Press of America.) Google Books preview · McMaster summary (book; no full-text OA.)

Summary

Hamblin’s Fallacies is the founding text of the modern revival of formal dialectic. The book has two halves. The first is a magisterial historical and critical survey demolishing what Hamblin calls the Standard Treatment: the lazy textbook tradition of cataloguing fallacies as freestanding logical errors, traceable to a misreading of Aristotle that has propagated unchanged through two thousand years of logic textbooks. Hamblin shows that almost every “fallacy” in the standard inventory either is not actually fallacious in context, is fallacious for reasons orthogonal to those typically given, or is incoherent as classified. The second half supplies a constructive alternative: a formal dialectical treatment in which arguments are evaluated not in isolation but as moves within rule-governed dialogues. The technical centrepiece is the commitment store: each participant in a dialogue has a public set of propositions to which they have committed, updated by their dialogue moves under explicit rules (statements add commitments, “Why?”-challenges may force retraction or defence, concessions add to the conceder’s store, and so on). A move is fallacious iff it violates the rules of the dialogue type — a context-relative notion that finally distinguishes (e.g.) when petitio principii is genuinely circular reasoning and when it is licit appeal to shared ground. The book inaugurated the dialectical tradition that runs through Walton & Krabbe 1995, Mackenzie, Pollock, and the entire computational-argumentation field; the commitment-store concept is the operational ancestor of every commitment-based ACL semantics.

Key Ideas

The Standard Treatment is incoherent: the textbook list of fallacies (begging the question, ad hominem, ad baculum, equivocation, …) cannot be analysed at the level of individual arguments because what counts as fallacious depends on the dialogue context and the participants’ shared and individual commitments.
Arguments live in dialogues: an argument is a move in a structured exchange; its assessment requires the dialogue’s rules — what are the legal moves, what does each move oblige one to defend, what counts as winning?
Commitment store as the engine: each participant’s public commitment set is updated by their moves; the dialogue’s rules govern what one is licensed to say given the current state of one’s own and others’ stores.
Why-because-question games: Hamblin gives explicit toy dialogue systems (variants of the “H system”) in which moves are Statement, Question, Challenge, Retract, Resolve and the rules govern what each licenses or requires.
Fallacies as dialogue-rule violations: petitio principii becomes the move of trying to use as a premise something the opponent has not yet committed to (or has explicitly challenged); ad hominem becomes the illicit shift from a persuasion to a personal-attack dialogue; etc.
Recovery of Aristotle: Hamblin’s reading of Aristotle’s Sophistical Refutations shows that the original treatment was already dialectical — it was the medieval and modern textbook tradition that flattened it into a list of logical errors.
The book’s lasting move: not a particular dialogue system but the programme of taking dialogue as the primary unit of analysis, which Walton & Krabbe (1995) and the computational-argumentation literature (Prakken, Vreeswijk, McBurney, Parsons) made operational.

Connections

Conceptual Contribution

Claim: Fallacies cannot be analysed as defects of single arguments; they are violations of the rules of the dialogue type within which the argument is offered. The right unit of analysis is the dialogue, with explicit rules governing each participant’s commitment store and the legitimate moves that update it.
Mechanism: Critical demolition of the Standard Treatment via close textual reading from Aristotle through 19th-century logic textbooks; constructive presentation of toy dialogue systems (the “H system” and variants) with explicit move-rules and commitment-store updates; reanalysis of canonical fallacies as type-specific rule violations.
Concepts introduced/used: Commitment Store, Formal Dialectic, Dialogue Move, Why-Statement-Resolve game, petitio principii qua dialectical fault, Standard Treatment.
Stance: founding theoretical monograph of modern dialectic.
Relates to: Direct ancestor of Commitment in Dialogue (Walton & Krabbe 1995), which extends Hamblin’s commitment-store machinery into a six-type dialogue typology and supplies the framework that the ACL commitment-based semantics tradition takes as given. The commitment-store concept is the operational primitive of Singh’s critique of mentalistic ACL semantics: where KQML / FIPA-ACL ground meaning in private mental states, Singh grounds it in public commitments — a direct lift of Hamblin into multi-agent communication. The dialectical-rules approach is also the upstream ancestor of structured argumentation systems (ASPIC+, ABA, DeLP) that instantiate Dung’s abstract framework with rule languages, and of dialogue-game protocol specifications (Coordinating Agents Using ACL Conversations, ACRE Agent Conversation Reasoning Engine). On the LLM-agent side, Hamblin’s central insight — that the fallaciousness of a move depends on the dialogue type and rules — is precisely the diagnostic missing from most LLM-agent debate / self-consistency setups: there is no commitment store, no dialogue type, and so no principled way to identify illegitimate moves.

Tags

#dialogue #formal-dialectic #commitment-stores #fallacies #foundations #hamblin #pragmatics

Commitment in Dialogue

Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning

Reference: Walton, D. N. & Krabbe, E. C. W. (1995). Commitment in Dialogue: Basic Concepts of Interpersonal Reasoning. SUNY Series in Logic and Language. State University of New York Press, Albany. Internet Archive borrow (book; institutional access via SUNY.)

Summary

Walton and Krabbe synthesise two decades of work on formal dialectic (Hamblin 1970 onward) and informal logic into a typology of dialogue and a corresponding theory of how participants’ commitments evolve as a dialogue proceeds. Their central observation is that argumentation in natural settings is not a single uniform activity but a structured family of dialogue types, each characterised by its initial situation, the individual goals of the participants, and the shared goal of the dialogue. The six basic types they identify — persuasion, negotiation, deliberation, inquiry, information-seeking, eristic — are mutually distinguished by these three dimensions and by their characteristic legitimate moves. Across all types, every utterance updates each participant’s commitment store: the public set of propositions to which they have committed, are committed by inference, and may be challenged on. The book gives semi-formal rules for each dialogue type, analyses dialogue shifts (moves that licitly or illicitly transition between dialogue types — e.g. a persuasion shifting to a negotiation), and uses the framework to give principled accounts of fallacies as illegitimate dialogue moves rather than logical errors. Its influence on multi-agent systems is enormous: every commitment-based ACL semantics (Singh, Fornara & Colombetti) inherits the Hamblin/Walton commitment-store concept; protocol-design work (e.g. ACRE, An Interaction-oriented Agent Framework for Open Environments) uses dialogue-type analysis to specify legitimate conversation policies.

Key Ideas

Six basic dialogue types: persuasion (resolve a conflict of opinion), negotiation (resolve a conflict of interest), deliberation (decide on a course of action), inquiry (establish proof of a hypothesis from agreed premises), information-seeking (transfer of information from informed to uninformed), eristic (vent emotion / display superiority). Each is characterised by initial situation × individual goals × shared goal.
Commitment store as the engine of dialogue: every participant has a public set of commitments updated by their moves; speech acts add, retract, or qualify entries. The store is open to challenge by other participants under the dialogue’s rules.
Dialectical / propositional commitments: Walton & Krabbe distinguish explicit commitments (asserted propositions) from inferred commitments (entailed by, or presupposed by, what was said) — a distinction crucial for capturing implicit communication.
Dialogue shifts: most real argumentation moves between dialogue types. Some shifts are licit (a persuasion may legitimately broaden into a deliberation); others are illicit (an information-seeking dialogue exploited as a covert persuasion is a fallacy of digression).
Fallacies as dialogue-rule violations: rather than treating fallacies as defects of single arguments (the syllogistic tradition), they are analysed as moves that violate the rules of the dialogue type they occur in — a circular argument is fine in inquiry but fallacious in persuasion.
Profiles of dialogue: a sequence diagram of typical turns within a dialogue type — the precursor of Conversation Policy / interaction-protocol diagrams in the ACL literature.

Connections

Conceptual Contribution

Claim: Argumentation is not a single uniform activity but a structured family of dialogue types characterised by the participants’ goals; within each type, every utterance updates each participant’s public commitment store under type-specific rules; fallacies are best analysed as illegitimate dialogue moves rather than as defective arguments.
Mechanism: Six basic dialogue types defined by initial situation × individual goals × shared goal; dialogue rules per type; commitment-store update semantics; analysis of dialogue shifts and mixed dialogues; classification of fallacies as type-specific rule violations.
Concepts introduced/used: Dialogue Typology, Commitment Store, Persuasion Dialogue, Deliberation Dialogue, Inquiry Dialogue, Information-Seeking Dialogue, Eristic Dialogue, Negotiation, Dialogue Shift, Profile of Dialogue.
Stance: synthesis monograph / theoretical framework.
Relates to: Provides the upstream typology that the commitment-based ACL programme (Singh, Fornara & Colombetti, Commitment Machines - Yolum and Singh) takes as given when it makes commitments first-class. The Hamblin commitment-store mechanism (Fallacies - Hamblin) is the operational heart; Walton & Krabbe extend it with the dialogue-type framing. Conceptually adjacent to Grice’s cooperative principle but more granular: where Grice supplies a single cooperative norm, Walton & Krabbe show that the relevant cooperation is type-specific (persuasion ≠ negotiation ≠ inquiry). Coordinating Agents Using ACL Conversations (Cost et al.) and ACRE Agent Conversation Reasoning Engine are direct engineering descendants — Coloured Petri Nets and Dooley graphs are formal specifications of the kinds of dialogue Walton & Krabbe describe semi-formally. In the LLM-agent era the dialogue-type taxonomy is the obvious diagnostic for MAST-style failures (e.g. multi-agent systems unwittingly conducting eristic dialogues at scale, or persuasion-shifts hijacking deliberations) and a natural specification language for conversation-policy enforcement.

Tags

#dialogue #argumentation #commitment-stores #foundations #walton #krabbe #pragmatics #acl-foundations

Stable Extension

In an Argumentation Framework, an admissible set that attacks every argument outside it. A stable extension may not exist (e.g. an odd-length attack cycle defeats stability); when it does, it coincides with one of the preferred extensions. Dung’s central correspondence theorem: stable extensions of an AF coincide with the stable models of the corresponding normal logic program (Gelfond–Lifschitz semantics) — the fact that established Dung’s framework as the unifying abstraction across nonmonotonic reasoning.

In this vault

Preferred Extension

In an Argumentation Framework, a maximal (with respect to set inclusion) admissible set — a most-permissive coherent position. Multiple preferred extensions can exist; they correspond to credulous acceptance (an argument is credulously accepted iff it appears in some preferred extension). Computational complexity is higher than for the Grounded Extension (Π₂ᵖ-complete for credulous acceptance).

In this vault

Grounded Extension

In an Argumentation Framework, the unique smallest complete extension — the least fixed point of Dung’s characteristic function F_AF. The grounded extension represents the sceptical answer: only arguments that survive every challenge by the framework’s own machinery are accepted. Always exists and is unique; computable in polynomial time. The default semantics for risk-averse reasoning.

In this vault

Argumentation Framework

Dung’s (1995) abstraction: a directed graph (A, R) whose nodes are arguments and whose edges R ⊆ A × A are attacks. The semantics is content-free — what an argument is is supplied by the instantiating theory — but the family of extensions (Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, complete) is universal. The substrate for ASPIC+, ABA, DeLP, multi-agent dialogue protocols, legal reasoning systems, and (recently) LLM-agent debate.

In this vault

On the Acceptability of Arguments

On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming, and n-Person Games

Reference: Dung, P. M. (1995). On the Acceptability of Arguments and its Fundamental Role in Nonmonotonic Reasoning, Logic Programming and n-Person Games. Artificial Intelligence, 77(2), pp. 321–357. DOI · Open access PDF (CUNY)

Summary

Dung shows that an enormous span of problems in AI — nonmonotonic reasoning, logic programming, n-person game theory — share a single underlying abstraction: a directed graph whose nodes are arguments and whose edges are attacks. He calls this an abstract argumentation framework (AF) and develops, in 30 pages, the entire theory of argument acceptability that has dominated computational argumentation ever since. The headline definitions: a set of arguments is conflict-free if it contains no attacker-attackee pair; admissible if it is conflict-free and defends each of its members against every attacker (an argument is defended if every attacker on it is itself attacked by something in the set); complete if it is admissible and contains every argument it defends; grounded (the unique smallest complete extension), preferred (a maximal admissible set), stable (admissible and attacks every argument outside it). Dung then proves the unifying results: the stable extensions of an AF coincide with the stable models of the corresponding logic program (Gelfond–Lifschitz); preferred extensions correspond to the preferred logic-programming semantics; default-logic extensions arise as stable extensions of an AF derived from default rules; and (the n-person game result) the stable extensions of a game’s argumentation graph correspond to the stable strategies of the game. The framework is content-agnostic — what an “argument” is is left to the instantiating theory — which is precisely what makes it apply across so many domains. Three decades later it is the substrate for legal reasoning systems, multi-agent dialogue protocols, structured argumentation calculi (ASPIC+, ABA, DeLP), and the theoretical underpinning of LLM-agent debate frameworks.

Key Ideas

Argument as a black box, attack as a binary relation: the AF (A, R) with A a set of arguments and R ⊆ A × A is the entire syntactic apparatus. All domain-specific structure (premises, conclusions, defeasible rules) is internalised when the AF is instantiated.
Defence as the operative concept: an argument a is defended by a set S iff every attacker of a is itself attacked by some member of S. Acceptability is “S defends every member of S.”
Family of extensions: admissible (defends itself), complete (admissible + closure), grounded (least complete — sceptical), preferred (maximal admissible — credulous), stable (admissible + attacks everything outside).
Universal correspondences: stable extensions ⇔ stable models of normal logic programs; preferred extensions ⇔ preferred semantics of logic programs; default-logic extensions ⇔ stable extensions of the AF generated by the defaults; the stable extensions of a 2-person game’s defeat graph ⇔ winning strategies.
Inference as fixed-point computation: each semantics is the fixed point of a characteristic operator on 2^A; the order-theoretic structure (complete partial order of admissible sets) makes the theory algorithmically tractable.
Sceptical vs credulous reasoning: every AF supports both — a is sceptically accepted iff in every preferred extension; credulously accepted iff in some preferred extension. The choice is a downstream policy decision.
Why it works as a unifier: nonmonotonic reasoning, default logic, logic programming with negation-as-failure, and game-theoretic equilibria all reduce to “find a coherent set of accepted positions in the presence of mutual challenge” — which is exactly what Dung’s framework computes.

Connections

Conceptual Contribution

Claim: Acceptability of arguments under attack is the abstraction common to nonmonotonic reasoning, logic programming with negation-as-failure, default logic, and equilibrium notions in n-person games. A single, content-free framework — a directed graph of arguments and attacks plus a fixed family of acceptability conditions — captures all of them.
Mechanism: Abstract argumentation framework (A, R); characteristic function F_AF : 2^A → 2^A mapping a set to the arguments it defends; admissible / complete / grounded / preferred / stable extensions defined as fixed points of F_AF under various conditions; instantiation theorems mapping logic-programming and default-logic problems to AFs and proving extension-correspondence.
Concepts introduced/used: Argumentation Framework, Attack Relation, Admissible Set, Grounded Extension, Preferred Extension, Stable Extension, Defence (Argumentation), Sceptical Reasoning, Credulous Reasoning.
Stance: foundational technical paper.
Relates to: Conceptually the missing companion of Circumscription - A Form of Nonmonotonic Reasoning (McCarthy 1980) — both address nonmonotonicity, but Dung gives an argumentation-graph framing that plays directly with logic-programming semantics where circumscription works at the level of model-theoretic minimisation. Provides the formal substrate beneath the dialogue-game tradition: a Persuasion Dialogue (Walton & Krabbe) is operationally a process for constructing the attack edges of a shared AF and computing extensions over it. The structured-argumentation systems (ASPIC+, ABA, DeLP, defeasible logic programming) instantiate Dung’s abstract framework with rule-based languages — and the SPL/Hence defeasible-logic engine used elsewhere in this vault is in this same family. In the LLM-agent era, multi-agent debate / self-consistency protocols recapitulate Dung’s machinery: agents generate arguments, attacks are mined from contradictions, and grounded/preferred extensions correspond to convergent / multi-modal answers. The paper’s reach into n-person games supplies a bridge to the game-theoretic / mechanism-design strands of Pact - A Choreographic Language for Agentic Ecosystems and Deals Among Rational Agents.

Tags

#argumentation #nonmonotonic-reasoning #logic-programming #foundations #dung #defeasible-reasoning #multi-agent

Common Business Communication Language

The Common Business Communication Language

Reference: John McCarthy (1975/1982, revised 1998/1999). Stanford CS Department. Source file: cbcl2.pdf. URL

Summary

McCarthy’s 1975 memo (revived in 1998 with footnotes anticipating XML and electronic commerce) sketches a Common Business Communication Language (CBCL) allowing computers from different organizations to exchange business messages - requests for quotations, offers, order status, delivery queries - without pre-arranged bilateral formats. The paper enumerates requirements: open-endedness, pre-existing compatibility, independence of internal data formats, and ability to fall back to human-readable form when a receiver does not understand a new message.

He proposes messages as nested parenthesized lists (a Lisp-like syntax McCarthy argues is isomorphic to but simpler than XML), adjectival modifiers (ADJECTIVE FOO YELLOW), and Russell description operators for referring expressions. The essay prefigures KQML-style performatives and electronic data interchange, and closes with 1998 advice to XML, W3C, and ICE on extensibility, Lisp-style syntax, and standard time formats.

Key Ideas

Inter-organizational computer communication without pre-arranged formats.
Lisp-style S-expression syntax isomorphic to but simpler than XML.
Adjectival modifiers (ADJECTIVE x y as a kind of y) for partial understanding.
Non-monotonic reasoning required for natural-language-like expressivity.
Proto-KQML vision of semantic business messaging.

Connections

KQML
Agent Communication Languages
Three Models For The Description Of Language
Ontologies
Elephant 2000 - A Programming Language Based on Speech Acts — companion McCarthy proposal; CBCL messages are the inter-organisational counterpart of Elephant’s intra-program speech acts.
First Order Theories of Individual Concepts and Propositions — supplies the sense/denotation machinery CBCL tacitly relies on for descriptions.
Circumscription - A Form of Nonmonotonic Reasoning — the non-monotonic reading of ADJECTIVE and partial-understanding fallback rests on circumscription-style defaults.
Ascribing Mental Qualities to Machines
CBCL - Safe Self-Extending Agent Communication — O’Connor 2026 (LangSec ’26): Lean-verified contemporary realisation of this proposal.

Conceptual Contribution

Claim: Organisations should exchange business messages in a common, open-ended language without pre-arranged bilateral formats; partial understanding must degrade gracefully to human-readable fallback.
Mechanism: Lisp-style S-expression messages (isomorphic to but simpler than XML), adjectival modifiers (ADJECTIVE x y) for partial-match semantics, Russell description operators for referring expressions, non-monotonic reasoning for NL-like expressivity; 1998 footnotes advise XML/W3C/ICE communities.
Concepts introduced/used: Common Business Communication Language, S-expressions, EDI, Non-monotonic Reasoning, Adjectival Modifiers, Agent Communication Languages, Ontologies, Performatives, Speech Act Theory, KQML
Stance: foundational
Relates to: Anticipates the performative-based vision of KQML Language And Protocol and the open discovery ambitions of Agent Network Protocol / Survey Of Agent Interoperability Protocols; its syntactic minimalism resonates with REST’s uniform interface in Principled Design Of The Modern Web Architecture.

Tags

On the Pitfalls of Measuring Emergent Communication

Reference: Lowe, Foerster, Boureau, Pineau, Dauphin (2019). AAMAS 2019 (Proc. 18th Intl. Conf. on Autonomous Agents and Multiagent Systems). Source file: p693.pdf. URL

Summary

This paper critically examines metrics used to detect and measure emergent communication in multi-agent reinforcement learning. The authors show that commonly used indicators — such as speaker consistency (SC), context independence (CI), mutual information between messages and actions, and message-entropy — can be misleading: agents trained with a communication channel that does not influence their behavior may still exhibit high values on these metrics, producing the illusion of communication.

To disentangle the phenomenon, they propose decomposing communication into positive signaling (messages carry information about a speaker’s observations) and positive listening (messages influence a listener’s subsequent actions). They introduce causal influence of communication (CIC), a causal-intervention-based metric measuring how an agent’s message changes another agent’s action distribution, and demonstrate its properties on matrix communication games (MCGs). They offer concrete recommendations for when each metric should be trusted.

Key Ideas

Speaker consistency can be positive even when no communication happens.
Separate positive signaling from positive listening.
Causal influence of communication (CIC) via interventions on messages.
Matrix Communication Games as a minimal testbed.
Entropy-based metrics are shape-dependent and deceptive.

Connections

Conceptual Contribution

Claim: Popular metrics for emergent communication in MARL cannot distinguish real communication from spurious correlations; communication must be analysed causally, decomposed into signalling and listening.
Mechanism: The authors construct Matrix Communication Games where a policy with a non-influential communication channel still scores high on speaker consistency, context independence, mutual information, and entropy-based measures. They then define positive signalling and positive listening as orthogonal properties, and introduce Causal Influence of Communication (CIC) as a do-calculus intervention that measures how replacing the sent message would change the listener’s action distribution.
Concepts introduced/used: Positive Signalling, Positive Listening, Causal Influence of Communication, Speaker Consistency, Context Independence, Matrix Communication Games, Emergent Communication
Stance: critique
Relates to: Sharpens the empirical agenda of Emergence of Grounded Compositional Language in Multi-Agent Populations and Emergent Communication; its causal framing complements the decision-theoretic message-value account in Towards Automating the Evolution of Linguistic Competence and offers a verifiability foothold missing from the mentalistic semantics critiqued by Agent Communication Languages - Rethinking the Principles.

Tags

Emergence of Grounded Compositional Language in Multi-Agent Populations

Reference: Igor Mordatch and Pieter Abbeel (2018). AAAI-18. Source file: 11492-13-15020-1-2-20201228.pdf. URL

Summary

Proposes a multi-agent environment and differentiable training procedure in which agents develop an abstract compositional communication protocol purely from the need to coordinate on non-linguistic goals (move-to-location, look-at, etc.) in a 2D world with landmarks. Agents emit streams of discrete symbols (Gumbel-Softmax relaxed) along with physical actions; symbols acquire stable, interpretable meanings corresponding to goal types, landmarks, and agent identities.

The emergent language exhibits syntactic ordering, vocabulary-size regularization via a Dirichlet-process-inspired penalty, and non-verbal strategies (pointing, guiding) when symbols are disabled. The paper is a foundational piece in the modern “emergent communication” literature.

Key Ideas

Communication emerges from cooperative multi-agent RL with shared reward
Gumbel-Softmax makes discrete symbol channels differentiable
Vocabulary-size penalty (DP-style) prevents symbol proliferation and encourages compositionality
Non-verbal channels (gaze, position) substitute when verbal is unavailable
Symbols ground to concepts: GOTO, color, landmark/agent identity

Connections

Conceptual Contribution

Claim: A basic compositional language with coherent vocabulary and rudimentary syntax can emerge from scratch among agents in a physically-grounded, cooperative multi-agent environment, driven purely by the need to coordinate on shared goals.
Mechanism: N agents with private goals share a continuous 2D environment and emit discrete symbol streams; policies are trained end-to-end with differentiable communication (Gumbel-Softmax), shared reward, plus a Dirichlet-process-inspired vocabulary-sparsity penalty and an auxiliary goal-prediction reward. Non-verbal strategies (pointing, gaze) emerge when symbolic channel is unavailable.
Concepts introduced/used: Emergent Communication, Grounded Compositional Language, Symbol Grounding Problem, Compositionality, Gumbel-Softmax, Multi-Agent Reinforcement Learning, Referential Games, Language Games, Non-verbal Communication, Vocabulary Size Penalty, Dirichlet Process
Stance: empirical / computational-simulation
Relates to: Companion to Multi-Agent Cooperation and the Emergence of Natural Language (also referential games but 2-player, image-based). Contrasts with the pre-designed KQML as an Agent Communication Language and FIPA-ACL approaches: here semantics emerge from task pressure rather than being stipulated. Resonates with the emergent-protocol behaviour Agora exhibits in A Scalable Communication Protocol for Networks of LLMs.

Tags

Emergent Communication

How communication arises between agents through interaction and learning.

Towards Automating the Evolution of Linguistic Competence

Towards Automating the Evolution of Linguistic Competence in Artificial Agents

Reference: Gmytrasiewicz, P. J., Gopal, D. (2000). Technical article, University of Texas at Arlington. Source file: Towards_Automating_the_Evolution_of_Linguistic_Com.pdf. URL

Summary

Gmytrasiewicz and Gopal propose a decision-theoretic framework for artificial agents to autonomously enrich and evolve their shared agent communication language. Each agent has a frame/object-based knowledge representation language (KRL) encoding beliefs about the world and nested beliefs about other agents. Decisions about which messages to send are grounded in expected-utility computations over the effect on the hearer’s mental state, so every well-defined message carries measurable value to the speaker.

When the ACL proves inadequate to express content the agent wishes to communicate, the agents engage in game-theoretic negotiation (after Rubinstein-style alternating offers) over new lexicon items and grammatical rules. Utilities trade off implementation cost, time-discounting, and communicative gain. The framework thus gives a concrete mechanism for pidgin-like emergence of shared ACLs among rational, knowledge-based agents.

Key Ideas

KRL as agents’ “language of thought”; ACL is a translation target.
Message value = expected-utility impact on hearer’s mental state.
Negotiation over lexicon and grammar when ACL is insufficient.
Nested agent models enable rational communication choices.
Decision-theoretic, game-theoretic grounding for language emergence.

Connections

Conceptual Contribution

Claim: The content and extension of an agent communication language can be derived from rational-decision principles: every message carries measurable expected utility, and when the current ACL is insufficient, agents rationally negotiate new lexicon and grammar.
Mechanism: Each agent has a frame-based KRL representing nested beliefs about others; message utility is computed as the expected change in the hearer’s mental state weighed against action value. When no existing ACL expression suffices, Rubinstein-style alternating-offers bargaining over new lexicon items and grammar rules trades off implementation cost, time-discount, and future communicative gain, producing a pidgin-like convergence path.
Concepts introduced/used: Knowledge Representation Language, Expected Utility Communication, Rubinstein Bargaining, Nested Beliefs, Lexicon Negotiation, Pidgin Emergence, Decision-Theoretic ACL
Stance: formal-semantic
Relates to: Provides a decision-theoretic counterpart to the situated emergence of Language Games for Autonomous Robots and the neural emergence studied in On the Pitfalls of Measuring Emergent Communication; its utility-grounded messages contrast with the mentalistic sincerity conditions of Agent-Oriented Programming and FIPA-ACL.

Tags

Language Games

Wittgenstein-inspired situated interactions in which agents bootstrap grounded shared vocabulary without a central designer.

In this vault

Three Models for the Description of Language

Reference: Noam Chomsky (1956). IRE Transactions on Information Theory. Source files: 195609-.pdf, chomksy.txt. URL

Summary

Chomsky’s seminal paper comparing three candidate models of linguistic structure — finite-state Markov processes, phrase-structure grammars, and transformational grammars — and showing that each is strictly more powerful than the last. He proves that English cannot be described by any finite-state grammar (via dependencies like “either…or”, “if…then” that require unbounded memory), and argues that even phrase-structure grammars, while formally adequate, yield awkward and complex descriptions of phenomena (auxiliaries, passives, discontinuous elements) that transformational rules handle elegantly.

The paper founded generative linguistics and the Chomsky hierarchy, and established transformational grammar as the preferred formalism for natural-language syntax.

Key Ideas

Finite-state grammars cannot generate English (mirror-image / nested dependencies)
Phrase-structure grammars more powerful but still inadequate for transformations
Transformational grammar operates on phrase markers, not strings
Distinction between grammar as discovery procedure vs. evaluation procedure
Foundations of the Chomsky hierarchy

Connections

Conceptual Contribution

Claim: Natural language (English) is not finitely describable by a finite-state Markov process, nor adequately by a pure phrase-structure grammar; a transformational grammar built on top of phrase structure is materially simpler and exposes genuine linguistic insight.
Mechanism: Three candidate models examined formally — (1) finite-state Markov processes, shown incapable of generating mirror-image / nested-dependency constructions central to English; (2) phrase-structure (context-free) grammars, adequate in principle but producing unwieldy, redundant grammars; (3) transformational grammars, where a kernel of simple sentences plus transformations derives the rest, yielding compact and explanatorily powerful descriptions.
Concepts introduced/used: Finite-state Grammars, Phrase-structure Grammar, Context-Free Grammars, Transformational Grammar, Chomsky Hierarchy, Generative Grammar, Kernel Sentences, Markov Processes, Compositionality
Stance: formal / linguistic-theory
Relates to: Foundational reference point for any discussion of language structure, including emergent-language work (Emergence of Grounded Compositional Language in Multi-Agent Populations, Multi-Agent Cooperation and the Emergence of Natural Language) where “compositionality” is the property Chomsky’s phrase-structure was designed to capture. Complements Algorithmic Information Theory - Grunwald Vitanyi’s description-length view with a structural/syntactic one. Distant ancestor of the parser-design rigour demanded by PKI Layer Cake - Kaminsky Patterson Sassaman.

Tags

KQML Language And Protocol

KQML - A Language and Protocol for Knowledge and Information Exchange

Reference: Finin, Fritzson, McKay, McEntire (1994). AAAI Technical Report WS-94-02 (ARPA Knowledge Sharing Effort). Source file: 741.pdf. URL

Summary

This paper describes the design of the Knowledge Query and Manipulation Language (KQML), an agent communication language developed under the ARPA Knowledge Sharing Effort. KQML is both a message format and a message-handling protocol supporting run-time knowledge sharing among cooperating intelligent agents. Its core contribution is an extensible set of performatives (speech-act-style operations such as tell, ask-if, ask-all, subscribe, advertise, broker, recruit) that define what an agent may do with another agent’s knowledge and goal stores.

KQML is organised as three layers - content, message, and communication - where the message layer carries a performative and metadata while the content layer is treated as opaque (often KIF). The paper introduces facilitators - special agents that coordinate others via content-based routing, brokering, recruiting, and matchmaking - and describes KRILs (KQML Router Interface Libraries) for embedding KQML into Lisp, Prolog, C, and SQL applications.

Key Ideas

Performative-based messaging grounded in speech act theory.
Three-layer architecture: content, message, communication.
Facilitators for content-based routing, brokering, recruiting.
KRILs as embedding libraries for existing systems.
Prototype uses: ARPA Rome Planning Initiative, CAD/CAM, intelligent databases.

Connections

Conceptual Contribution

Claim: Knowledge sharing among heterogeneous intelligent agents is best realised by a layered, performative-based message protocol whose content is opaque and whose routing is mediated by special facilitator agents.
Mechanism: Defines a three-layer architecture (content / message / communication), a set of extensible performatives grounded in Speech Act Theory, facilitators for brokering/recruiting/matchmaking, and KRIL embedding libraries for Lisp/Prolog/C/SQL.
Concepts introduced/used: KQML, Performatives, Facilitators, Content Languages, KIF, Speech Act Theory, Ontologies, Multi-Agent Systems, Agent Communication Languages
Stance: foundational / engineering
Relates to: Direct philosophical descendant of Foundations Of Illocutionary Logic and sibling proposal to Common Business Communication Language; becomes the ancestor that FIPA-ACL, Agent Communication And Institutional Reality, A Common Ontology Of ACLs, and the modern surveys (Survey Of AI Agent Protocols, Survey Of Agent Interoperability Protocols) all build on or critique.

Tags

Facilitators

Mediator agents in KQML that route, broker, and match-make between heterogeneous KBS agents.

In this vault

ACRE Agent Conversation Reasoning Engine

ACRE: Agent Conversation Reasoning Engine

Reference: Lillis & Collier (University College Dublin). Source file: ACRE_Agent_Conversation_Reasoning_Engine.pdf. URL

Summary

ACRE complements existing rule-based agent programming languages (AFAPL2, AgentSpeak, Jason, Jack) with explicit support for modelling, managing, and reasoning about complex multi-message conversations. Rather than handling each FIPA-ACL message individually, ACRE represents conversations as instances of protocols specified as Coloured Petri Nets or Dooley Graphs, so agents can track which performatives are expected next and react accordingly.

The paper integrates ACRE with the Agent Factory framework: conversations are exposed via a conversation-id parameter, and plan pre/postconditions in AFAPL2 reason over BELIEF(status(...)) predicates derived from ACRE. A Vickrey auction example shows how an Auctioneer agent uses ACRE-tracked conversations to issue cfp, collect propose/refuse messages, and broadcast accept-proposal/reject-proposal.

Key Ideas

Protocols are first-class citizens, separate from individual messages.
Conversations tracked via Coloured Petri Nets / Dooley Graphs.
Integration with AFAPL2: conversation state surfaces as beliefs for plan reasoning.
Code verification check that agent plans honour protocol expectations.
Vickrey auction case study using FIPA Contract Net-style interactions.

Connections

Conceptual Contribution

Claim: Agents need conversations, not just messages, as first-class abstractions; existing AOP languages (AgentSpeak, Jason, AFAPL2) lack native protocol reasoning.
Mechanism: Models FIPA-ACL interaction protocols as Coloured Petri Nets / Dooley Graphs instantiated per conversation-id; surfaces conversation state as BELIEF(status(...)) predicates usable in plan pre/postconditions; validated via Vickrey auction (Contract Net).
Concepts introduced/used: Interaction Protocols, Coloured Petri Nets, Dooley Graphs, Conversations, Conversation Policy, FIPA-ACL, Performatives, Contract Net Protocol, BDI, Agent-Oriented Programming, Multi-Agent Systems
Stance: engineering
Relates to: Operationalises the protocol-tracking needs implicit in FIPA-ACL and KQML; its plan-level conversation awareness is an ancestor of task/session tracking in modern Agent-to-Agent Protocol as covered by Survey Of Agent Interoperability Protocols.

Tags

Coordinating Agents Using ACL Conversations

Coordinating Agents using Agent Communication Languages Conversations

Reference: R. Scott Cost, Yannis Labrou, Tim Finin (2000). Springer-Verlag book chapter, March 2000. Source file: Coordinating_Agents_using_Agent_Communication_Lang.pdf. URL

Summary

This chapter argues that ACLs like KQML and FIPA-ACL provide the vocabulary for exchanging propositional attitudes but not the higher-level coordination structures agents need when carrying out task-oriented interactions. The authors advocate conversation protocols — pre-arranged message-exchange patterns — as the missing layer above individual speech acts, giving context for interpretation and enabling agents to expect and verify sequences of messages.

They survey existing approaches (COOL state machines, Dooley Graphs, Push-Down Transducers, DCGs) and propose a formalism based on Colored Petri Nets (CPNs) for specifying conversation protocols. The CPN-based specification enables concurrency modeling, role/participant tracking, and formal verification of properties like liveness and reachability. The approach positions shareable conversation protocol specifications as “abstract agent interfaces” (AAIs).

Key Ideas

ACLs alone do not encode expectations about response sequences; conversation protocols fill that gap.
Conversation = pre-arranged coordination protocol giving pragmatic context to messages.
Colored Petri Nets offer concurrency and verifiability lacking in FSM-based approaches.
Three issues for conversations: specification, sharing, and aggregation into services.
Specialization and composition of conversations, analogous to OO subclassing.

Connections

Conceptual Contribution

Claim: Isolated speech-act messages are insufficient for agent coordination; shareable, verifiable conversation protocols — best specified as Colored Petri Nets — are the appropriate layer above ACL performatives.
Mechanism: Survey of FSM/DFA/DCG conversation models (COOL, Dooley Graphs, ATM, PDTs) and their expressivity limitations; stepwise translation of a KQML Register conversation from JDFA to an equivalent CPN that captures role constraints, concurrency, message ordering, and a negotiation example; argues CPNs enable liveness/reachability verification.
Concepts introduced/used: Conversation Protocols, Colored Petri Nets, Propositional Attitudes, Abstract Agent Interfaces, Conversation Specialization, Conversation Composition, Speech Acts
Stance: engineering / formal-semantic
Relates to: Complements ACRE Agent Conversation Reasoning Engine (runtime reasoning over conversation state) and shares motivation with Verifiable Semantics for ACLs — both insist ACL semantics be externally checkable. Builds on KQML Overview and FIPA-ACL performative sets.

Tags

Interaction Protocols

Specifications of legal conversation patterns (e.g. as Petri nets or state machines) above the message level.

In this vault

Foundations Of Illocutionary Logic

Foundations of Illocutionary Logic

Reference: Searle & Vanderveken (1985). Cambridge University Press. Source file: 5F9BF68C-E1C8-11EE-931A-C444DB61CCB4.pdf. URL

Summary

Searle and Vanderveken construct a formalized logic of speech acts, filling the gap between philosophy of language and formal logic. The book recursively defines the space of illocutionary forces from five primitives (assertive, commissive, directive, declarative, expressive) via seven components of illocutionary force (illocutionary point, mode of achievement, propositional-content conditions, preparatory conditions, sincerity conditions, degree of strength, direction of fit).

It develops axiomatic propositional illocutionary logic, laws of illocutionary entailment, commitment, negation, conjunction, and conditionalization, and closes with a semantic analysis of over a hundred English performative verbs. The work is foundational for agent communication languages because it gives a rigorous semantics to the performatives (inform, request, promise, declare, etc.) later adopted by KQML and FIPA-ACL.

Key Ideas

Five illocutionary points: assertive, commissive, directive, declarative, expressive.
Seven components of illocutionary force.
Direction of fit: word-to-world vs world-to-word.
Formal calculus of success conditions and illocutionary entailment.
Semantic definitions of English performative verbs.

Connections

Conceptual Contribution

Claim: The space of possible speech acts is generated recursively from five illocutionary points and seven components of illocutionary force, and admits a genuine formal logic of success and entailment.
Mechanism: Axiomatic propositional illocutionary logic: laws of illocutionary entailment, commitment, negation, conjunction, and conditionalisation; closes with semantic definitions of over a hundred English performative verbs.
Concepts introduced/used: Speech Act Theory, Performatives, Illocutionary Force, Direction of Fit, Sincerity Conditions, Preparatory Conditions, Commitment-based Semantics, Mental State, Mentalistic Semantics
Stance: foundational / formal-semantic
Relates to: Supplies the philosophical semantics imported by KQML Language And Protocol and FIPA-ACL, and re-examined publicly in Agent Communication And Institutional Reality and A Common Ontology Of ACLs.

Tags

Performatives

Austin/Searle speech-act tags (inform, request, promise, declare, …) that name the illocutionary force of a message.

In this vault

Foundations Of Illocutionary Logic
KQML
FIPA-ACL
Speech Act Theory
CBCL - Safe Self-Extending Agent Communication — eight-performative DCFL-bounded core with formally-safe runtime extension

KIF

Knowledge Interchange Format

First-order-logic-based language (Genesereth) used as a neutral content language for KQML and Ontolingua.

In this vault

Trends in Agent Communication Language

Reference: Chaib-draa, B., Dignum, F. (2002). Computational Intelligence, Vol. 18, No. 2. Source file: trends-in-acl.pdf. URL

Summary

Editorial introduction to a special issue on ACLs that surveys the field’s major research threads. The authors review the origins of ACLs (KSE, KQML/KIF, FIPA-ACL based on ARCOL), situating them as intentional/social layers above transport protocols (TCP/IP, HTTP, IIOP). They highlight five core issues: theories of agency underpinning the semantics, ACL semantics proper (pre-/post-/completion conditions vs. rational effects), verification of compliance and protocols, treatment of ontologies, and completeness of message-type sets.

The paper emphasizes tensions between mentalistic semantics (inherited from Searle/Cohen-Levesque speech-act theory) and social alternatives (Singh), and argues conversation policies/protocols are a primary practical vehicle for tractable agent interaction. It closes by reviewing ad-hoc treatment of ontologies and the limits of KQML and FIPA-ACL message-type coverage (e.g., missing commissives in FIPA-ACL).

Key Ideas

ACLs operate at intentional/social layer above transport.
Mentalistic (FIPA) vs. social (Singh) semantics tension.
Verifiability of sincerity/semantics is largely infeasible.
Conversation policies make ACL use tractable.
Ontology integration remains largely ad-hoc.

Connections

Conceptual Contribution

Claim: ACL research clusters around five persistent issues — theory of agency, ACL semantics, verification, ontologies, and completeness of message-type repertoires — and progress requires reconciling mentalistic and social semantics via practical conversation policies.
Mechanism: Chaib-draa and Dignum trace ACLs from the KSE through KQML/KIF to FIPA-ACL/ARCOL, situating them as an intentional/social layer above TCP/HTTP/IIOP transports, and survey each issue. They highlight Cohen–Levesque rational-effect semantics vs. Singh’s social commitments, argue sincerity verification is generally infeasible, note FIPA-ACL’s missing commissives, and promote conversation policies as the practical tractability lever.
Concepts introduced/used: ACL Layering, Rational Effect, Conversation Policy, Protocol Verification, Commissives, Theory of Agency, Ontology Grounding
Stance: survey
Relates to: A companion to The State of the Art in Agent Communication Languages; summarises the tension sharpened in Agent Communication Languages - Rethinking the Principles and motivates the commitment-based turn realised in An Interaction-oriented Agent Framework for Open Environments; its ontology concern links to Ontology Change Classification and Survey.

Tags

The State of the Art in Agent Communication Languages

Reference: Kone, Shimazu, Nakajima (2000). Knowledge and Information Systems, Springer. Source file: The_State_of_the_Art_in_Agent_Communication_Langua.pdf. URL

Summary

A critical review of ACL design circa 2000. The authors lay out a generalized ACL framework structured around eight principles (heterogeneity, cooperation/coordination, separation, interoperability, transparency, extensibility/scalability, performance, and security). They distill ACL specifications into four components: message format, semantic model, interaction protocols, and shared ontologies/content language.

The paper surveys major ACLs — KQML with KIF and facilitator mediation, France Telecom’s ARCOL with its rational-action semantics, the FIPA standard derived from ARCOL, OAA’s ICL, and mobile-agent LOGOS — documenting each approach’s advantages and limitations (lack of formal semantics, low heterogeneity, missing shared ontologies, weak negotiation protocols). It closes by identifying open issues and pointing to the social-agency approach of Singh as a promising direction.

Key Ideas

Eight ACL design principles as evaluation yardstick.
Four-part ACL spec: format, semantics, protocols, ontology.
KQML vs. ARCOL/FIPA as declarative approaches; OAA/LOGOS as procedural.
Speech-act-derived communicative act categories.
Key open issues: formal semantics, heterogeneity, shared ontologies.

Connections

Conceptual Contribution

Claim: An ACL should be evaluated against eight design principles and factored into four orthogonal components, revealing systematic gaps (formal semantics, heterogeneity, shared ontologies, negotiation) in the ACLs available at the turn of the millennium.
Mechanism: Kone, Shimazu and Nakajima enumerate eight principles (heterogeneity, cooperation/coordination, separation, interoperability, transparency, extensibility/scalability, performance, security) and a four-part ACL template (message format, semantic model, interaction protocols, shared ontology/content language). They apply this lens to KQML+KIF, ARCOL, FIPA-ACL, OAA’s ICL and LOGOS, and close by endorsing Singh’s social-agency direction.
Concepts introduced/used: ACL Design Principles, KQML, KIF, ARCOL, FIPA-ACL, OAA ICL, LOGOS, Rational Action Semantics, Facilitator, Content Language
Stance: survey
Relates to: Sits alongside Trends in Agent Communication Language as a companion turn-of-2000s assessment; its endorsement of social semantics anticipates Agent Communication Languages - Rethinking the Principles and is realised by An Interaction-oriented Agent Framework for Open Environments; references ontology issues surveyed in Ontology Change Classification and Survey.

Tags

Conversation Policy

Constraints on legal sequences of ACL messages — the layer between single performatives and a full protocol.

In this vault

Verifiable Semantics

ACL semantics whose conformance can be checked against observable agent program state — the key demand behind moving from mentalistic to public semantics.

In this vault

Agent Communication Languages - Rethinking the Principles

Agent Communication Languages: Rethinking the Principles

Reference: Singh, M. P. (1998). IEEE Computer (December 1998). Source file: singh-acl.pdf. URL

Summary

Singh argues that mainstream ACLs like KQML and FIPA/Arcol are built on an untenable mentalistic semantics — grounding message meaning in the sender’s beliefs and intentions — which cannot be verified from the outside and therefore cannot serve as a compliance standard. For true interoperability in heterogeneous multi-agent systems, he proposes shifting to a social agency model in which ACL semantics is defined in terms of public commitments, roles, and conventions rather than private mental states.

The paper maps the design space of ACLs along phisssspective (private/public), type of meaning (personal/conventional), basis (semantic/pragmatic), context (fixed/flexible), coverage (of communicative acts), and construction autonomy (design/execution). It motivates “societies” of agents with published protocols, where compliance becomes testable and dialects can usefully coexist. The move from mental to social semantics underpins later work on commitment-based protocols.

Key Ideas

Mentalistic ACL semantics is non-verifiables => poor basis for standards.
Social agency: commitments, roles, conventions as public meaning.
Design/execution autonomy orthogonal and both important.
Dialects are OK; idiolects are not.
Protocols as flexible specifications, not fixed FSMs.

Connections

Agent Communication Languages
FIPA-ACL
FIPA-ACL Specifications
KQML
Speech Act Theory
Commitment-based Semantics
Mentalistic Semantics
Public Semantics
Verifiable Semantics
Interaction Protocols
Conversation Policy
Multi-Agent Systems
Communicative Actions for Artificial Agents - Cohen Levesque — the mentalistic high-water mark this paper critiques
An Ontology for Commitments in Multiagent Systems - Singh — Singh’s own formal sequel: four-place commitment ontology
Articulating Reasons - Brandom — philosophical underwriting of Public Semantics
Making It Explicit - Brandom
Jones-Sergot Normative Systems — Counts-As Relation / institutional grounding
CBCL - Safe Self-Extending Agent Communication — O’Connor 2026 contemporary realisation

Conceptual Contribution

Claim: Mentalistic ACL semantics (KQML, FIPA/ARCOL) cannot ground interoperability because compliance with sincerity and belief conditions is externally unverifiable; ACLs should be rebuilt on a social semantics of public commitments, roles and conventions.
Mechanism: Singh maps the ACL design space along six axes — perspective (private/public), meaning type (personal/conventional), basis (semantic/pragmatic), context (fixed/flexible), coverage (communicative-act repertoire), and construction autonomy (design-time vs. run-time). He uses this scheme to argue that FIPA/KQML occupy an untenable region, and sketches a social-agency alternative in which agents belong to “societies” with published protocols, commitments are first-class, and dialects (but not idiolects) are tolerated.
Concepts introduced/used: Social Agency, Commitment-Based Semantics, Mentalistic Semantics, Conversation Policy, Dialect vs Idiolect, Design Autonomy, Execution Autonomy, ACL Verifiability
Stance: critique
Relates to: Directly targets the mentalistic stance of Agent-Oriented Programming, KQML as an Agent Communication Language, and FIPA-ACL; its social-semantic programme is operationalised by An Interaction-oriented Agent Framework for Open Environments (commitment-based Mercurio/JaCaMo) and cited approvingly by the surveys The State of the Art in Agent Communication Languages and Trends in Agent Communication Language.

Tags

Public Semantics

ACL semantics grounded in externally observable facts (commitments, roles, institutional state) rather than private mental state.

In this vault

ACL Rethinking Principles
Agent Communication And Institutional Reality
Commitment-based Semantics
Mentalistic Semantics
CBCL - Safe Self-Extending Agent Communication — dialect installation as a public commitment

Commitment-based Semantics

Approach that grounds ACL message meaning in public social commitments rather than private mental states — making conformance verifiable.

In this vault

ACL Rethinking Principles
Agent Communication Languages - Rethinking the Principles
Agent Communication And Institutional Reality
A Common Ontology Of ACLs
Public Semantics
Mentalistic Semantics
Flexible Protocol Specification and Execution
A Commitment-Based Approach to Agent Communication
CBCL - Safe Self-Extending Agent Communication — modern LangSec-grounded ACL inheriting Singh’s social-agency programme; dialect installation as public commitment

KQML as an Agent Communication Language

Reference: Tim Finin, Richard Fritzson, Don McKay, and Robin McEntire (1994). CIKM ’94 (Proceedings of the Third International Conference on Information and Knowledge Management). Source file: 191246.191322.pdf. URL

Summary

Foundational paper on the Knowledge Query and Manipulation Language (KQML), developed under the ARPA Knowledge Sharing Effort. KQML is both a message format and a message-handling protocol for run-time knowledge sharing among intelligent agents. It builds on speech-act theory: each message (a performative) carries an illocutionary force (ask, tell, subscribe, advertise, recommend, broker, recruit, etc.) atop a content language (often KIF) and an ontology reference.

The paper describes the three-layer structure (content / message / communication), facilitator agents that provide matchmaking, brokering and content-based routing, and implementations including routers, facilitators, and KRIL interface libraries. KQML became the reference point against which later ACLs (notably FIPA-ACL) were designed.

Key Ideas

Performatives as speech-act-inspired message types
Separation of content language, message layer, and transport
Facilitators for advertise/subscribe, brokering, recruitment, routing
Reserved performatives: ask-if/ask-all, tell, stream-all, subscribe, monitor, advertise, recruit
KIF + ontologies as the assumed content layer

Connections

Conceptual Contribution

Claim: Interoperable knowledge sharing among heterogeneous intelligent agents requires a three-layer communication language (content / message / communication) whose message layer is built from speech-act-inspired performatives, and whose runtime infrastructure provides facilitator agents for matchmaking and brokering.
Mechanism: Specify ~30 reserved performatives (ask-if, tell, subscribe, advertise, recruit, broker-one, …) that wrap a content expression (typically KIF) with an ontology reference and transport metadata; implement via routers, facilitators, and per-application KRIL interface libraries; demonstrate advertise/subscribe, content-based routing, and recruitment patterns.
Concepts introduced/used: KQML, Performatives, Speech Act Theory, Facilitators, Facilitator Agents, Mentalistic Semantics, KIF, Ontologies, Agent Communication Languages, Conversation Policy, Interaction Protocols
Stance: engineering / standard-proposal
Relates to: Foundational reference against which FIPA-ACL, A Common Ontology Of ACLs, ACL Rethinking Principles, and Agent Communication Languages - Rethinking the Principles argue (over mentalistic vs commitment-based semantics). Performatives-as-protocol anticipates Agora’s Protocol Documents in A Scalable Communication Protocol for Networks of LLMs and the MCP/A2A/ANP layer of modern LLM agents (Model Context Protocol, Agent-to-Agent Protocol, Agent Network Protocol).

Tags

Mentalistic Semantics

ACL semantics in which each message commits the sender’s (and sometimes receiver’s) beliefs and intentions — powerful but unverifiable from outside.