Model Checking Distributed Systems against Temporal-Epistemic Specifications

Andreas Griesmayer, Alessio Lomuscio

Abstract

Verifying distributed systems is a complex challenge due to the inherent state-explosion problem and the need to reason about the internal knowledge of individual components. This paper introduces a novel framework that enables formal verification of "temporal-epistemic" properties in distributed systems. By developing the ABSMC compiler, which translates models from the Abstract Behavioral Specification (ABS) language into the MCMAS model checker, the authors provide a pathway to verify what individual agents "know" about the system state over time, particularly in systems utilizing asynchronous "futures."

Introduction

Distributed systems are notoriously difficult to verify because the number of possible message orderings and internal states grows exponentially with the number of components. Traditional model checking typically focuses on safety ("nothing bad happens") and liveness ("something good eventually happens"). However, in many distributed environments—such as secure communication protocols or autonomous multi-agent systems—it is equally important to reason about knowledge. For instance, a protocol might require that a server knows a client's request is authentic before processing it.

While the ABS modeling language is well-suited for describing distributed objects and asynchronous communication, it previously lacked the tools to verify these epistemic properties. Conversely, specialized epistemic model checkers like MCMAS were not designed to handle high-level distributed programming constructs directly.

The ABSMC Framework

The authors address this gap with ABSMC (ABS Model Checker), a tool that automates the translation from a bounded subset of ABS (referred to as $ABS_B$) to the Interpreted Systems Programming Language (ISPL), the input format for the MCMAS model checker.

Language Mapping and Modeling

The translation process involves several key mappings:

  • Objects to Agents: Each distributed object in the ABS model is represented as an "Agent" within the interpreted system.
  • The Environment as a Buffer: To account for asynchronous message passing and potential reordering, the network is modeled as a specialized "Environment Agent" that functions as a bounded message buffer.
  • Handling Futures: The logic of "futures"—placeholders for asynchronous return values—is implemented by tracking message indices within the environment buffer.
Figure 2: The ABSMC tool maps high-level ABS code (left) to a formal state transition model (right) suitable for epistemic verification.

As illustrated in the mapping of the RREQ function in Figure 2, the tool converts executable code into a state transition graph. This allows the system to leverage symbolic model checking using Binary Decision Diagrams (BDDs) to represent the state space efficiently, enabling the verification of formulas in Temporal-Epistemic logic (CTL + Knowledge operators).

Case Study: The AODV Protocol

The methodology was evaluated using the AODV (Ad-hoc On-Demand Distance Vector) routing protocol. The protocol was modeled in ABS and tested across four network topologies of varying complexity: linear (AODV3), triangular (AODV$\Delta$), diamond (AODV$\diamond$), and mesh (AODV$\infty$).

The study revealed that epistemic logic serves as a powerful debugging tool. It allows developers to verify the intent of a protocol—for example, ensuring that a node not only has a route but also "knows" the route is valid. A key insight was that agents can often deduce the state of distant nodes by observing their own local state and incoming messages, even without direct communication.

Results and Performance

The authors successfully verified several critical properties of the AODV protocol, including:

  • Liveness: Ensuring that a node eventually discovers a route to its destination (e.g., AF r1S).
  • Epistemic Correctness: Verifying properties such as AG (r12S -> K(N1, r2S)), which states that if Node 1 has a route to S via Node 2, then Node 1 knows that Node 2 possesses a route to S.

In terms of performance, the most complex topology (AODV$\infty$) was verified in approximately 2,262 seconds using 351MB of RAM. The results indicated that the density of network connections (the number of edges) impacts state-space complexity more significantly than the raw number of nodes, due to the increased number of possible message interleavings.

Conclusion and Future Work

The ABSMC framework provides a robust method for verifying complex distributed systems against sophisticated temporal-epistemic specifications. While the current approach requires manual bounding of process numbers and buffer sizes, it demonstrates the feasibility of automated epistemic verification for high-level distributed code. Future work will focus on developing automatic estimation techniques for these bounds and exploring abstraction methods to handle even larger systems and infinite data types.

Summary updated

Abstract

Concurrency and message reordering are two main causes for the state-explosion in distributed systems with asynchronous communication. We study this domain by analysing ABS, an executable modelling language for object-based distributed systems and present a symbolic model checking methodology for verifying ABS programs against temporal-epistemic specifications. Specifically, we show how to map an ABS program into an ISPL program for verification with MCMAS, a model checker for multi-agent systems. We present a compiler implementing the formal map, exemplify the methodology on a mesh network use case and report experimental results.
BibTeX
@inproceedings{griesmayer2013model,
  author = {Andreas Griesmayer and Alessio Lomuscio},
  title = {{Model Checking Distributed Systems against Temporal-Epistemic Specifications}},
  booktitle = {FMOODS/FORTE},
  year = {2013},
  doi = {10.1007/978-3-642-38592-6\_10},
}
Figure