A general scheme for token- and tree-based distributed mutual exclusion algorithms

摘要

In a distributed context, mutual exclusion algorithms can be divided into two families according to their underlying algorithmic principles: those that are permission-based and those that are token-based. Within the latter family, a lot of algorithms use a rooted tree structure to move the requests and the unique token. This paper presents a very general information structure (and the associated generic algorithm) for token- and tree-based mutual exclusion algorithms. This general structure not only covers, as particular cases, several known algorithms, but also allows for the design of new ones that are well suited for various topology requirements.