Search papers, labs, and topics across Lattice.
This paper formalizes the concept of bounded bypass in mutual exclusion protocols, addressing its previous ambiguities and proposing two new liveness properties: post-doorway and intermittent bounded bypass. The authors demonstrate that a 1998 algorithm by Yoah Bar-David can enhance any deadlock-free MUTEX protocol to satisfy bounded bypass with a quadratic bound in the number of processes, while also ensuring the intermittent version under specific conditions. Through model checking, they validate their definitions and claims, correcting prior errors in the literature.
Bounded bypass can be achieved in any deadlock-free MUTEX protocol with a quadratic improvement, reshaping our understanding of liveness properties in concurrent systems.
In the literature on mutual exclusion, bounded bypass has been used for a long time as a strengthening of starvation-freedom, but, to the best of our knowledge, it still lacks a satisfying definition as a liveness property on its own. Moreover, we have encountered MUTEX protocols for which this notion needs to be slightly weakened in order to be met. To solve these issues, we first provide a formal definition of bounded bypass (that also corrects a previous definition from Raynal) and then introduce the notions of post-doorway and intermittent bounded bypass, two liveness properties that lie between starvation-freedom and bounded bypass. Essentially, intermittent bounded bypass weakens bounded bypass by ignoring the possible bypasses that may happen during the execution of a certain finite set of write operations to shared registers. Orthogonally, post-doorway bounded bypass ignores the bypasses that may happen during a finite initial phase of the lock protocol. Furthermore, we study an algorithm proposed by Yoah Bar-David in 1998 to enhance the liveness properties of any deadlock-free MUTEX protocol and prove that: (1) in the setting of atomic registers, this algorithm upgrades any deadlock-free mutual exclusion protocol to a bounded bypass one, with a bound that is quadratic in the number of processes; and (2) in the setting of safe and regular registers, the very same algorithm ensures the intermittent version of bounded bypass, still with a quadratic (but slightly different) bound. Finally, we provide logical formulae for the different notions of bounded bypass defined in this paper and use them to confirm all claims made here, by using model checking. This had a positive impact on the theoretical development of the work, since it allowed us to identify and correct small mistakes/ambiguities in definitions and proofs.
