A GENERAL SCHEME FOR TOKEN-BASED AND TREE-BASED DISTRIBUTED MUTUAL EXCLUSION ALGORITHMS

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