Two system components (sites) are assumed. Each of them includes a particular (critical) state. The two sites must synchronize such that they always are able to eventually go critical, but never are coincidently in their respective critical state.
The mutual exclusion problem is the problem of constructing algorithms achieving the two mentioned requirements.
Figure MU1. Contentious mutex
Our first solution is the contentious mutex algorithm.
This algorithm meets both requirements of mutual exclusion and evolution.
The local state key, however, cannot be associated uniquely with one of the sites. Both compete for key and moreover repeated conflict for key must be resolved fairly for both sites. Hence, additional global means are necessary to install proper management of key nondeterminism.
Furthermore, as the algorithm neglects locality of fairness for both b1 and b2, the algorithm cannot be implemented distributedly.
Our next algorithm is similar to MU1 but instead of competing the sites alternate in going critical.