A Generalized Mutual Exclusion Problem and Its Algorithm
Aoxueluo, Weigang Wu, Jiannong Cao, Michel Raynal · 2013
Mutual exclusion (ME) is a fundamental problem for resource allocation in distributed systems, It is concerned with how the various processes access shared resources in a mutually exclusive way. Besides the classic ME problem, several variant problems have been proposed and studied. In this paper, drawing inspiration from the scenario of controlling autonomous vehicles at intersections, we have defined a new ME problem, called Local Group Mutual Exclusion (LGME), w here mutual exclusion is necessary only among the processes requesting overlap but not the same set of resources. In comparison with other variant problems of ME, LGME is more general but also more challenging. To solve the LGME problem, we propose a novel notion called strong coterie, which can handle the complex process relationship in LGME. Based on strong coterie, we have designed an ME algorithm, which can handle concurrent CS execution and message asynchrony. The correctness of our algorithm is rigorously proved.