What is the consensus number for semaphores?

Question

(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_*)?

Answer 1

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 its 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.

Answer 2

The answer depends on the supported operations on the mutex or the semaphore. If only blocking locks are supported, the consensus number is 1. If a thread can try to lock the mutex without waiting, the consensus number is 2. That is because if there are two threads, both can try to lock the mutex, both can agree which one got it, so there is consensus. If the mutex can additionally determine, for any number of threads, which thread has locked it, then the consensus number is infinite. I think the situation for semaphores is similar. Mutexes are equivalent to semaphores with the counter 1. I don't think consensus can be reached just with larger counters, it still comes down to the same operations. Pthreads supports non-blocking locks but not queries, so there the answer would be 2.

Signaling a condition variable does nothing if any threads are not waiting for it, so they have consensus number 1.

Answer 3

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.

Answer 4

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