A Study of the Electrum and DynAlloy Dynamic Behavior Notations

Abstract

Alloy is a formal specification language, which despite featuring a simple syntax and relational semantics, is very expressive and supports efficient automated specification analysis, based on SAT solving. While the language is sufficiently expressive to accommodate both static and dynamic properties of systems within specifications, the latter kind of properties require intricate, ad-hoc, constructions to encode system executions. Thus, extensions to the language have been proposed, that internalize these encodings and provide analysis techniques, specifically tailored to properties of executions. In this paper we study two particular extensions to Alloy that incorporate elements for the specification of properties of executions. These are DynAlloy, whose syntax and semantics are inspired by dynamic logic, and Electrum, based on linear-time temporal logic and inspired by languages such as TLA+. We analyze and compare the syntactic characteristics of the languages, their corresponding expressiveness, and the effectiveness and efficiency of their associated analysis tools. The comparison is based on a set of Alloy specifications that are taken from the literature and demand dynamic behavior analysis, including an Alloy model of the Chord ring-maintenance protocol, that drives our qualitative comparison of the notations.