CARMA: Collective Adaptive Resource-sharing Markovian Agents

Luca Bortolussi, Rocco De Nicola, Vashti Galpin, Stephen Gilmore, Jane Hillston, Diego Latella, Michele Loreti, Mieke Massink

Introduction

In our increasingly connected world, we are surrounded by Collective Adaptive Systems (CAS)—massive networks of heterogeneous agents like smart power grids, robot swarms, or city-wide bike-sharing programs. These systems are "open," meaning agents join and leave constantly, and "adaptive," as agents change behavior based on their surroundings.

The primary challenge in engineering these systems is their inherent unpredictability. Traditional modeling tools often fail to capture how a single agent's local attributes—such as a drone's battery level or a bike station's GPS coordinates—influence the behavior of the entire collective. To address this, researchers have introduced CARMA (Collective Adaptive Resource-sharing Markovian Agents), a new formal language designed specifically to specify and analyze these complex systems.

The CARMA Framework

CARMA is a stochastic process algebra that allows researchers to model massive groups of interacting agents using attribute-based communication. By treating the environment as a dynamic participant that can evolve and modulate agent interactions, CARMA provides a rigorous framework for the quantitative analysis of "smart" collective systems.

Key Innovations

  • The Store ($\gamma$): Every agent possesses a local set of attributes (e.g., location, status, or resource_count) that define its state.
  • Predicate-Based Communication: Instead of fixed addresses or ports, CARMA uses logical predicates ($\pi$). A broadcast message is only received by agents whose attributes satisfy the sender's conditions. This mirrors real-world scenarios where a device might seek "any available printer within range."
  • The Environment ($\mathcal{E}$): Unlike older models where the environment is static, a CARMA system is defined as a "Collective in an Environment." The environment has its own global store and evolution rules that change based on agent actions.
  • FUTS Semantics: The researchers utilized Functional Unlabelled Transition Systems (FUTS) to define the language's operational semantics. This mathematical framework allows for the calculation of action rates and state probabilities more compactly than traditional methods.

Modeling Dynamics and Communication

CARMA supports both unicast (point-to-point, blocking) and broadcast (one-to-many, non-blocking) communication. This flexibility allows for realistic modeling of various networking protocols.

A significant technical insight in the paper involves the renormalization of rates. CARMA ensures that the total rate of a broadcast is determined by the sender, preventing the number of potential receivers from artificially inflating the system's speed. Furthermore, the authors demonstrate how "spontaneous" internal actions (like a user deciding to walk) can be modeled as a broadcast to a "false" predicate ($\perp$), ensuring the action occurs without requiring synchronization from others.

Case Study: Urban Bike-Sharing

As a theoretical paper, the authors evaluated CARMA using a synthetic case study of a bike-sharing system. The scenario involved a city divided into zones, each containing parking stations with specific bike and slot capacities. The simulation tracked 150 users (bikers and pedestrians) moving between zones.

Results

Using a prototype simulator, the authors demonstrated that CARMA could effectively:

  • Track the minimum, maximum, and average number of bikes per station over time.
  • Capture "race conditions," such as multiple bikers arriving at the last empty slot simultaneously.
  • Represent complex socio-technical patterns, such as incentive-based rebalancing, which are difficult to express in older stochastic algebras.

Future Outlook

While CARMA is mathematically powerful, the current "discrete" semantics—which track every individual agent—face scalability limitations when dealing with millions of agents. The authors' next step is developing fluid approximation (continuous semantics). This would allow the behavior of massive collectives to be approximated using ordinary differential equations (ODEs), similar to fluid dynamics models.

Additionally, because CARMA is a "low-level" formal language, future work will focus on creating higher-level, more intuitive interfaces for system designers that can be compiled into CARMA for rigorous analysis.

Summary updated

BibTeX
@inproceedings{bortolussi2015carma,
  author = {Luca Bortolussi and Rocco De Nicola and Vashti Galpin and Stephen Gilmore and Jane Hillston and Diego Latella and Michele Loreti and Mieke Massink},
  title = {{CARMA: Collective Adaptive Resource-sharing Markovian Agents}},
  booktitle = {QAPL},
  year = {2015},
  url = {https://openreview.net/forum?id=PXoLl23cNg0},
}
Figure