Langshaw: Declarative Interaction Protocols Based on Sayso and Conflict

Munindar P. Singh, Samuel H. Christie V., Amit K. ChopraIJCAI 2024

Abstract: Langshaw is a novel declarative language for multiagent systems (MAS) that simplifies protocol specification by focusing on social authority and conflict rather than low-level message ordering. By bridging the gap between synchronous human reasoning and asynchronous network reality, Langshaw enables the creation of robust, provably correct protocols for decentralized environments.

Introduction

In decentralized multiagent systems—such as independent software agents representing different companies in a supply chain—coordination is notoriously difficult. Traditionally, developers rely on "message-oriented" protocols. However, these suffer from two major flaws: state explosion, where specifying every possible message order becomes unmanageably complex, and the meaning gap, where messages lack the inherent "social" meaning of an action (e.g., who has the authority to set a price).

Presented at IJCAI-24, Langshaw (named after speech-act philosopher J.L. Austin) addresses these issues by allowing developers to specify protocols using a simple synchronous mental model, which is then automatically compiled into a provably correct asynchronous messaging protocol.

The Langshaw Language: Sayso, Nono, and Nogo

Langshaw shifts the focus from timing to authority and mutual exclusion. The language relies on three core primitives:

  • sayso: Defines which agent has the authority to bind a value to an attribute. If multiple agents attempt to set the same value, sayso determines priority.
  • nono: Specifies mutual exclusion. Actions in a nono relationship cannot both occur in the same transaction.
  • nogo: Specifies asymmetric prevention. If action A occurs, action B is subsequently prevented.
The Purchase protocol in Langshaw, illustrating the core primitives for social authority and conflict management.

By embracing the idea that "saying makes it so," Langshaw allows agents to act concurrently. The system handles potential conflicts by ignoring lower-priority attempts as defined by the social state, rather than strictly enforcing message sequences.

Technical Pipeline: Verification and Compilation

To ensure reliability, the Langshaw framework includes a robust technical pipeline:

  1. Formal Semantics: The authors use semantic tableaux (a tree-based proof method) to represent all possible social states of a protocol. To avoid exponential state explosion, they developed a "reduced tableau" method that consolidates redundant branches.
  2. Verification: Algorithms check for Safety (ensuring no nono conflicts occur) and Liveness (ensuring the protocol can reach completion).
  3. Compilation: Langshaw is compiled into BSPL (Blindingly Simple Protocol Language), an existing framework for asynchronous messaging. This bridges the gap by turning high-level social constraints into low-level message dependencies.
Compiled BSPL-style rules derived from the Langshaw specification.

Key Results and Performance

The paper evaluates Langshaw using benchmark interaction protocols like Purchase, Refund, and Rescind. The results demonstrate both efficiency and correctness:

  • Efficiency: The verifier is highly performant. It checked liveness for a standard Purchase protocol in just 480.1 ms, while simpler protocols were verified in as little as 1.5 ms.
  • Reliability: The tool successfully identified flaws in "Unsafe" and "Nonlive" versions of protocols, such as cases where a buyer could both accept and reject a quote.
  • Compiler Correctness: The authors proved that any enactment of the compiled asynchronous protocol has a corresponding valid synchronous enactment in Langshaw, allowing developers to "think synchronous" but "deploy asynchronous" safely.

Conclusion

Langshaw provides a powerful abstraction for MAS developers, moving the focus from low-level networking concerns to high-level social logic. While future work may extend the language to model complex constructs like commitments or sanctions, Langshaw already offers a significant step forward in making decentralized coordination manageable and provably secure.

Summary updated

BibTeX
@inproceedings{singh2024langshaw,
  author = {Munindar P. Singh and Samuel H. Christie V. and Amit K. Chopra},
  title = {{Langshaw: Declarative Interaction Protocols Based on Sayso and Conflict}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure