2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Is Paxos used to solve mutual exclusion too? Which mutual exclusion algorithms do modern distributed systems use? $\endgroup$ – Nitish Upreti Oct 4 '14 at 17:25
  • 1
    $\begingroup$ It depends on the requirements for your mutual exclusion protocol. I'm pretty sure that as they approach the requirements of consensus protocols (e.g. fault tolerance and progress), you start needing a consensus protocol :) (I'd appreciate if an expert confirmed that though) But it doesn't have to be Paxos, other protocols exist, e.g. Raft. If you're ok with non-guaranteed progress in favor of performance or simplicity, you can use weaker mutual exclusion protocols. $\endgroup$ – jkff Oct 4 '14 at 17:39
  • $\begingroup$ Thanks a lot for mentioning Raft. This looks super interesting. I am taking a graduate Distributed systems course and strugggling as there is hardly any visible correlation between theory and practice. I had asked a similar question previously and did not receive any response : cs.stackexchange.com/questions/30246/… $\endgroup$ – Nitish Upreti Oct 4 '14 at 19:17
  • $\begingroup$ "those (mutual exclusion) that are fully fault-tolerant are essentially equivalent to consensus": I am curious about this. Could you please give me some references? Or can you argue for it? In my opinion, mutual exclusion is strictly weaker than consensus. Here is an indirect argument: We can solve $n$-process mutual exclusion using just SWMR safe registers, however it is impossible to solve even $n>2$-process consensus using atomic registers. What do you think of it? $\endgroup$ – hengxin Mar 24 '15 at 7:56
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.