Changes in distributed-system runtime support in response to changes in technological and operational circumstances may also change the services offered to supported systems. The graph-based semantics comparison workbench described in this paper determines how runtime support changes may affect supported distributed systems. The workbench is easy to establish and flexible over a wide range of changes, providing an intuitive interpretation of both the system under analysis and potential behavioral changes.

Graphs model system abstractions. Rewrite rules specify subgraph matches and, if matching occurs, transformations to reconfigure the graph. Other rules can detect deadlock or other safety-property violations. Graph and rule modules help generate various system models and execution behaviors, and parameters help generate variation within a system. The graph-based model is refined into a toolchain to demonstrate the principles involved as well as their practicality.

As a benchmark, the workbench analyzed several programs written in a message-based distributed object-oriented system. Under analysis, runtime systems differing in execution models reveal behavioral changes resulting in deadlock and other inconsistencies in program execution. Analysis data presented suggest modest increases in, and efficient traversal of, state spaces.

There is much going on in this paper, and much of it is somewhat esoteric, particularly graph-based concurrency analysis. The paper is self-contained, but that’s not as helpful as it might seem. The writing is good, but there is a lot of it, and some is not as finely woven as it could be. The bibliography has a good selection of background material, as well as the more expected references.