💻 computer science

Langshaw: Declarative Interaction Protocols Based on Sayso and Conflict

This paper introduces Langshaw, a declarative protocol language that utilizes "sayso," "nono," and "nogo" constructs to balance flexibility and semantic clarity in multiagent interactions, while providing formal semantics, safety/liveness verification, and methods for generating asynchronous message-oriented protocols.

Original authors: Munindar P. Singh, Samuel H. Christie V, Amit K. Chopra

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Munindar P. Singh, Samuel H. Christie V, Amit K. Chopra

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a group of friends trying to organize a surprise party. They need to agree on the guest list, the budget, the food, and the location. In the world of computer science, these friends are "agents" (software programs), and the party plan is a "protocol."

The paper introduces a new way to write these party plans, called Langshaw. The authors argue that current ways of writing these plans are either too rigid (like a strict script where you can't improvise) or too messy (hard to understand what everyone is actually trying to say).

Here is how Langshaw works, explained through simple analogies:

1. The Core Problem: Who Decides What?

In a normal conversation, if two people try to decide the same thing at the same time, it gets chaotic.

The Old Way: Most computer languages try to stop this by forcing everyone to wait their turn (synchronous) or by making the rules so complex that it's hard to know who is allowed to do what.
The Langshaw Way: Langshaw accepts that people (agents) might try to do things at the same time. Instead of stopping them, it uses two special tools to manage the chaos: Sayso and Conflict.

2. The Magic Tools

Sayso: The "Who Has the Final Word" Rule

Imagine the friends are arguing about the menu.

The Concept: Langshaw introduces a construct called Sayso. This is like a pre-agreed rule that says, "When it comes to the food, the Chef has the final say. When it comes to the music, the DJ has the final say."
How it works: If the Chef and the DJ both try to change the menu at the exact same time, the system checks the "Sayso" list. Since the Chef has "Sayso" over food, the Chef's choice wins, and the DJ's attempt is ignored. This prevents a messy argument without needing a referee to stop the conversation.

Nogo and Nono: The "Do Not Mix" Rules

Sometimes, two actions just can't happen together, like trying to "Cancel the party" and "Send the invitations" at the same time.

Nogo (Stop Sign): This is a one-way rule. "If you Cancel the party, you cannot Send the invitations." It's like a traffic light: if the light is red (Cancel), you can't go (Send).
Nono (Mutual Exclusion): This is a two-way rule. "You cannot Cancel the party AND Send the invitations." They are mutually exclusive. You have to pick one path.

3. The "Social Artifact": The Shared Whiteboard

Langshaw imagines the group's interaction happening on a giant, shared Social Whiteboard.

Every time someone does something (like "Buyer sends a quote"), it gets written on the board.
The rules (Sayso and Conflicts) ensure that even if everyone writes on the board at the same time, the final picture on the board makes sense.
Safety: The system checks if the board ends up in a broken state (e.g., "Party Cancelled" and "Party Happening" written next to each other). Langshaw's rules prevent this.
Liveness: The system checks if the party actually gets finished. It ensures the group doesn't get stuck in an endless loop of arguing without ever sending an invitation.

4. From "Perfect Timing" to "Real Life"

The paper does something clever with time:

The Ideal World (Synchronous): First, the authors write the rules assuming everyone is in the same room, talking instantly. This makes it easy to check if the rules are logical and safe.
The Real World (Asynchronous): Then, they use a "compiler" (a translator tool) to turn those perfect, instant rules into a format that works on the real internet, where messages get delayed, lost, or arrive out of order.
- Analogy: It's like writing a perfect script for a play where actors speak instantly. Then, the director translates that script into a series of text messages and emails that the actors can send from different cities, ensuring the story still makes sense even if the emails arrive late.

5. Why This Matters

The authors built a tool (a "verifier") that can look at a Langshaw protocol and instantly tell you:

"This plan is safe; no one will accidentally break the rules."
"This plan is live; the process will actually finish."
"Here is the code you need to run this on the real internet."

They tested this on several examples (like a "Purchase" protocol for buying items) and found that their tool is fast and accurate.

Summary

Langshaw is a new language for designing how computer programs talk to each other. Instead of forcing them to take turns or writing confusing code, it uses Sayso (priority rules) and Conflict (do-not-mix rules) to let them work together freely. It starts with a simple, perfect model and then translates it into a format that works on the messy, slow internet, ensuring that even when things happen at the same time, the result is always correct.

Technical Summary: Langshaw – Declarative Interaction Protocols Based on Sayso and Conflict

1. Problem Statement

In decentralized multiagent systems (MAS), agents must interact in a loosely coupled manner to achieve interoperation. Current languages for specifying these protocols face a fundamental trade-off: they either over-constrain protocol enactments (limiting flexibility) or complicate the capture of meaning (making reasoning difficult).

Traditional message-based modeling is problematic for two reasons:

Low-level complexity: Messages are the smallest operational units, leading to an explosion in possible message orders and coordination complexity.
Mapping issues: There is often no natural mapping between specific messages and their underlying social or mental meanings.

Existing approaches often mix information content with coordination logic (e.g., BSPL, HAPN) or rely on external "synchronizers" (infrastructure-level entities) to resolve conflicts arbitrarily, which fails to capture the social nature of agent interactions.

2. Methodology: The Langshaw Language

The authors propose Langshaw, a declarative protocol language inspired by Austin's speech act theory ("saying makes it so"). Langshaw separates communicative actions from both messages and meanings, modeling interactions directly through social actions.

Core Constructs

Langshaw introduces three novel primitives to manage information and coordination:

Sayso (Priority): A construct capturing who has priority over setting specific attributes.
- Agents can attempt to bind attributes. If multiple agents attempt to bind the same attribute, the agent with the higher-ranked sayso succeeds; others fail (become no-ops).
- This allows for flexible, concurrent attempts while ensuring a consistent social state through prioritized authority rather than arbitrary infrastructure ordering.
Nono (Mutual Exclusion): A construct capturing pairwise conflicts between actions.
- If two actions have a nono constraint, they are mutually exclusive for the same bindings. This prevents inconsistent social states (e.g., an agent cannot both "Accept" and "Reject" the same order).
Nogo (Asymmetric Blocking): A construct capturing asymmetric conflicts.
- If action $A$ has a nogo over action $B$ , the occurrence of $A$ prevents $B$ from being performed, even if they are attempted concurrently or in different orders.

Syntax and Semantics

Syntax: Protocols define roles, attributes (with keys), social actions (performed by roles), sayso rankings, nono pairs, and nogo constraints.
Formal Semantics: The paper provides a synchronous semantics framed as inference rules (semantic tableaux).
- The system state is a set of performed actions.
- Transitions occur via jointly feasible sets of concurrent actions.
- Feasibility is determined by sayso dominance (resolving conflicts), adherence to nono/nogo constraints, and consistency with existing social state bindings.
- This synchronous model simplifies specification and reasoning while acknowledging that real-world MAS often operate asynchronously.

3. Key Contributions

A. Formal Language and Verification

The authors introduce Langshaw and provide:

Formal Semantics: A rigorous definition of protocol enactment based on social state updates.
Decision Procedures: Efficient algorithms to verify safety (absence of integrity violations) and liveness (guarantee of completion).
- Safety is verified by checking that no branch in the semantic tableau contains conflicting actions (e.g., a nono violation).
- Liveness is verified by ensuring that every possible enactment path leads to a state where completion criteria (specific attributes) are bound.

B. Bridging Synchronous and Asynchronous Worlds

A major contribution is the compilation of Langshaw protocols into asynchronous message-oriented protocols (specifically BSPL - Blindingly Simple Protocol Language).

The Gap: Synchronous semantics are easier to reason about, but real MAS run on asynchronous infrastructures (like the Internet).
The Solution: The authors present a compiler that translates Langshaw's high-level declarative rules into BSPL messages.
- Sayso is modeled via delegation (e.g., a lower-priority agent must receive a delegation message from a higher-priority agent to bind an attribute).
- Nono/Nogo constraints are modeled using nil parameters (blocking parameters) that prevent message transmission until specific conditions are met.
Correctness: The paper proves that any asynchronous enactment produced by the compiled BSPL protocol corresponds to a valid synchronous enactment in the original Langshaw semantics.

C. Optimization (Tableau Reduction)

To address the potential exponential explosion of the semantic tableau, the authors propose a reduction technique:

They identify interference (actions that block or delay others) and group non-interfering actions.
Using graph coloring approximations, they consolidate branches to cover all semantically distinct possibilities without enumerating every interleaving, ensuring tractable verification.

4. Results

The authors implemented a verifier in Python and tested it on several protocols from the literature (e.g., Purchase, Refund, RFQ-Quote).

Performance: The verifier successfully checked liveness and safety for various protocols in milliseconds (e.g., 480ms for the "Purchase" protocol).
Scalability: The reduction technique effectively managed the state space, with node and branch counts remaining manageable even for complex protocols.
Validation: The compiler successfully generated BSPL protocols that respected the original Langshaw constraints, demonstrating the feasibility of the synchronous-to-asynchronous translation.

5. Significance and Claims

The paper claims significance in the following areas:

Social Abstraction: Langshaw forces designers to think of coordination in social terms (authority, conflict, meaning) rather than low-level message ordering. This aligns with the "saying makes it so" doctrine, making protocols more intuitive for stakeholders.
Flexibility vs. Correctness: By using sayso to resolve conflicts socially rather than via arbitrary infrastructure synchronizers, Langshaw supports maximal concurrency while maintaining protocol correctness. It allows agents to attempt actions concurrently, with the system resolving conflicts based on declared priorities.
Bridging the Gap: The work demonstrates that a synchronous semantics can serve as a viable pathway to asynchronous enactment. This bypasses the traditional debate between synchrony and asynchrony by showing that high-level synchronous specifications can be rigorously compiled into robust asynchronous implementations.
Engineering Utility: The approach offers a method to realize implemented MAS by capturing stakeholder intuitions and translating them into executable code (via BSPL), addressing the gap between semiformal notations (like AUML) and engineering goals.

The authors conclude that while native programming models for Langshaw are needed, the current best approach is to verify a Langshaw protocol, compile it to BSPL, and execute it using existing BSPL programming models (e.g., Kiko).