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.