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.
Wed 10 Jan
|15:50 - 16:15|
|16:15 - 16:40|
Brijesh DongolBrunel University London, Radha JagadeesanDePaul University, James RielyDePaul UniversityLink to publication DOI Pre-print Media Attached
|16:40 - 17:05|
|17:05 - 17:30|