A note on group mutual exclusion

摘要

Group mutual exclusion is a natural problem, formulated by Joung in 1998, that generalises the classical mutual exclusion problem. In group mutual exclusion a process requests a "session" before entering its critical section; processes are allowed to be in the critical section simultaneously provided they have requested the same session. To rule out solutions that cause processes to delay each other even when they all request the same session, group mutual exclusion algorithms must satisfy a property called "concurrent entering". Joung stated this property only informally. Keane and Moir later gave a precise statement of this property and devised a simple group mutual exclusion algorithm that satisfies it.

We argue that Keane and Moir's formulation is not quite as strong as the property Joung described informally. We propose a new precise and simple formulation of concurrent entering that is stronger than Keane and Moir's and properly captures Joung's intention. Keane and Moir's algorithmdoes not satisfy this stronger property, while Joung's original algorithm does. We present another algorithm that satisfies this stronger property and has some advantages over Joung's.