, 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
37 3.7 Round-based simulation for simulator s i ,
45 3.10 Adaptive set-consensus for t-resilient systems (for process p i ), p.48 ,
, Agreement Functions Chapter
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 ,
Atomic snapshots of shared memory, Journal of the ACM, vol.40, issue.4, pp.873-890, 1993. ,
Renaming in an asynchronous environment, Journal of the ACM, vol.37, issue.3, pp.524-548, 1990. ,
Tight bounds for adopt-commit objects. Theory of Computing Systems, vol.55, pp.451-474, 2014. ,
Simultaneous consensus tasks: A tighter characterization of set-consensus, ICDCN, pp.331-341, 2006. ,
Using local-spin k-exclusion algorithms to improve wait-free object implementations, Distributed Computing, vol.11, issue.1, pp.1-20, 1997. ,
Generalized FLP impossibility result for t-resilient asynchronous computations, STOC, pp.91-100, 1993. ,
Immediate atomic snapshots and fast renaming, PODC, pp.41-51, 1993. ,
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. ,
Safety-liveness exclusion in distributed computing, 34th ACM Symposium on Principles of Distributed Computing, PODC '15, pp.227-236, 2015. ,
Strong equivalence relations for iterated models, OPODIS, pp.139-154, 2014. ,
The BG distributed simulation algorithm, Distributed Computing, vol.14, issue.3, pp.127-146, 2001. ,
Bounds on shared memory for mutual exclusion, Information and Computation, vol.107, issue.2, pp.171-184, 1993. ,
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
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. ,
More choices allow more faults: Set consensus problems in totally asynchronous systems, Information and Computation, vol.105, issue.1, pp.132-158, 1993. ,
, New combinatorial topology bounds for renaming: the lower bound. Distributed Computing, vol.22, pp.287-301, 2010.
New combinatorial topology bounds for renaming: The upper bound, J. ACM, vol.59, issue.1, 2012. ,
Specifying concurrent problems: beyond linearizability and up to tasks, International Symposium on Distributed Computing, pp.420-435, 2015. ,
Long-lived tasks, International Conference on Networked Systems, pp.439-454, 2017. ,
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
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
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
, OPODIS, 2016.
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
Linear space bootstrap communication schemes, Theoretical Computer Science, vol.561, pp.122-133, 2015. ,
URL : https://hal.archives-ouvertes.fr/hal-01251557
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
Sergio Rajsbaum, and Nayuta Yanagisawa. A characterization of t-resilient solvable colorless tasks in anonymous shared-memory model, SIROCCO, p.15, 2018. ,
Solution of a problem in concurrent programming control, Commun. ACM, vol.8, issue.9, p.569, 1965. ,
Time-space tradeoffs for implementations of snapshots, 38th ACM Symposium on Theory of Computing, STOC '06, pp.169-178, 2006. ,
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
Impossibility of distributed consensus with one faulty process, Journal of the ACM, vol.32, issue.2, pp.374-382, 1985. ,
Round-by-round fault detectors (extended abstract): Unifying synchrony and asynchrony, Proceedings of the 17th Symposium on Principles of Distributed Computing, 1998. ,
The extended BG-simulation and the characterization of t-resiliency, STOC, pp.85-92, 2009. ,
Simulating few by many: Limited concurrency = set consensus, 2009. ,
Generalized universality, Proceedings of the 22nd international conference on Concurrency theory, CONCUR'11, pp.17-27, 2011. ,
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. ,
Three-processor tasks are undecidable, SIAM J. Comput, vol.28, issue.3, pp.970-983, 1999. ,
Turning adversaries into friends: Simplified, made constructive, and extended, OPODIS, pp.380-394, 2010. ,
Relating L-Resilience and Wait-Freedom via Hitting Sets, ICDCN, pp.191-202, 2011. ,
A generalized asynchronous computability theorem, ACM Symposium on Principles of Distributed Computing, PODC '14, pp.222-231, 2014. ,
Distributed programming with tasks, Principles of Distributed Systems -14th International Conference, OPODIS 2010, pp.205-218, 2010. ,
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
Wait-free synchronization, ACM Transactions on Programming Languages and Systems, vol.13, issue.1, pp.123-149, 1991. ,
Distributed Computing Through Combinatorial Topology, 2014. ,
Obstruction-free synchronization: Double-ended queues as an example, ICDCS, pp.522-529, 2003. ,
The decidability of distributed decision tasks (extended abstract), STOC, pp.589-598, 1997. ,
Simulations and reductions for colorless tasks, PODC, pp.253-260, 2012. ,
The asynchronous computability theorem for t-resilient tasks, Proceedings of the 25th ACM Symposium on Theory of Computing, pp.111-120, 1993. ,
The topological structure of asynchronous computability, Journal of the ACM, vol.46, issue.2, pp.858-923, 1999. ,
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
Visiting gafni's reduction land: From the bg simulation to the extended bg simulation, SSS, pp.369-383, 2009. ,
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. ,
Sur les correspondances multivoques des ensembles, Fundamenta mathematicae, vol.1, issue.8, pp.114-134, 1926. ,
Chromatic subdivision of a simplicial complex, Homology, Homotopy and Applications, vol.14, issue.1, pp.1-13, 2012. ,
Agreement functions for distributed computing models, Networked Systems (NETYS), volume 10299 of LNCS, pp.175-190, 2017. ,
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. ,
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
Understanding non-uniform failure models, Bulletin of the EATCS, vol.106, pp.53-77, 2012. ,
Universal model simulation: Bg and extended bg as examples, Stabilization, Safety, and Security of Distributed Systems, pp.17-31, 2013. ,
Memory requirements for agreement among unreliable asynchronous processes, Advances in Computing Research, vol.4, pp.163-183, 1987. ,
A new solution of dijkstra's concurrent programming problem, Communications of the ACM, vol.17, issue.8, pp.453-455, 1974. ,
On interprocess communication; part I and II, Distributed Computing, vol.1, issue.2, pp.77-101, 1986. ,
Wait-free algorithms for fast, long-lived renaming, Science of Computer Programming, vol.25, issue.1, pp.1-39, 1995. ,
Exploring gafni's reduction land: From mega to wait-free adaptive (2p-[p/k])-renaming via k-set agreement, DISC, pp.1-15, 2006. ,
On a problem of formal logic, Proceedings of the London Mathematical Society, vol.30, p.264286, 1930. ,
Asynchronous computability theorems for t-resilient systems, DISC, pp.428-441, 2016. ,
An algorithmic approach to the asynchronous computability theorem, Journal of Applied and Computational Topology, pp.1-24, 2018. ,
Algebraic topology, 1966. ,
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. ,
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. ,
Wait-free k-set agreement is impossible: The topology of public knowledge, SIAM J. on Computing, vol.29, pp.1449-1483, 2000. ,
Contention-sensitive data structures and algorithms, 23rd International Conference on Distributed Computing, DISC'09, pp.157-171, 2009. ,
The computational structure of progress conditions, DISC, 2010. ,
On computable numbers, with an application to the entscheidungsproblem, Proceedings of the London mathematical society, vol.2, pp.230-265, 1937. ,
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. ,
A tight space bound for consensus, 48th ACM Symposium on Theory of Computing, STOC '16, pp.345-350, 2016. ,