Atomic snapshots of shared memory, J. ACM, vol.40, issue.4, pp.873-890, 1993. ,
Defining liveness, Inf. Process. Lett, vol.21, issue.4, pp.181-185, 1985. ,
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. ,
Strong equivalence relations for iterated models, OPODIS, pp.139-154, 2014. ,
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. ,
Set-consensus collections are decidable, OPODIS, 2016. ,
URL : https://hal.archives-ouvertes.fr/hal-01416981
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
Impossibility of distributed consensus with one faulty process, J. 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. ,
Read-write memory and k-set consensus as an affine task, OPODIS, 2016. ,
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. ,
Wait-free synchronization, ACM Trans. Prog. Lang. Syst, vol.13, issue.1, pp.123-149, 1991. ,
Distributed Computing Through Combinatorial Topology, 2014. ,
Simulations and reductions for colorless tasks, PODC, pp.253-260, 2012. ,
The topological structure of asynchronous computability, J. ACM, vol.46, issue.2, pp.858-923, 1999. ,
A framework for the design of dependent-failure algorithms. Concurrency and Computation: Practice and Experience, vol.19, pp.2255-2269, 2007. ,
Chromatic subdivision of a simplicial complex, Homology, Homotopy and Applications, vol.14, issue.1, pp.1-13, 2012. ,
Understanding non-uniform failure models, Bulletin of the EATCS, vol.106, pp.53-77, 2012. ,
Agreement functions for distributed computing models, NETYS, 2017. To apper ,
Affine Tasks for k-Test-and-Set. working paper or preprint, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01810601
Brief announcement: Compact topology of shared-memory adversaries, 31th International Symposium on Distributed Computing, DISC'16, vol.56, pp.1-4, 2017. ,
An asynchronous computability theorem for fair adversaries, Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, pp.387-396, 2018. ,
URL : https://hal.archives-ouvertes.fr/hal-01572257
Distributed Algorithms, 1996. ,
Wait-free k-set agreement is impossible: The topology of public knowledge, SIAM J. on Computing, vol.29, pp.1449-1483, 2000. ,
Asynchronous computability theorems for t-resilient systems, DISC, pp.428-441, 2016. ,
Algebraic topology, 1966. ,
The vertices of C are points of |C|. 2. For any ? ? C , there exists ? ? C such that ? ? |?|, DISC, vol.1, 2010. ,
, The piecewise linear map |C | ? |C| mapping each vertex of C to the corresponding point of C is a homeomorphism
, We now turn to the chromatic complexes used in distributed computing, and recall some notions from, vol.20
We view s as a complex, with its simplices being all possible faces t. A chromatic complex is a simplicial complex C together with a non-collapsing simplicial map ? : C ? s. Note that C can have dimension at most n. We usually drop ? from the notation. We write ?(C) for the union of ?(v) over all vertices v ? C. Note that if C ? C is a sub-complex of a chromatic complex, it inherits a chromatic structure by restriction. In particular, the standard n-simplex s is a chromatic complex, with ? being the identity. Every chromatic complex C has a standard chromatic subdivision Chr C. Let us first define Chr s for the standard simplex s. The vertices of Chr s are pairs (i, t), where i ? {0, 1, . . . , n} and t is a face of s containing i. We let ?(i, t) = i. Further, Chr s is characterized by its n-simplices ,