Various progress properties have been proposed for concurrent objects, such as wait-freedom, lock-freedom, starvation-freedom and deadlock-freedom. However, none of them apply for concurrent objects with partial methods, i.e. methods that are supposed not to return under certain circumstances. A typical example is the lock_acquire method.
In this paper we propose two new progress properties, partial starvation-freedom (PSF) and partial deadlockfreedom (PDF), for concurrent objects with partial methods. We also design four patterns to write abstract specifications for PSF or PDF objects under strongly or weakly fair scheduling, so that these objects contextually refine the abstract specifications. Our Abstraction Theorem shows the equivalence between PSF (or PDF) and the progress-aware contextual refinement. Finally, we generalize the program logic LiLi to have a new logic to verify the PSF or PDF property and linearizability of concurrent objects.
Conference DayWed 10 JanDisplayed time zone: Tijuana, Baja California change
15:50 - 17:30
|Effective Stateless Model Checking for C/C++ Concurrency|
|Transactions in Relaxed Memory Architectures|
Brijesh DongolBrunel University London, Radha JagadeesanDePaul University, James RielyDePaul UniversityLink to publication DOI Pre-print Media Attached
|Simplifying ARM Concurrency: Multicopy-Atomic Axiomatic and Operational Models for ARMv8|
|Progress of Concurrent Objects with Partial Methods|