- An object that allows n threads to propose() n values.
- It guarantees Each thread will decide() on a (single) value.
- The cardinal number of the set of all values decided on is lower or equal to k.
- All values decided on were proposed.
It is obviously trivial if n <= k so the first interesting case is SetAgree(3, 2).
Consensus(n) is the same as SetAgree(n, 1). A consensus number of an object is the highest number of threads that can arrive at a consensus using that object and shared memory access.
Alright, I'll start by saying I think the consensus number of SetAgree(3, 2) is not two.
My line of proof is that I assume there is a protocol that solves a binary consensus(2) using the strongest SetAgree(infinity, 2).
At some point in the algorithm (which has to be deterministic) we arrive at a node where if thread A acts, the consensus will be its proposal (without loss of generality 1) and if thread B acts, it will be its proposal (without loss of generality 0).
Lets say, both of them wish to access the SetAgree object at this node, they could get the values they proposed no matter the order of access they use so the state of the system will be the same (no matter the order). If only one of them accesses the object and the other one reads or writes to a memory register then the order is meaningless for sure simply because memory doesn't affect the SetAgree object and SetAgree doesn't affect any of the shared memory registers. So obviously regardless of the order, the state of the system will be the same after these two operations which means, it is not possible that one leads a consensus on (1) and the other on (0).
The line of proof that suggests consensus number 2 states (the known fact) that setAgree(3, 2) cannot be build with shared memory alone. This is well known but it doesn't suggest setAgree(3, 2) has a stronger consensus number cause that line of proof only applies to data structures, cause it relies on universal construction.
Is there any stronger proof that it's consensus number 1 or 2?