Modal Assertions for Actor Correctness

Gordon, Colin S.

ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and Decentralized Control (AGERE 2019), October 2019, doi: 10.1145/3358499.3361221

Abstract

The actor model is a well-established way to approach to modularly designing and implementing concurrent and/or distributed systems, seeing increasing adoption in industry. But deductive verification tailored to actor programs remains underexplored; general concurrent logics could be used, but the logics are complex and full of features to reason about behaviors the actor model strives to avoid. We explore a relatively lightweight approach of extending a system for proving {sequential} program correctness with means to prove safety properties of distributed actor programs (currently, assuming no faults). We borrow ideas from hybrid logic, a modal logic for stating assertions are true at a particular point in a model (in this case, a particular actor's local state). To make such assertions useful, we stabilize them using rely-guarantee-style reasoning over local actor states, and only permit sending stable versions of these assertions to other actors. By carefully restricting the formation of assertions that a proposition is true at a certain actor, we avoid the need for actors to handle each others' rely-guarantee relations explicitly. We find that almost all of the required restrictions either fall out of established reference immutability techniques or can be implemented as a Dafny library, and outline the minor additional extensions that would be required for a sound implementation. We use this library to verify an actor variant of a classic rely-guarantee example (lower-bounding a montonic counter).

Bibtex

@inproceedings{agere19,
  abbr = {AGERE},
  title = {{Modal Assertions for Actor Correctness}},
  bibtex_show = {true},
  author = {Gordon, Colin S.},
  booktitle = {{ACM SIGPLAN International Workshop on Programming Based on Actors, Agents, and
      Decentralized Control (AGERE 2019)}},
  address = {Athens, Greece},
  month = {October},
  year = 2019,
  doi = {10.1145/3358499.3361221},
  code = {https://gist.github.com/csgordon/b9173c2b28099e8353c36eb19c058691},
  acm = {https://dl.acm.org/citation.cfm?id=3361221},
  pdf = {papers/agere19corrected.pdf},
  abstract={
The actor model is a well-established way to approach to modularly designing and implementing concurrent and/or distributed systems, seeing increasing adoption in industry.
But deductive verification tailored to actor programs remains underexplored; general concurrent logics could be used, but the logics are complex and full of features to reason about behaviors the actor model strives to avoid.

We explore a relatively lightweight approach of extending a system for proving {sequential} program correctness with means to prove safety properties of distributed actor programs (currently, assuming no faults).
We borrow ideas from hybrid logic, a modal logic for stating assertions are true at a particular point in a model (in this case, a particular actor's local state).  To make such assertions useful, we stabilize them using rely-guarantee-style reasoning over local actor states, and only permit sending stable versions of these assertions to other actors.
By carefully restricting the formation of assertions that a proposition is true at a certain actor, we avoid the need for actors to handle each others' rely-guarantee relations explicitly.

We find that almost all of the required restrictions either fall out of established reference immutability techniques or can be implemented as a Dafny library, and outline the minor additional extensions that would be required for a sound implementation.
We use this library to verify an actor variant of a classic rely-guarantee example (lower-bounding a montonic counter).
  }
}