Consensus Value

Question

while reading on concurrent programming, I came across the term Consensus Number in Compare-And-Swap & Compare-And-Set operations. I'm having trouble in understanding what is meant by this term, can anyone explain??

Thank You!!

Answer 1

Consensus problem is like this... You have N processes. Every thread gets to propose a value, then the threads should decide on one and the same of these proposed values.

Example for two threads: Thread A suggests value A, thread B suggests value B. Then the valid outcomes are that either both threads decide A, or that both threads decide B.

There are different special objects or operations that are useful in solving the consensus problem. Their powerfulness is graded by their consensus number. This equals the maximum number of threads for which they can solve the consensus problem.

• Consensus number 1: Normal read/write registers. (That is, plain variables.)
• Consensus number 2: Test & set (a.k.a. compare & set), queue, stack et.c.
• Consensus number 2n-2: n-register assignment
• Consensus number ∞: Compare & swap, et.c.