Y. Afek, H. Attiya, D. Dolev, E. Gafni, M. Merritt et al., Atomic snapshots of shared memory, Journal of the ACM, vol.40, issue.4, pp.873-890, 1993.
DOI : 10.1145/153724.153741

Y. Afek, E. Gafni, and . Lieber, Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus, Proc. 23rd Int'l Symposium on Distributed Computing (DISC'09), Springer LNCS #5805, pp.111-126, 2009.
DOI : 10.1007/978-3-642-04355-0_14

Y. Afek, E. Gafni, S. Rajsbaum, M. Raynal, and C. Travers, The k-simultaneous consensus problem, Distributed Computing, vol.29, issue.5, pp.185-195, 2010.
DOI : 10.1007/s00446-009-0090-8
URL : https://hal.archives-ouvertes.fr/inria-00354248

D. Angluin, Local and Global Properties in Networks of Processors, Proc. 12th ACM Symposium on Theory of Computing (STOC'80, pp.82-93, 1980.

H. Attiya, A. Bar-noy, D. Dolev, D. Peleg, and R. Reischuck, Renaming in an asynchronous environment, Journal of the ACM, vol.37, issue.3, pp.524-548, 1990.
DOI : 10.1145/79147.79158

H. Attiya and A. Fouren, Polynomial and Adaptive Long-lived (2p ? 1)-Renaming, Proc. 14th Int'l Symposium on Distributed Computing (DISC'00), Springer LNCS #1914, pp.149-163, 2000.
DOI : 10.1007/3-540-40026-5_10

H. Attiya, A. Gorbach, and S. Moran, Computing in Totally Anonymous Asynchronous Shared Memory Systems, Information and Computation, vol.173, issue.2, pp.162-183, 2002.
DOI : 10.1006/inco.2001.3119

H. Attiya and S. Rajsbaum, The Combinatorial Structure of Wait-Free Solvable Tasks, SIAM Journal on Computing, vol.31, issue.4, pp.1286-1313, 2002.
DOI : 10.1137/S0097539797330689

H. Attiya and A. Paz, Counting-Based Impossibility Proofs for Renaming and Set Agreement, Proc. 26th Int'l Symposium on Distributed Computing (DISC'12), Springer LNCS #7611, pp.356-370, 2012.

H. Attiya and J. Welch, Distributed Computing: Fundamentals, Simulations and Advanced Topics, p.414, 2004.
DOI : 10.1002/0471478210

M. Armoni and M. Ben-ari, The concept of nondeterminism, ACM SIGCSE Bulletin, vol.41, issue.2, pp.141-160, 2009.
DOI : 10.1145/1595453.1595495

E. Borowsky and E. Gafni, -resilient asynchronous computations, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , STOC '93, pp.91-100, 1993.
DOI : 10.1145/167088.167119
URL : https://hal.archives-ouvertes.fr/hal-00896459

E. Borowsky and E. Gafni, A simple algorithmically reasoned characterization of wait-free computation (extended abstract), Proceedings of the sixteenth annual ACM symposium on Principles of distributed computing , PODC '97, pp.189-198, 1997.
DOI : 10.1145/259380.259439

A. Castañeda, A Study of the Wait-free Solvability of Weak Symmetry Breaking and Renaming, Posgrado en Ciencia e Ingeniería de la Computación, 2010.

A. Castañeda and S. Rajsbaum, New combinatorial topology upper and lower bounds for renaming, Proceedings of the twenty-seventh ACM symposium on Principles of distributed computing, PODC '08, pp.295-304, 2008.
DOI : 10.1145/1400751.1400791

A. Castañeda, S. Rajsbaum, and M. Raynal, The renaming problem in shared memory systems: An introduction, Computer Science Review, vol.5, issue.3, pp.229-251, 2011.
DOI : 10.1016/j.cosrev.2011.04.001

A. Castañeda, S. Rajsbaum, and M. Raynal, Agreement via Symmetry Breaking: On the Structure of Weak Subconsensus Tasks, 2013 IEEE 27th International Symposium on Parallel and Distributed Processing, pp.1147-1158, 2013.
DOI : 10.1109/IPDPS.2013.41

A. Castañeda, D. Imbs, S. Rajsbaum, and M. Raynal, Renaming Is Weaker Than Set Agreement But for Perfect Renaming: A Map of Sub-consensus Tasks, Proc. 10th Latin American Theoretical INformatics Symposium, pp.145-156, 2012.
DOI : 10.1007/978-3-642-29344-3_13

S. Chaudhuri, More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems, Information and Computation, vol.105, issue.1, pp.132-158, 1993.
DOI : 10.1006/inco.1993.1043

S. Chaudhuri, R. , and P. , Understanding the Set Consensus Partial Order Using the Borowsky-Gafni Simulation (Extended Abstract), 10th Int'l Workshop on Distributed Algorithms (WDAG'96), Springer LNCS #1171, pp.362-379, 1996.

T. Chandra and S. Toueg, Unreliable failure detectors for reliable distributed systems, Journal of the ACM, vol.43, issue.2, pp.225-267, 1996.
DOI : 10.1145/226643.226647

E. W. Dijkstra, Solution of a problem in concurrent programming control, Communications of the ACM, vol.8, issue.9, p.569, 1965.
DOI : 10.1145/365559.365617

D. Dolev, N. Lynch, S. Pinter, E. Stark, and W. Weihl, Reaching approximate agreement in the presence of faults, Journal of the ACM, vol.33, issue.3, pp.499-516, 1986.
DOI : 10.1145/5925.5931

Y. Dinitz, S. Moran, and S. Rajsbaum, Bit complexity of breaking and achieving symmetry in chains and rings, Journal of the ACM, vol.55, issue.1, 2008.
DOI : 10.1145/1326554.1326557

M. J. Fischer, N. A. Lynch, and M. S. Paterson, Impossibility of distributed consensus with one faulty process, Journal of the ACM, vol.32, issue.2, pp.374-382, 1985.
DOI : 10.1145/3149.214121

E. Gafni, Renaming with k-Set-Consensus: An Optimal Algorithm into n + k ??? 1 Slots, Proc. 10th Int'l Conference On Principles Of Distributed Systems (OPODIS'06), Springer LNCS #4305, pp.36-44, 2006.
DOI : 10.1007/11945529_4

E. Gafni, The 01-Exclusion Families of Tasks, Proc. 12th Int'l Conference on Principles of Distributed Systems (OPODIS'08), Springer LNCS #5401, pp.246-258, 2008.

E. Gafni and P. Kuznetsov, On set consensus numbers, Distributed Computing, vol.20, issue.5, pp.149-163, 2011.
DOI : 10.1007/s00446-011-0142-8

E. Gafni and S. Rajsbaum, Distributed Programming with Tasks, Proc. 10th Int'l Conference on Principles of Distributed Systems (OPODIS'10), Springer LNCS #6490, pp.205-218, 2010.
DOI : 10.1137/S0097539796307698

E. Gafni, S. Rajsbaum, and M. Herlihy, Subconsensus Tasks: Renaming Is Weaker Than Set Agreement, Proc. 20th Int'l Symposium on Distributed Computing (DISC'06), Springer LNCS #4167, pp.329-338, 2006.
DOI : 10.1007/11864219_23

E. Gafni, S. Rajsbaum, M. Raynal, and C. Travers, The Committee Decision Problem, Proc. Latin American Theoretical Informatics Symposium (LATIN'06). Springer LNCS #3887, pp.502-514, 2006.
DOI : 10.1007/11682462_47
URL : https://hal.archives-ouvertes.fr/inria-00000290

E. Gafni, M. Raynal, C. Travers, and . Test&set, From adaptive renaming to set agreement, Proc. 26th Int'l IEEE Symposium on Reliable Distributed Systems, pp.93-103, 2007.
DOI : 10.1016/j.tcs.2008.05.016
URL : https://hal.archives-ouvertes.fr/hal-00432970

E. Gafni, M. Mostéfaoui, M. Raynal, and T. C. , From adaptive renaming to set agreement, Theoretical Computer Science, vol.410, issue.14, pp.14-151328, 2009.
DOI : 10.1016/j.tcs.2008.05.016
URL : https://hal.archives-ouvertes.fr/hal-00432970

M. Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems, vol.13, issue.1, pp.124-149, 1991.
DOI : 10.1145/114005.102808

M. P. Herlihy and S. Rajsbaum, Set consensus using arbitrary objects (preliminary version), Proceedings of the thirteenth annual ACM symposium on Principles of distributed computing , PODC '94, pp.324-333, 1994.
DOI : 10.1145/197917.198119

M. Herlihy and S. Rajsbaum, On the decidability of distributed decision tasks, Proceedings of the fifteenth annual ACM symposium on Principles of distributed computing , PODC '96, pp.589-598, 1997.
DOI : 10.1145/248052.248110

M. P. Herlihy and S. Rajsbaum, A classification of wait-free loop agreement tasks, Theoretical Computer Science, vol.291, issue.1, pp.55-77, 2003.
DOI : 10.1016/S0304-3975(01)00396-6

M. P. Herlihy and N. Shavit, The topological structure of asynchronous computability, Journal of the ACM, vol.46, issue.6, pp.858-923, 1999.
DOI : 10.1145/331524.331529

D. Imbs, S. Rajsbaum, and M. Raynal, The Universe of Symmetry Breaking Tasks, Proc. 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO'11), Springer LNCS #6796, pp.66-77, 2011.
URL : https://hal.archives-ouvertes.fr/inria-00560453

L. Lamport, A fast mutual exclusion algorithm, ACM Transactions on Computer Systems, vol.5, issue.1, pp.1-11, 1987.
DOI : 10.1145/7351.7352

. L. Lamport, The part-time parliament, ACM Transactions on Computer Systems, vol.16, issue.2, pp.133-169, 1998.
DOI : 10.1145/279227.279229

N. A. Lynch, Distributed Algorithms, 1996.

M. Moir and J. Anderson, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, vol.25, issue.1, pp.1-39, 1995.
DOI : 10.1016/0167-6423(95)00009-H
URL : http://doi.org/10.1016/0167-6423(95)00009-h

M. Mostéfaoui, M. Raynal, and T. C. , Exploring Gafni???s Reduction Land: From ?? k to Wait-Free Adaptive $(2p-\lceil\frac{p}{k}\rceil)$ -Renaming Via k-Set Agreement, Proc. 20th Int'l Symposium on Distributed Computing (DISC'09)
DOI : 10.1007/11864219_1

S. Moran and Y. Wolfsthal, Extended impossibility results for asynchronous complete networks, Information Processing Letters, vol.26, issue.3, pp.141-151, 1987.
DOI : 10.1016/0020-0190(87)90052-4

M. Raynal, Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems, Synthesis Lectures on Distributed Computing Theory, vol.1, issue.1, 2010.
DOI : 10.2200/S00236ED1V01Y201004DCT002
URL : https://hal.archives-ouvertes.fr/inria-00543036

M. Raynal, Concurrent Programming: Algorithms, Principles, and Foundations, p.2012
DOI : 10.1007/978-3-642-32027-9
URL : https://hal.archives-ouvertes.fr/hal-00922217

E. Styer and G. L. Peterson, Tight bounds for shared memory symmetric mutual exclusion problems, Proceedings of the eighth annual ACM Symposium on Principles of distributed computing , PODC '89, pp.177-192, 1989.
DOI : 10.1145/72981.72993

M. Saks and F. Zaharoglou, -set agreement is impossible, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing , STOC '93, pp.1449-1483, 2000.
DOI : 10.1145/167088.167122
URL : https://hal.archives-ouvertes.fr/hal-00192526

?. Consider-an-n,-n, 1, x + 1]-GSB object X in A. In B, X is replaced with the read/writebased wait-free function f(·) in Figure 9. #a X and SP X [1, .., x + 1] are associated with the instance of f(·) function that replaces X . #a X is a constant indicating the number of times object X has been invoked at the end of E, hence 0 ? #a X ? n ? (x + 1). And SP X [1, .., x + 1] is an (x + 1)-dimensional shared array, which contains a splitter object (explained below) in each of its entries. A splitter is a wait-free concurrent object that provides processes with a single operation