A generalized mutual exclusion problem and its algorithm

Aoxue Luo, Wu Weigang, Jiannong Cao, Michel Raynal

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

6 Citations (Scopus)

Abstract

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.
Original languageEnglish
Title of host publicationProceedings
Subtitle of host publicationInternational Conference on Parallel Processing - The 42nd Annual Conference, ICPP 2013
PublisherIEEE
Pages300-309
Number of pages10
ISBN (Print)9780769551173
DOIs
Publication statusPublished - 1 Jan 2013
Event42nd Annual International Conference on Parallel Processing, ICPP 2013 - Lyon, France
Duration: 1 Oct 20134 Oct 2013

Conference

Conference42nd Annual International Conference on Parallel Processing, ICPP 2013
Country/TerritoryFrance
CityLyon
Period1/10/134/10/13

Keywords

  • Coterie
  • Distributed algorithm
  • Mutual exclusion
  • Quorum
  • Resource allocation

ASJC Scopus subject areas

  • Software
  • Mathematics(all)
  • Hardware and Architecture

Cite this