, of IS runs on the left and the set of all IS runs represented as a simplicial complex on the right

, Preliminaries 2.1 Examples of valid sets of IS outputs, Chapter

, 60 4.3 Integration of adversary families, active resilience and collection of set-consensus objects inside a representation of agreement function classes, Agreement Functions 4.1 Relations between agreement function properties, p.64

, First and second iteration of the 2-dimensionnal barycentric subdivision of s. . 68 5.2 Second iteration of the 2-dimensionnal standard chromatic subdivision of s, Combinatorial Topology 5.1, p.69

, 74 6.2 3-processes affine tasks R 1?T &S and R 2?T &S with their facets displayed in blue, Affine Tasks 6.1, p.79

, 3-processes system, of all 2-contention simplices in Chr 2 s and some detailed IS runs, vol.87

, Facets of R 1 and R 2 in blue on top of the edges, in black, of Chr 2 s, p.88

, Critical simplices are displayed in orange (with p 2 the top vertex, p 1 the bottom left vertex and p 3 the bottom right vertex)

, Simplices in black, orange and green are mapped to concurrency levels of 0, 1 and 2 respectively (with p 2 the top vertex, p 1 the bottom left vertex and p 3 the bottom right vertex)

, Some examples of affine tasks R A in blue (with p 2 the top vertex, p 1 the bottom left vertex and p 3 the bottom right vertex)

, A view of 8 registers and processes with couples of independantly covered registers by processes p 1, Stable Storage in Comparison-Based Models

, A possible covering of r 1 , r 2 , r 3 and r 5 induced by the couples of independantly covered registers from Figure 7.1

, Graph representation of processes {p 5

.. .. , 119 7.5 Extended confusion from Figure 7.3 by making p 5 indistinguishably cover r 4 or r 6

, Covering registers outside of the covering with all but one of the confused processes

, Addition of an alternative covering of the same size and for the same processes

, Two possible extensions of confusion size, either with initial or alternative confusions

}. .. , 139 8.2 Second and third iterations of the affine task characterizing the 3-proces testand-set model, First and second iteration of the candidate affine task for the wake-up adversarial model with participation equal to {p 1, vol.1

.. .. , 21 2.2 Simulation of the AS memory in the IIS model for p i, Preliminaries 2.1 Level-based immediate snapshot implementation for p

.. .. , 30 3.4 Commit-abort object: algorithm for process i, Distributed Simulations 3.1 Shared memory simulation for simulator

, Abortable memory simulation for simulator s i

B. .. Abortable, 37 3.7 Round-based simulation for simulator s i

. .. Dispatcher-for-process-p-i, 45 3.10 Adaptive set-consensus for t-resilient systems (for process p i ), p.48

, Agreement Functions Chapter

.. .. Solving-r-k?t-&s, 80 6.2 Solution to R k in the n-processes (k + 1)-active-resilient model for process p i . . 88 6.3 Resolution of R A in the ?-model for process p i

. .. , 112 7.2 (n ? t)-lock-free t-resilient SWMR memory using t + 1 registers, Stable Storage in Comparison-Based Models 7.1 k-lock-free SWMR implementation using n + k ? 1 MWMR registers, p.130

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.

]. H. +-90, A. Attiya, D. Bar-noy, D. Dolev, R. Peleg et al., Renaming in an asynchronous environment, Journal of the ACM, vol.37, issue.3, pp.524-548, 1990.

J. Aspnes and F. Ellen, Tight bounds for adopt-commit objects. Theory of Computing Systems, vol.55, pp.451-474, 2014.

E. +-06]-yehuda-afek, S. Gafni, M. Rajsbaum, C. Raynal, and . Travers, Simultaneous consensus tasks: A tighter characterization of set-consensus, ICDCN, pp.331-341, 2006.

H. James, M. Anderson, and . Moir, Using local-spin k-exclusion algorithms to improve wait-free object implementations, Distributed Computing, vol.11, issue.1, pp.1-20, 1997.

E. Borowsky and E. Gafni, Generalized FLP impossibility result for t-resilient asynchronous computations, STOC, pp.91-100, 1993.

E. Borowsky and E. Gafni, Immediate atomic snapshots and fast renaming, PODC, pp.41-51, 1993.

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

V. Bushkov and R. Guerraoui, Safety-liveness exclusion in distributed computing, 34th ACM Symposium on Principles of Distributed Computing, PODC '15, pp.227-236, 2015.

Z. Bouzid, E. Gafni, and P. Kuznetsov, Strong equivalence relations for iterated models, OPODIS, pp.139-154, 2014.

E. Borowsky, E. Gafni, N. A. Lynch, and S. Rajsbaum, The BG distributed simulation algorithm, Distributed Computing, vol.14, issue.3, pp.127-146, 2001.

E. James, N. A. Burns, and . Lynch, Bounds on shared memory for mutual exclusion, Information and Computation, vol.107, issue.2, pp.171-184, 1993.

Z. Bouzid, M. Raynal, and P. Sutra, Anonymous obstruction-free (n, k)-set agreement with n-k+1 atomic read/write registers, 19th International Conference on Principles of Distributed Systems, OPODIS '15, vol.18, p.17, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01680833

S. Chaudhuri, Agreement is harder than consensus: Set consensus problems in totally asynchronous systems, Proceedings of the 9th ACM Symposium on Principles of Distributed Computing, pp.311-324, 1990.

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.

A. Castañeda and S. Rajsbaum, New combinatorial topology bounds for renaming: the lower bound. Distributed Computing, vol.22, pp.287-301, 2010.

A. Castañeda and S. Rajsbaum, New combinatorial topology bounds for renaming: The upper bound, J. ACM, vol.59, issue.1, 2012.

A. Castañeda, S. Rajsbaum, and M. Raynal, Specifying concurrent problems: beyond linearizability and up to tasks, International Symposium on Distributed Computing, pp.420-435, 2015.

A. Castañeda, S. Rajsbaum, and M. Raynal, Long-lived tasks, International Conference on Networked Systems, pp.439-454, 2017.

C. Delporte-gallet, H. Fauconnier, E. Gafni, and S. Rajsbaum, Black art: Obstruction-free k-set agreement with |mwmr registers| < |proccesses|, 1st International Conference on Networked Systems, NETYS '13, pp.28-41, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00922423

C. Delporte-gallet, H. Fauconnier, P. Kuznetsov, and E. Ruppert, On the space complexity of set agreement, 34th ACM Symposium on Principles of Distributed Computing, PODC '15, pp.271-280, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01251563

C. Delporte, H. Fauconnier, S. Rajsbaum, and M. Raynal, t-resilient immediate snapshot is impossible, International Colloquium on Structural Information and Communication Complexity, pp.177-191, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01315342

C. Delporte-gallet, H. Fauconnier, E. Gafni, and P. Kuznetsov, OPODIS, 2016.

C. Delporte-gallet, H. Fauconnier, E. Gafni, and L. Lamport, Adaptive register allocation with a linear number of registers, 27th International Symposium on Distributed Computing, DISC '13, pp.269-283, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00922425

C. Delporte-gallet, H. Fauconnier, E. Gafni, and S. Rajsbaum, Linear space bootstrap communication schemes, Theoretical Computer Science, vol.561, pp.122-133, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01251557

C. Delporte-gallet, H. Fauconnier, R. Guerraoui, and A. Tielmann, The disagreement power of an adversary, Distributed Computing, vol.24, issue.3-4, pp.137-147, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00376981

C. Delporte-gallet and H. Fauconnier, Sergio Rajsbaum, and Nayuta Yanagisawa. A characterization of t-resilient solvable colorless tasks in anonymous shared-memory model, SIROCCO, p.15, 2018.

E. W. Dijkstra, Solution of a problem in concurrent programming control, Commun. ACM, vol.8, issue.9, p.569, 1965.

P. Fatourou, F. E. Fich, and E. Ruppert, Time-space tradeoffs for implementations of snapshots, 38th ACM Symposium on Theory of Computing, STOC '06, pp.169-178, 2006.

P. Fraigniaud, E. Gafni, S. Rajsbaum, and M. Roy, Automatically adjusting concurrency to the level of synchrony, Distributed Computing -28th International Symposium, pp.1-15, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01062031

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.

E. Gafni, Round-by-round fault detectors (extended abstract): Unifying synchrony and asynchrony, Proceedings of the 17th Symposium on Principles of Distributed Computing, 1998.

E. Gafni, The extended BG-simulation and the characterization of t-resiliency, STOC, pp.85-92, 2009.

E. Gafni and R. Guerraoui, Simulating few by many: Limited concurrency = set consensus, 2009.

E. Gafni and R. Guerraoui, Generalized universality, Proceedings of the 22nd international conference on Concurrency theory, CONCUR'11, pp.17-27, 2011.

E. Gafni, Y. He, P. Kuznetsov, and T. Rieutord, Read-Write Memory and k-Set Consensus as an Affine Task, 20th International Conference on Principles of Distributed Systems (OPODIS 2016), vol.70, pp.1-6, 2016.

E. Gafni and E. Koutsoupias, Three-processor tasks are undecidable, SIAM J. Comput, vol.28, issue.3, pp.970-983, 1999.

E. Gafni and P. Kuznetsov, Turning adversaries into friends: Simplified, made constructive, and extended, OPODIS, pp.380-394, 2010.

E. Gafni and P. Kuznetsov, Relating L-Resilience and Wait-Freedom via Hitting Sets, ICDCN, pp.191-202, 2011.

E. Gafni, P. Kuznetsov, and C. Manolescu, A generalized asynchronous computability theorem, ACM Symposium on Principles of Distributed Computing, PODC '14, pp.222-231, 2014.

E. Gafni and S. Rajsbaum, Distributed programming with tasks, Principles of Distributed Systems -14th International Conference, OPODIS 2010, pp.205-218, 2010.

E. Gafni, M. Raynal, and C. Travers, Test & set, adaptive renaming and set agreement: A guided visit to asynchronous computability, SRDS, pp.93-102, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00139305

M. Herlihy, Wait-free synchronization, ACM Transactions on Programming Languages and Systems, vol.13, issue.1, pp.123-149, 1991.

M. Herlihy, N. Dmitry, S. Kozlov, and . Rajsbaum, Distributed Computing Through Combinatorial Topology, 2014.

M. Herlihy, V. Luchangco, and M. Moir, Obstruction-free synchronization: Double-ended queues as an example, ICDCS, pp.522-529, 2003.

M. Herlihy and S. Rajsbaum, The decidability of distributed decision tasks (extended abstract), STOC, pp.589-598, 1997.

M. Herlihy and S. Rajsbaum, Simulations and reductions for colorless tasks, PODC, pp.253-260, 2012.

M. Herlihy and N. Shavit, The asynchronous computability theorem for t-resilient tasks, Proceedings of the 25th ACM Symposium on Theory of Computing, pp.111-120, 1993.

M. Herlihy and N. Shavit, The topological structure of asynchronous computability, Journal of the ACM, vol.46, issue.2, pp.858-923, 1999.

D. Imbs, P. Kuznetsov, and T. Rieutord, Progress-Space Tradeoffs in Single-Writer Memory Implementations, 21st International Conference on Principles of Distributed Systems (OPODIS 2017), volume 95 of LIPIcs, vol.9, p.17, 2017.
URL : https://hal.archives-ouvertes.fr/hal-01787848

D. Imbs and M. Raynal, Visiting gafni's reduction land: From the bg simulation to the extended bg simulation, SSS, pp.369-383, 2009.

P. Jayanti, K. Tan, and S. Toueg, Time and space lower bounds for non-blocking implementations (preliminary version), 15th ACM Symposium on Principles of Distributed Computing, PODC '96, pp.257-266, 1996.

D. König, Sur les correspondances multivoques des ensembles, Fundamenta mathematicae, vol.1, issue.8, pp.114-134, 1926.

N. Dmitry and . Kozlov, Chromatic subdivision of a simplicial complex, Homology, Homotopy and Applications, vol.14, issue.1, pp.1-13, 2012.

P. Kuznetsov and T. Rieutord, Agreement functions for distributed computing models, Networked Systems (NETYS), volume 10299 of LNCS, pp.175-190, 2017.

P. Kuznetsov, T. Rieutord, and Y. He, Brief Announcement: Compact Topology of Shared-Memory Adversaries, 31st International Symposium on Distributed Computing (DISC 2017), volume 91 of LIPIcs, vol.56, pp.1-56, 2017.

P. Kuznetsov, T. Rieutord, and Y. He, An asynchronous computability theorem for fair adversaries, 37th ACM Symposium on Principles of Distributed Computing, PODC '18, pp.387-396, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01572257

P. Kuznetsov, Understanding non-uniform failure models, Bulletin of the EATCS, vol.106, pp.53-77, 2012.

P. Kuznetsov, Universal model simulation: Bg and extended bg as examples, Stabilization, Safety, and Security of Distributed Systems, pp.17-31, 2013.

M. C. Loui and H. H. Abu-amara, Memory requirements for agreement among unreliable asynchronous processes, Advances in Computing Research, vol.4, pp.163-183, 1987.

L. Lamport, A new solution of dijkstra's concurrent programming problem, Communications of the ACM, vol.17, issue.8, pp.453-455, 1974.

L. Lamport, On interprocess communication; part I and II, Distributed Computing, vol.1, issue.2, pp.77-101, 1986.

M. Moir and J. H. Anderson, Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, vol.25, issue.1, pp.1-39, 1995.

A. Mostéfaoui, M. Raynal, and C. Travers, Exploring gafni's reduction land: From mega to wait-free adaptive (2p-[p/k])-renaming via k-set agreement, DISC, pp.1-15, 2006.

P. Frank and . Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society, vol.30, p.264286, 1930.

V. Saraph, M. Herlihy, and E. Gafni, Asynchronous computability theorems for t-resilient systems, DISC, pp.428-441, 2016.

V. Saraph, M. Herlihy, and E. Gafni, An algorithmic approach to the asynchronous computability theorem, Journal of Applied and Computational Topology, pp.1-24, 2018.

H. Edwin and . Spanier, Algebraic topology, 1966.

E. Sperner, Neuer beweis für die invarianz der dimensionszahl und des gebietes, Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, vol.6, pp.265-272, 1928.

M. Saks and F. Zaharoglou, Wait-free k-set agreement is impossible: The topology of public knowledge, Proceedings of the 25th ACM Symposium on Theory of Computing, pp.101-110, 1993.

M. Saks and F. Zaharoglou, Wait-free k-set agreement is impossible: The topology of public knowledge, SIAM J. on Computing, vol.29, pp.1449-1483, 2000.

G. Taubenfeld, Contention-sensitive data structures and algorithms, 23rd International Conference on Distributed Computing, DISC'09, pp.157-171, 2009.

G. Taubenfeld, The computational structure of progress conditions, DISC, 2010.

M. Alan and . Turing, On computable numbers, with an application to the entscheidungsproblem, Proceedings of the London mathematical society, vol.2, pp.230-265, 1937.

N. Yanagisawa, Wait-free solvability of colorless tasks in anonymous sharedmemory model, 18th International Symposium on Stabilization, Safety, and Security of Distributed Systems, SSS '06, pp.415-429, 2016.

L. Zhu, A tight space bound for consensus, 48th ACM Symposium on Theory of Computing, STOC '16, pp.345-350, 2016.