Is the consensus number of SetAgree(3, 2) 2 or 1 (proof needed)?

Question

SetAgree(n, k)

---

• 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?

Answer 1

We can prove that 2-set-consensus among 3 processors (noted (3,2)) cannot be used (together with registers) to solve consensus among 2 processors (noted (2,1)) using the Borowsky-Gafni simulation (BG simulation for short).

The BG simulation allows 3 processors using registers only to simulate any algorithm in which 2 processors use registers and (3,2). Therefore, the BG simulation transforms an algorithm A solving consensus among 2 processors using (3,2) into an algorithm B solving consensus among 3 processors using registers only. Since the latter is impossible, there is no such algorithm A.

Note that by solving I mean solving wait-free.

This proof first appeared in Borowsky and Gafni, "Generalized FLP impossibility result for t-resilient asynchronous computations." Proceedings of the twenty-fifth annual ACM symposium on Theory of computing. ACM, 1993. (In particular see the end of section 3.3).