Downloads provided by UsageCounts
Early in the development of Hoare logic, Owicki and Gries introduced auxiliary variables as a way of encoding information about the history of a program’s execution that is useful for verifying its correctness. Over a decade later, Abadi and Lamport observed that it is sometimes also necessary to know in advance what a program will do in the future . To address this need, they proposed prophecy variables , originally as a proof technique for refinement mappings between state machines. However, despite the fact that prophecy variables are a clearly useful reasoning mechanism, there is (surprisingly) almost no work that attempts to integrate them into Hoare logic. In this paper, we present the first account of prophecy variables in a Hoare-style program logic that is flexible enough to verify logical atomicity (a relative of linearizability) for classic examples from the concurrency literature like RDCSS and the Herlihy-Wing queue. Our account is formalized in the Iris framework for separation logic in Coq. It makes essential use of ownership to encode the exclusive right to resolve a prophecy, which in turn enables us to enforce soundness of prophecies with a very simple set of proof rules.
4613 Theory of computation, Separation logic, Technology, linearizability, Science & Technology, separation logic, Iris, LINEARIZABILITY, 4612 Software engineering, Computer Science, Software Engineering, Programming logic, Computer Science, 4903 Numerical and computational mathematics, Operational semantics, Prophecy variables, Theory of computation, logical atomicity
4613 Theory of computation, Separation logic, Technology, linearizability, Science & Technology, separation logic, Iris, LINEARIZABILITY, 4612 Software engineering, Computer Science, Software Engineering, Programming logic, Computer Science, 4903 Numerical and computational mathematics, Operational semantics, Prophecy variables, Theory of computation, logical atomicity
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 45 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
| views | 4 | |
| downloads | 7 |

Views provided by UsageCounts
Downloads provided by UsageCounts