(I think that) the consensus number for a mutex is 2.
What is the consensus number for semaphores (like in pthread_sem_*)?
What is the consensus number for condition variables (like in pthread_cond_*)?
A:
Infinite, surely? But they're not wait free.
Perhaps I'm misunderstanding. You say a mutex has a consensus number of 2 - what's your source for that? It's designed to allow any number of threads to share a resource, with the trade-off of blocking.
Atomic test-and-set has a consensus number of 2, but doesn't block.
To clarify: semaphores, mutexes, etc. are primitives that you can simply wrap around a shared resource to make it safe (as long as you do it correctly). They may block, but they will guarantee your data is safe.
The paper you cite is about the primitives needed to protect data without blocking, which is hard. The same primitives may be useful for locks as well, but that's just a nice extra.
Mark
2009-04-21 16:07:44
Helltone
2009-04-22 09:48:51
So the "minimum" consensus number of a mutex is 2. What is the "minimum" consensus number of a semaphore ?
Helltone
2009-04-22 12:28:22
But that implementation of a mutex won't be wait-free. You'll spin on the TAS instruction.
Mark
2009-04-22 12:31:40
(sorry, accidentally deleted that comment)
Mark
2009-04-22 12:32:20
I must confess, I've only skim-read the paper, but it's about analysing wait-free synchronisation. I don't think consensus number is really relevant to anything that blocks.
Mark
2009-04-22 12:40:21
If you want to know more about the cases that dictate different implementations of synchronisation, take a look at http://en.wikipedia.org/wiki/Peterson%27s_algorithm and its "See also" articles
Mark
2009-04-22 12:50:31
A:
From this article alone you can conclude that a semaphore must have a consensus number less than or equal to 2. Here's why:
On the third page of the article they state: "The fetch&add operation is quite flexible: it can be used for semaphores...". Since we know that fetch&add has consensus number equal to 2, Theorem 1 of that paper can then be used to show that a semaphore must have consensus number less than or equal to 2. The proof goes like this:
Proof
Assume that a wait-free implementation of semaphores by fetch&add exists. Further assume that a semaphore has consensus number greater than 2. We know that fetch&add has a consensus number of 2. From Theorem 1 we can conclude that there exists no wait-free implementation of a semaphore by fetch&add in a system of more than 2 processes. This contradicts the assumption that an implementation by fetch&add exists. Therefore, a semaphore must have a consensus number less than or equal to 2.
QED
Waylon Flinn
2009-04-21 20:29:04
Hmm.. I'm pretty sure you cannot implement semaphores with mutexes, you also need condition variables or some other way to atomically unlock a mutex and enter a queue.
Helltone
2009-04-22 09:45:11
The last step doesn't follow. I could implement a mutex with compare-and-exchange. Does that make it infinite? Or I could implement a mutex with just a set, which would only be safe for one process. The point of the paper is to investigate non-blocking primitives, which a mutex is not.
Mark
2009-04-22 12:29:00
Waylon Flinn
2009-04-22 13:22:40
+1
A:
The consensus number for a mutex would be 1. It's trivially clear that a mutex will be wait-free for a single thread. From it's definition, it's also clear that a mutex is no longer wait-free for two threads. The consensus number therefore is >=1 and <2, so it must be 1.
Likewise, other synchronization mechanisms that work by halting one thread in favor of another also have consensus number 1, and therefore cannot be used to construct a wait-free object shared by 2 threads.
MSalters
2009-04-22 13:22:06