Understanding the Set Consensus Partial Order using the Borowsky-Gafni Simulation

We present a complete characterization of the Set Consensus Partial Order, a refinement of the Consensus Hierarchy of Herlihy. We define the (n, k) -set consensus problem as the k-set consensus problem for n processors. We then answer the question of whether an (n, k)-set consensus object (an object which solves the (n, k)-set consensus problem) can be implemented using a combination of (m, l)-set consensus objects and snapshot objects, for all possible values of n, k, m,l, creating a partial order of set consensus objects. The model we consider is the asynchronous shared memory model.