A New Hybrid Mutual Exclusion Algorithm in the Absence of Majority Consensus

摘要

All the voting-based mutual exclusion (ME) algorithms that work on majority consensus inherently confirm safety criterion. However, such algorithms may violate progress condition when no single process gets majority of votes. In this paper, a new two-phase, hybrid ME algorithm is proposed that works even when majority consensus cannot be reached. Simulation results establish that the proposed algorithm offers lower message and time complexity as compared to established as well as recent algorithms. The second phase of the algorithm, in spite of being symmetric, executes in constant time.