Rodolphe Lepigre
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Research Interests
Rodolphe Lepigre has a total of 6 co-authors. Here are the top co-authors by number of shared publications:
- Amin Timany
Aarhus University, Denmark
1 shared publication - Bart Jacobs
KU Leuven, Leuven, Belgium
1 shared publication - Derek Dreyer
MPI-SWS, Saarland Informatics Campus, Germany
1 shared publication - Gaurav Parthasarathy
ETH Zurich, Zurich, Switzerland
1 shared publication - Marianna Rapoport
University of Waterloo Waterloo Canada
1 shared publication - Ralf Jung
ETH Zurich, Zurich, Switzerland
1 shared publication
Latest Publications
- Open Access
- 20 December 2019
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 4 (POPL) , 1-32
The future is ours: prophecy variables in separation logic
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.
- 20 December 2019
- Published by Association for Computing Machinery (ACM) in Proceedings of the ACM on Programming Languages
- Vol. 4 (POPL) , 1-32
Open AccessThe future is ours: prophecy variables in separation logic
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.