Fair Operational Semantics
Dongjae Lee, Minki Cho, Jinwoo Kim, Soonwon Moon, Youngju Song, Chung-Kil Hur
Abstract
Fairness properties, which state that a sequence of bad events cannot happen infinitely before a good event takes place, are often crucial in program verification. However, general methods for expressing and reasoning about various kinds of fairness properties are relatively underdeveloped compared to those for safety properties. This paper proposes FOS (Fair Operational Semantics), a theory capable of expressing arbitrary notions of fairness as an operational semantics and reasoning about these notions of fairness. In addition, FOS enables thread-local reasoning about fairness by providing thread-local simulation relations equipped with separation- logic-style resource algebras. We verify a ticket lock implementation and a client of the ticket lock under weak memory concurrency as an example, which requires reasoning about different notions of fairness including fairness of a scheduler, fairness of the ticket lock implementation, and even fairness of weak memory. The theory of FOS, as well as the examples in the paper, are fully formalized in Coq.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
5 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Nola: Later-Free Ghost State for Verifying Termination in Iris cites Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness
- Nola: Later-Free Ghost State for Verifying Termination in Iris cites Conditional Contextual Refinement
- Nola: Later-Free Ghost State for Verifying Termination in Iris cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Lawyer: Modular Obligations-Based Liveness Reasoning in Higher-Order Impredicative Concurrent Separation Logic cites Nola: Later-Free Ghost State for Verifying Termination in Iris
- Lawyer: Modular Obligations-Based Liveness Reasoning in Higher-Order Impredicative Concurrent Separation Logic cites Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness
- Lawyer: Modular Obligations-Based Liveness Reasoning in Higher-Order Impredicative Concurrent Separation Logic cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Structural Temporal Logic for Mechanized Program Verification cites Interaction trees: representing recursive and impure programs in Coq
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness cites Conditional Contextual Refinement
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for Liveness cites Stuttering for Free
- Conditional Contextual Refinement cites Interaction trees: representing recursive and impure programs in Coq
- Conditional Contextual Refinement cites Simuliris: a separation logic framework for verifying concurrent program optimizations
- Simuliris: a separation logic framework for verifying concurrent program optimizations cites Interaction trees: representing recursive and impure programs in Coq
- Stuttering for Free cites Conditional Contextual Refinement
- Stuttering for Free cites Interaction trees: representing recursive and impure programs in Coq
- Stuttering for Free cites Simuliris: a separation logic framework for verifying concurrent program optimizations
Cited by top-tier papers5
- Stuttering for FreeMinki Cho, Youngju Song, Dongjae Lee, Lennard Gäher et al.OOPSLA 2023 · 11 citations
- Lilo: A Higher-Order, Relational Concurrent Separation Logic for LivenessDongjae Lee, Janggun Lee, Taeyoung Yoon, Minki Cho et al.OOPSLA 2025 · 3 citations
- Nola: Later-Free Ghost State for Verifying Termination in IrisYusuke Matsushita, Takeshi TsukadaPLDI 2025 · 2 citations
- Structural Temporal Logic for Mechanized Program VerificationEleftherios Ioannidis, Yannick Zakowski, Steve Zdancewic, Sebastian AngelOOPSLA 2025 · 1 citation
- Lawyer: Modular Obligations-Based Liveness Reasoning in Higher-Order Impredicative Concurrent Separation LogicEgor Namakonov, Justus Fasse, Bart Jacobs, Lars Birkedal et al.OOPSLA 2026
Builds on6
- Interaction trees: representing recursive and impure programs in CoqLi-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur et al.POPL 2020 · 133 citations
- Promising 2.0: global optimizations in relaxed memory concurrencySung-Hwan Lee, Minki Cho, Anton Podkopaev, Soham Chakraborty et al.PLDI 2020 · 48 citations
- Simuliris: a separation logic framework for verifying concurrent program optimizationsLennard Gäher, Michael Sammler, Simon Spies, Ralf Jung et al.POPL 2022 · 33 citations
- Conditional Contextual RefinementYoungju Song, Minki Cho, Dongjae Lee, Chung-Kil Hur et al.POPL 2023 · 29 citations
- Making weak memory models fairOri Lahav, Egor Namakonov, Jonas Oberhauser, Anton Podkopaev et al.OOPSLA 2021 · 21 citations
Related papers
- Overcoming Memory Weakness with Unified Fairness - Systematic Verification of Liveness in Weak Memory ModelsParosh Aziz Abdulla, Mohamed Faouzi Atig, Adwait Godbole, Shankaranarayanan Krishna et al.CAV 2023 · 9 citations
- Towards Proving Liveness on Weak MemoryLara Bargmann, Heike WehrheimFM 2026
- Verifying optimizations of concurrent programs in the promising semanticsJunpeng Zha, Hongjin Liang, Xinyu FengPLDI 2022 · 5 citations
- Decidable verification under a causally consistent shared memoryOri Lahav, Udi BokerPLDI 2020 · 30 citations
- Unifying Weak Memory Verification Using PotentialsLara Bargmann, Brijesh Dongol, Heike WehrheimFM 2024 · 2 citations
