If we can achieve consensus, does it imply we can achieve mutual exclusion? Is there a difference?
Example : Paxos solves the consensus problem, can it also be used to solve mutual exclusion?
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.Sign up to join this community
If you have a consensus mechanism, then you can achieve consensus on who owns a critical section, and thus solve mutual exclusion. This is exactly what happens in, say, single-master distributed database systems when they are doing leader election to decide which machine will accept writes (this has to be mutually exclusive).
However, different algorithms for mutual exclusion provide different guarantees of progress in the presence of failures; those that are fully fault-tolerant are essentially equivalent to consensus; those that aren't, are weaker.
The mutual exclusion problem makes sense only when processors are scheduled fairly; otherwise, a processor halting in the critical section blocks the whole system. But, in a model with fair scheduling, both mutual exclusion and consensus are solvable with registers only, so it is not a good model to compare them.
Consensus is a single-use task: everybody proposes and decides a value once. For a meaningful comparison, let us specify mutual exclusion as a single-use task too. In single-use mutual exclusion, a unique processor must enter the critical section once, and that's it. This is equivalent to the test-and-set problem, where a unique processor must declare itself winner whereas all others declare themselves losers.
Now we can compare test-and-set and consensus: test-and-set has consensus power 2, which means that, in the wait-free model, it is strictly weaker than consensus when there are at least 3 processors.