CARMA: Collective Adaptive Resource-sharing Markovian Agents

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

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" (agents join and leave constantly) and "adaptive" (agents change behavior based on their surroundings).

The challenge? They are incredibly hard to model and predict. Traditional tools often fail to capture how a single agent's local attributes—like a drone's battery level or a bike station's GPS coordinates—influence the behavior of the entire collective.

In this paper, a team of researchers introduces CARMA (Collective Adaptive Resource-sharing Markovian Agents), a new formal language designed specifically to specify and analyze these complex systems.

TL;DR

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.

What Problem Does This Paper Address?

Designing and engineering CAS is a headache because they operate in unpredictable, open-ended environments. Most existing modeling languages (like standard process algebras) rely on fixed communication channels or ports.

However, in a collective system, an agent doesn't usually talk to a specific "Port A"; it talks to "any agent within 500 meters that has a spare battery." This is attribute-based communication. Furthermore, the environment itself (e.g., weather, network congestion) often dictates how fast or successfully these agents can interact. The authors identified a gap: we needed a language that combines stochastic timing (to measure performance) with flexible, attribute-driven logic.

Methods

The authors developed CARMA by building on previous languages like SCEL and PALOMA, but with several key innovations:

  • The Store ($\gamma$): Every agent has a "store"—a local set of attributes (like location, status, or resource_count).
  • Predicate-Based Communication: Instead of fixed addresses, CARMA uses logical predicates ($\pi$). A broadcast message is only received by agents whose attributes satisfy the sender's conditions.
  • 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 can have its own global store and "evolution rules" that change based on what the agents are doing.
  • FUTS Semantics: The researchers used Functional Unlabelled Transition Systems (FUTS) to define the language's operational semantics. This mathematical framework allows them to calculate the rates of actions and the probability of different system states in a way that is more compact than traditional methods.
  • Unicast vs. Broadcast: CARMA supports both point-to-point (blocking) and one-to-many (non-blocking) communication, allowing for realistic modeling of different networking protocols.

Datasets

As a theoretical paper introducing a new formal language, it does not use a pre-existing empirical dataset. Instead, the authors evaluate CARMA using a synthetic case study of a bike-sharing system.

  • Scenario: A city divided into zones, each containing parking stations with a set number of bikes and slots.
  • Agents: 150 users (bikers and pedestrians) and multiple parking stations.
  • Goal: Simulate how users moving between zones and picking up/dropping off bikes affects the global distribution of resources.

Key Insights and Ideas

  • Environment as a First-Class Citizen: One of the "aha" moments is that the environment doesn't just provide context; it modulates the rates of actions. For example, if a zone is overcrowded, the environment can mathematically lower the probability of a successful "bike return" action.
  • Modeling Spontaneous Actions: The authors show a clever trick: "spontaneous" or internal actions (like a user deciding to start walking) can be modeled as a broadcast to a "false" predicate ($\perp$). This means the action happens, but no other agent is capable of synchronizing with it.
  • Renormalization of Rates: A major technical insight involves how to calculate the rate of broadcast synchronizations. CARMA ensures that the total rate of a broadcast is determined by the senders, ensuring that the number of potential receivers doesn't artificially inflate the speed of the system.

Key Results

The paper successfully formalizes the CARMA syntax and its discrete operational semantics.

  • Simulation Success: Using a prototype simulator, the authors demonstrated that CARMA could track the minimum, maximum, and average number of bikes per station over time in their bike-sharing scenario.
  • Qualitative Power: The model effectively captured the "race conditions" inherent in CAS—for instance, two bikers arriving at the last empty slot at the same time.
  • Linguistic Richness: The authors proved that CARMA can represent complex socio-technical patterns (like incentive-based rebalancing of bikes) that are difficult to express in older stochastic algebras.

Limitations and Future Work

  • The Scalability Wall: The current "discrete" semantics (tracking every individual agent) becomes computationally impossible when dealing with millions of agents.
  • Fluid Approximation: The authors acknowledge this and state that their next step is developing differential (continuous) semantics. This would allow them to approximate the behavior of millions of agents using ordinary differential equations (ODEs), similar to how fluid dynamics models individual molecules.
  • User Accessibility: While mathematically powerful, CARMA is currently a "low-level" language. The authors suggest the need for a higher-level, more intuitive language for system designers that can then be "compiled" down into CARMA for 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},
}

Loading related content...

Figure