Proof: Let S be the number of complete (m ?1)-simplexes in K m (colored with f0; : : :; m ? 1g), where the (m ? 1)-simplexes in each m-simplex are considered separately, and counted as +1 or ?1, by their induced orientations. We argue that S = I and S = C. To prove that S = I, consider the following cases. If an (m ? 1)-face is internal, then it contributes 0 to S, since the contributions of the two m-simplexes containing it cancel each other. Obviously, an internal (m ? 1)-face contributes 0 to I. An external (m ? 1)-face in the boundary of K m is counted the same, +1 or ?1 by orientation, in both S and I. Therefore, S = I. To prove that C = S, consider an m-simplex m , and look at the following cases. Proof: Assume the vertices of M( m ) are f0; 1; : : :; mg. Let i be the simplex in M( m ) labeled with f0; 1; : : :; ig, and for i > 0, let I i , C i , be the index and the content of ( i ). We prove by induction on i that C i is odd; the basis, i = 1, is trivial. Assume the claim holds for m ? 1. Thus, the content C m?1 of ( m?1 ) is odd. But C m?1 is equal to the index I m of ( m ). By the Index Lemma (Lemma 6.2), I m = C m . It follows that there exists an odd number of simplexes 2 ( m ) with ( ) = m , as needed. 41 opposite orientations to the face. That is, the chain @( 1 + 2 ) has zero coe cient on the face that 1 and 2 share. Such an orientation is called coherent, and partitions the m-simplexes in two classes, so that simplexes that share an (m ? 1)-face are in di erent classes. Notice that the orientation of simplexes of dimension other than m can be arbitrary. Also, if K m is orientable, then it has exactly to coherent orientations. The next proposition follows directly from the de nition of pseudomanifold and of orientability. Proposition B.1 Let K m be an m-pseudomanifold with a coherent orientation, and c the chain which is the sum of all its m-simplexes. Then @(c) is a chain of (m ? 1)-simplexes, which as a set is equal to bound(K m ). Let E n be the ISE complex on input n , where each process executes a xed number of steps. Theorem 5.14 There is an algebraic span from M( n ) to E n . Proof: Give an arbitrary orientation to the simplexes of M( n ) to obtain a chain complex C(M( n )). By Theorem 5.9 we know that E n is a chromatic divided image of M( n ) under . By Theorem 5.13 we can give to every pseudomanifold ( ) a coherent orientation, and obtain the chain complex C(E n ). Let _ be the chain map that associates to i 2 M( n ), the chain which is the sum of the isimplexes that appear in ( ), with sign de ned as follows: _ ( n ) is the sum of the n-simplexes in ( n ). If _ ( i ) has been de ned, then _ (face j ( i )) is the sum of the (i ? 1)-simplexes in (face j ( i )) with sign (?1) j . We proceed to prove that _ is a chain map. First, _ q is a well de ned homomorphism, since it is de ned on simplexes (the generators of the group C q (M( n ))), and extended linearly. Now, _ q ( q ) = c satis es the hypothesis of Proposition B.1, and hence @ 0 q (c) is equal to bound( ( q )), as a set. Since @ q ( q ) is equal P q i=0 (?1) i face i ( q ), and equal to bound( q ) as a set, and by the last requirement of the de nition of a divided image, we have that @ 0 q q = q?1 @ q , since the orientations correspond. Notice that with q = 0 we use Condition 3 of De nition 4.1. Fix a coloring c of K m with f0; : : :; mg. Let Recall that by Lemma 5.12, a chromatic pseudomanifold K m is orientable if and only if its m-simplexes can be partitioned into two disjoint classes, such that if two m-simplexes share an (m ? 1)-face then they belong to di erent classes. A q-chain of K is a formal sum of oriented q-simplexes: P`i =0 i q i , where i is an integer. When writing chains, we typically omit q-simplexes with zero coe cients, unless they are all zero, when we simply write 0. We write 1 q as q and ?1 q as ? q . We identify ? q with q having the opposite orientation. The q-chains of K (with component-wise addition) form a free Abelian group C q (K), called the q-th chain group of K. For dimension ?1, we adjoin the in nite cyclic group Z in dimension -1, C ?1 (K) = Z. The boundary @ q : C q (K) ! C q?1 (K) is a homomorphism such that, for a q-chain , @ q?1 @ q = 0 ; and the augmentation @ 0 : C 0 (K) ! C ?1 (K) is an epimorphism (i.e., a surjective homomorphism). For an oriented simplex q = (v 0 ; : : :v q ), let face i ( q ), the i th face of q , to be the (q ? 1)-simplex (v 0 ; : : :;v i ; : : :; v q ), where circum ex denotes omission. The boundary operator @ q : C q (K) ! C q?1 (K), q > 0, is de ned on simplexes: The chain complex C(K) is the sequence of groups and homomorphisms fC q (K); @ q g. Let C(K) = fC q (K); @ q g and C(L) = fC q (L); @ 0 q g be chain complexes for simplicial complexes K and L. An augmentation-preserving chain map (or chain map) is a family of homomorphisms. q : C q (K) ! C q (L) ; such that @ 0 q q = q?1 @ q . Let S`= M( `) , for a simplex `. An algebraic span is a chain map : C(S`) ! C(P n ), where P n is a protocol complex. An m-pseudomanifold K m is orientable if its simplexes can be oriented in a way such that if two m-simplexes share a face, then the chain @( 1 + 2 ) has zero coe cient on the face that 1 and 2 share. When K m is properly colored this is equivalent to saying that the m-simplexes can be oriented in such a way that if two m-simplexes share an (m ? 1)-face, then they give 6 Munkres 25] uses for @0. Proof: Assume i?1 2~ (bound( i ) Before proving the other direction of the claim, notice that bound(~ ( i )) bound( ( i )). Otherwise, if i?1 2 bound(~ ( i )), then there exists a unique i 2~ ( i ) containing i?1 . If there is another i-simplex 2 ( i ) containing i?1 , would also be in~ ( i ), by de nition of , since and i are connected by a (one step) i-path. Assume that i?1 2 bound(~ ( i )), and let i be the unique i-simplex in~ ( i ) containing i?1 . Then i?1 2 bound( ( i )), since we have just proved that bound(~ ( i )) bound( ( i )). Hence i?1 2 (bound( i )), and thus i?1 2 ( i?1 ), for some face i?1 of i . Since i 2~ ( i ), there exists an i-path from i to an i-simplex containing some i?1 To complete the proof of the lemma, we show, by induction on i, that~ ( i ) is i-connected, and that, for i > 1,~ (bound( i )) is (i ? 1)-connected. To show that~ (bound ( 2 )) is 1-connected, observe that~ ( 1 ) is 1-connected because since it is nite, it is a graph which consists of a simple path. The lemma follows since De nition 4.1(4) holds. For the induction step, we rst show that~ ( i ) is i-connected. By the induction hypothesis, the boundary of~ ( i ) is (i ? 1)-connected. Remove one i-simplex with an exterior face from ( i ). The complex obtained is a pseudomanifold, and its boundary is still (i ? 1)-connected. We repeat this process until no more such i-simplexes exist. Since every i-simplex is connected by an i-path to an i-simplex with a face in the boundary, this process removes every i-simplex. The proof that~ (bound( i+1 )) is i-connected follows from the fact that~ ( i ) is i-connected: it su ces to prove that for any 1 ; 2 2 bound( i+1 ),~ ( 1 ) \~ ( 2) contains an (i ? 1)-simplex. This follows from De nition 4.1(4), because~ ( 1 ) \~ ( 2) =~ ( 1 \ 2 ), and from De nition 4.1(5), because~ ( 1 \ 2 ) is an (i ? 1)-pseudomanifold. We start with some algebraic preliminaries; see 25, Section 1.13] and 20]. Let K be an n-dimensional simplicial complex, and = (v 0 ; : : :; v q ) a q-simplex of K. An orientation for is an equivalence class of orderings on v 0 ; : : :; v q , consisting of one particular ordering and all even permutations of it. For example, an orientation of a 1-simplex (v 0 Assume~ ( j ) has been de ned for j < i, satisfying the required properties. Let~ ( i ) be the complex containing every face of every i 2 ( i ), such that there exists an i-path from i to some simplex with an (i ? 1)-face in~ (bound( i )). First notice that~ ( i ) is an i-pseudomanifold, since~ ( i ) ( i ), and it is full to dimension i. It is also simple to see it has properties (1), (2) This bound is tight, by the protocol of 10]. This paper presents a study of wait-free solvability based on combinatorial topology. Informally, we have de ned the notion of a chromatic divided image, and proved that a necessary condition for wait-free solvability is the existence of a simplicial chromatic mapping from a divided image of the inputs to the outputs that agrees with the problem speci cation. We also derive a new necessary and su cient condition, based on a speci c, well structured chromatic divided image, the ISE complex. The ISE complex is also proved to be orientable and connected, which allowed us to prove theorems about its combinatorial properties. These properties were then used to derive tight lower bounds for renaming and k-set consensus. Our results do not use homology groups, whose computation may be complicated. In a recent paper, Borowsky and Gafni 8] introduce a new model of computation, based on an iterated version of immediate snapshots, and prove that it is equivalent to the wait-free model, when only decision tasks are concerned. In this model, there is a sequence of immediate snapshot objects. A process accesses the i-th object in its i-step, writing its entire state. Thus, each object is used at most once by each process. It is easy to check that the iterated immediate snapshot executions complex is a divided image of the input complex; the proof is completely analogous to the proof that the immediate snapshot executions complex is a divided image of the input complex. Therefore, the characterization and impossibility results of this paper hold for this model as well. This exemplify how our combinatorial framework can be useful for other models of computation. Many questions remain open. First, it is of interest to nd other applications to the necessary and su cient condition presented here; in particular, can we derive interesting protocols from the su cient condition? Second, there are several directions to extend our framework, e.g., to allow fewer than n failures (as was done for one failure in 5]), to handle other primitive objects besides read/write registers (cf. 19, 9]), and to incorporate on-going tasks. Acknowledgments: We would like to thank Javier Bracho, Eli Gafni, John Havlicek, Maurice Herlihy, Guy Ray, Nir Shavit and Mark Tuttle for comments on the paper and very useful discussions. order preserving mapping between any two subsets of process ids, of the same size; i.e., the mapping that maps the smallest id in one set to the smallest id in the second set, etc. It is obvious that S has structural symmetry under , since we consider only executions in which all processes take the same number of steps. Let P be the decision map implied by P, and de ne 0 to be the binary coloring which colors each vertex in S with the parity of the value assigned to it by P . Fix an input simplex n . Since the protocol is comparison-based and anonymous, 0 is a symmetric coloring of S( n ) (with respect to ). Therefore, the assumptions of Theorem 6.4 are satis ed and therefore, at least one m-simplex of S( n ) is monochromatic under 0 . On the other hand, note that the domain 0; 2n ? 1] does not include n + 1 di erent odd names; similarly, the domain 0; 2n ? 1] does not include n + 1 di erent even names. This implies that 0 cannot color any simplex of S with all zeroes or with all ones; i.e., no simplex of S is monochromatic. A contradiction. Intuitively, in the k-set consensus task 10], processes start with input values from some domain and are required to produce at most k di erent output values. To assure non-triviality, we require all output values to be input values of some processes. Captured in our combinatorial topology language, the k-set consensus task is the triple hD n ; D n ; i. D n is P(D), for some domain D, and maps each n 2 D n to the subset of n-simplexes in D n that contain at most k di erent values from the values in n . We now use Theorem 5.9 and Sperner's Lemma to prove: Theorem 7.2 If k n then there does not exists a wait-free protocol that solves the k-set consensus task. Proof: Assume, by way of contradiction, that P is a wait-free protocol for the k-set consensus task, k n. We show that P must have at least one execution in which k + 1 di erent values are output, which implies that P does not solve the k-set consensus task correctly. This is done by applying Theorem 6.3 to the ISE complex, which is a chromatic divided image of the input complex, by Theorem 5.9. Let P be the decision map implied by P. Note that P can also be seen as a simplicial map into I n . Consider the input simplex of dimension k + 1, where processes p 0 ; : : :; p k have di erent input values v 0 ; : : :; v k , respectively. Clearly, there exists some bound N on the number of steps a process takes in all executions on input . By Theorem 5.9, E n ( ) is a divided image of . Let v be the value P assigns to some vertex in E( ), and let 0 be its carrier in M( ). The non-triviality condition implies that v is the input of some process in 0 , and therefore: 33 orientation. Thus, all complete (m ? 1)-simplexes in bound(K m ) are counted with the same sign by I (whether on the same face or not), implying that I 6 = 0. In this section, we apply the condition for wait-free solvability presented earlier (Theorem 5.9) to derive two lower bounds, for renaming and for k-set consensus. The rst lower bound also relies on Theorem 6.4, and therefore, on the fact that the chromatic divided image induced by immediate snapshot executions is orientable and connected. In the renaming task 2], processes start with an input value (original name) from a large domain and are required to decide on distinct output values (new names) from a domain which should be as small as possible. Clearly, the task is trivial if processes can access their id; in this case, process p i decides on i, which yields the smallest possible domain. To avoid trivial solutions, it is required that the processes and the protocol are anonymous 2]. That is, process p i with original name x executes the same protocol as process p j with original name x. Captured in our combinatorial topology language, the M-renaming task is the triple hD n ; M n ; i. D n contains all subsets of some domain D (of original names) with di erent values, M n contains all subsets of 0::M] (of new names) with di erent values, and maps each n 2 D n to all n-simplexes of M n . We use Theorem 5.9 and Theorem 6.4 to prove that there is no wait-free anonymous protocol for the M-renaming task, if M 2n ? 1. The bound is tight, since there exists an anonymous wait-free protocol for the 2n-renaming problem 2]. Theorem 7.1 If M < 2n, then there is no anonymous wait-free protocol that solves the Mrenaming task. Proof: Assume, by way of contradiction, that P is a wait-free protocol for the M-renaming task, M 2n ? 1. Assume that D = 0::2n]; i.e., assume that the original names are only between 0 and 2n. Since we consider a bounded set of inputs, we can assume, without loss of generality, that every process executes the same number of steps. Furthermore, we assume that P is comparison-based, i.e., the protocol produces the same outputs on inputs which are order-equivalent. (See Herlihy 18], who attributes this observation to Eli Gafni). By Theorem 5.9, the ISE complex, S, is a chromatic divided image of the input complex D n . By Theorem 5.13, S is orientable, and by Theorem 5.11, S is connected. Let be the . Then 2 is the union of (m) and the vertex of~ with id m. Next, 3 is the union of (m?1) 2 and the vertex of~ with id m ? 1. Thus, 3 has two vertices in common with~ , and we can continue in this way until we get to k =~ . Similarly, we can construct a path from~ to 0 . By the symmetry of m , we can take both sub paths of equal length, so the path has even length, and therefore and 0 have the same 31 position, the length of this path must be odd. (By considering the hypercube of binary coloring vectors, as done for the case of two complete simplexes on the image of the same face.) Since orientations on this path alternate, it follows that 3 and 2 have di erent orientations. The coloring 2 = f(1; 1); (2; 2); : : :; (m; 0)g c , is rotated relative to its ids, and hence the orderings of 3 and 2 agree (on the sign of the permutation) if and only if m is odd. E.g., if m = 2, they disagree|f(1; 1); (2; 0)g, and if m = 3, they agree|f(1; 1); (2; 2); (3; 0)g. To complete the proof of the claim, we will prove that the orientation of 1 is (?1) m times the orientation of 3 . This relies on the fact that they are symmetric simplexes under in ( ) and ( ). That is, the orientations of 1 and 3 agree when m is even, and disagree otherwise. Therefore, the orientations of 1 and 2 agree, and they are counted with the same sign by I, and the proof will follow. The intuition for the proof that the orientation of 1 is (?1) m times the orientation of 3 is illustrated in Figure 6 . In this example, m = 3, and ( (3) ) is at the top and ( (0) ) at the bottom. The numbers in the gure represent ids. The two simplexes marked are in corners, and symmetric. The orientation of the one on top, call it 1 , is 0; 1; 2. The orientation of the bottom one, call it 3 , is 1; 3; 2.  ); where v ij is the vertex with id i j of (i) , and hence v i0 ; : : :; v im?1 is some permutation of the vertices of (i) . Notice that for each permutation there is a unique simplex in this corner. Let 1 be the simplex in the corner 0; 1; : : :; m ? 1 of ( (m) ), and let 3 be the symmetric simplex in ( (0) ), which must be in the corner 1; 2; : : :; m. Now, the rst observation is that any two corners of ( (m) ) have the same orientation. For example, consider two corners in ( (3) ) in Figure 6 , 1 (the top marked simplex), which is the 0; 1; 2 corner, and the 1; 2; 3 corner, 0 3 , which is the simplex in ( ) adjacent to 3 (the bottom marked simplex). Both are oriented 0; 1; 2. Once we prove this, the claim will follow by observing that 3 is adjacent to a unique simplex in ( ). Notice that the colors assigned by c are the same in 1 and 2 , and thus both 1 and 2 will be counted by I. Furthermore, since 2 has the same ids as 1 and is complete, then it must have the same binary coloring as 1 , i.e., all 0's. It remains to show that 1 and 2 have the same orientation and hence are counted with the same sign by I. Since ( ) is (m ? 1)-connected, there is an (m ? 1)-path between 1 and 2 . Note that this path consists of a sequence of (m ? 1)-simplexes, each sharing an (m ? 2)-face with the previous simplex. Furthermore, since the binary coloring is irreducible, the binary coloring of each simplex in the path di ers from the binary coloring of the previous one in exactly one vertex. Thus the binary coloring of the simplexes in the path induces a sequence of binary vectors, starting with the all 0's vector and ending with the all 0's vector, each di ering from the previous one in exactly one binary color. That is, the path corresponds to a cycle in a hypercube graph. Since the hypercube graph is bipartite, the length of any cycle in it is even; therefore, the length of the path is even. Clearly, since K m is oriented, consecutive simplexes on the path have di erent orientations. Since the length of the path is even, 1 and 2 have the same orientation. Hence, 1 and 2 are counted with the same sign by I. We now show that any complete (m ? 1)-simplex 2 in ( ), for i 6 = m, will be counted with the same sign by I. Without loss of generality, assume i = 0. Note that 2 is complete, with process id's f1; 2; : : :; mg. Thus, the binary color of the vertex with process id m must be 1, so that its c coloring will be 0. This implies that 2 = f(1; 1); (2; 2); : : :; (m; 0)g c . Therefore  ), which is isomorphic to 1 , and let be the bijection of from the id's of (m) and the id's of (0) . Since b is symmetric, the binary coloring of 3 is all 0's, as the binary coloring of 1 ; that is, 3 = f(1; 0); (2; 0); : : :; (m; 0)g b . Note that 3 is not complete, since 3 = f(1; 1); (2; 2); : : :; (m; m)g c . Since ( (0) ) is connected, there is an (m ? 1)-path between 3 and 2 in ( (0) ). Since the binary coloring vector of 2 di ers from the binary coloring vector of 3 in exactly one 29 Let K m be a divided image of M( m ). The well-known Sperner's Lemma says that an odd number of m-simplexes of K m must go to m (and in particular, at least one simplex). For orientable divided images, Sperner's Lemma follows from the Index Lemma; this proof appear in Appendix C. We emphasize that Sperner's Lemma holds also for non-orientable divided images (see for example 3]). This lemma is used in Section 7.2 for the set consensus impossibility, and hence, this impossibility does not depend on orientability. For the induction step, assume that m > 1, and that we have proved the claim for m ? 1. Let be the simplicial map from m to itself that maps the vertex v whose id is i to the vertex whose id is (i + 1) mod (m + 1) (that is, the mapping the rotates the id's). In the rest of the proof, we assume that sub-indices are taken modulo m + 1. This is proved by showing that all complete (m ? 1)-simplexes in bound(K m ) are counted with the same sign by I; we rst consider complete (m ? 1)-simplexes on the same face. Proof: We squeeze bound(K m ) by using contractions; a contraction of bound(K m ) is obtained by identifying one of its vertices, v 0 , with another vertex, v, with the same color, and deleting any simplex containing both v and v 0 . We apply symmetric contractions, in which we choose an internal (m ? 2)-simplex, m?2 2 ( ), such that its two link vertices have the same binary coloring; hence, a contraction can be applied to m?2 . We contract m?2 and simplexes isomorphic to it in ( (i) ), for all i. (This is a sequence of m + 1 contractions.) Notice that the simplexes which are isomorphic to m?2 are also internal, furthermore, since b is symmetric, their link vertices have the same binary coloring. We show that if a symmetric contraction is applied to bound(K m ) to obtain bound 0 , then bound 0 is a boundary of a symmetric, oriented chromatic divided image of m under 0 , with 0 (bound( m )) = bound 0 , and #mono( 0 ( m )) = #mono( ( m )). If v 1 and v 2 are the link vertices of m?2 2 ( ), then id(v 1 ) = id(v 2 ). Therefore, bound 0 is chromatic. Also, it is easy to see that the orientation on bound 0 is still well de ned: two (m?1)-simplexes that did not have an (m?2)-face in common before the contraction will have it after the contraction, only if they di er in exactly one vertex, in addition to v 1 and v 2 . Thus, two such simplexes have opposite orientations (since orientations alternate on simplexes that share an (m ?2)-face). By the de nition of symmetric contraction, bound 0 remains symmetric. Since a contraction removes simplexes with opposite orientations and the same binary colorings, #mono( ( m )) = #mono( 0 ( m )). The proof of the main theorem relies on the Index Lemma|a classical result of combinatorial topology, generalizing Sperner's Lemma (cf. 16, p. 201]). For completeness, we state this lemma here, and include a proof of it in our framework in Appendix C. Theorem 5.14 There is an algebraic span from M( n ) to E n . In this section we prove a combinatorial theorem about the number of monochromatic simplexes in any binary coloring of an orientable divided image; this theorem is used in the next section to show a lower bound on renaming. Let K m be an orientable, chromatic divided image of m under . Fix an orientation of K m , and an induced orientation on its boundary. Let #mono(K m ) be the number of monochromatic m-simplexes of K m , counted by orientation, i.e., an m-simplex is counted as +1 if it is positively oriented, otherwise, it is counted as ?1. For example, consider a complex K m with two m-simplexes, as in Figure 5 , with all vertexes colored 1, then both simplexes are monochromatic In this case, the count is 0, since the simplexes have opposite orientations, and hence one is counted +1 and the other is counted ?1. The main theorem of this section applies to divided images that have structural symmetry, i.e., any pair of divided images of faces (of the same dimension) are isomorphic, under a bijection that maps the process ids consistently. A mapping, f : L m ! K m is id consistent if for any two vertices Formally, a divided image K m has structural symmetry if for any two i-faces, i 1 and i 2 , of , there is an id consistent simplicial bijection (one-to-one mapping), , between the vertices of ( i 1 ) and the vertices of ( i 2 ). For example, the ISE complex has structural symmetry, if we consider all immediate snapshot executions in which all processes take the same number of steps. A binary coloring, b, of K m with structural symmetry , is symmetric if isomorphic vertices have the same color; that is, b( (v)) = b(v), for every vertex v 2 K m . Proving that a coloring is symmetric is not trivial, and will be done when the binary coloring theorem is applied in Section 7.1. Notice that if K m has a symmetric binary coloring, then it has structural symmetry, by de nition. Consider an internal (m?2)-simplex, m?2 2 bound(K m ), which is contained in two (m?1)-simplexes, 1 and 2 . Its link vertices are v 1 , which is the vertex of 1 not in m?2 , and v 2 , which is the vertex of 2 not in m?2 . A binary coloring is irreducible if the link vertices of any internal (m ? 2)-simplex simplex of ( (i) ) have di erent binary colors. We now argue why we may restrict our attention to irreducible binary colorings, by proving that bound(K m ) can be \squeezed" to make sure its coloring is irreducible, while preserving all its interesting properties.  negative orientations. Consider two m-simplexes 1 and 2 that share an (m ? 1)-face, then since K m is orientable, the shared face gets opposite induced orientations. Therefore, because K m is chromatic, 1 and 2 must be in di erent classes. To prove the converse direction, assume we can partition the simplexes of a chromatic pseudomanifold K m into two disjoint classes, such that if two m-simplexes share an (m?1)-face then they belong to di erent classes. Orient all simplexes of the rst class in positive direction, and the simplexes of the second class in negative direction. Consider two m-simplexes 1 and 2 that share an (m ? 1)-face, . Remark. The previous theorem can be strengthened, to remove the assumption that processes always take the same number of steps, if we assume that each process always takes an even number of steps. The proof does not change. Since any protocol can be modi ed so that each process always takes an even number of steps, making this assumption causes no loss of generality. Thus, this stronger version of the theorem allows to work with in nite input complexes, and is not restricted to bounded wait-free protocols. Herlihy and Rajsbaum introduced algebraic spans as a structure useful to obtain impossibilities for renaming and set-consensus with algebraic techniques 20]. In Appendix B, we show that an orientable chromatic divided image induces an algebraic span; the proof requires the de nition of algebraic span, a concept of a di erent avor from the rest of this paper. The next simple lemma (e.g. 4]) shows that if we restrict attention to chromatic pseudomanifolds, the previous (common) de nition of orientability is equivalent to a simpler combinatorial de nition. Lemma 5.12 A chromatic pseudomanifold K m is orientable if and only if its m-simplexes can be partitioned into two disjoint classes, such that if two m-simplexes share an (m ?1)-face then they belong to di erent classes. Proof: Assume K m is orientable, and partition its simplexes into two classes, one consisting of the simplexes with positive orientations, and the other consisting of the simplexes with 24 Theorem 5.10 Let hI n ; O n ; i be a task. There exists a wait-free protocol which solves this task if and only if there exists a full divided image E n of I n and a color-preserving (on ids), anonymous simplicial map from E n to O n that agrees with . Proof: Assume there exists a wait-free protocol P which solves . In particular, P solves in immediate snapshot executions. By Theorem 5.9, the ISE complex, E n , is a chromatic divided image of I n . Since the protocol can be simulated by a full-information protocol, the corresponding full divided image is also a chromatic divided image of I n . Clearly, P is a color-preserving (on ids), anonymous simplicial map from E n to O n that agrees with . Assume there exists a full divided image E n of I n and a color-preserving (on ids), anonymous simplicial map from E n to O n that agrees with . Using as the decision rule, we get a wait-free protocol which solves in the immediate snapshot executions. By Lemma 3.1, this implies that there is a wait-free protocol for . Note that one direction of the proof, the necessary condition, applies also to protocols that are not full-information. Remark. The above theorem ignores the issue of computability. Clearly, the su cient condition requires that each process can compute its corresponding part of . Furthermore, if a task is solvable then it implies a way to compute . Therefore, we can add the requirement that is computable to the necessary and su cient condition for wait-free solvability. We do not pursue this line further, since we are interested in isolating the distributed coordination aspects of the problem from the sequential ones; hence we can allow each state machine to compute arbitrary (even non-computable) functions. The previous theorem provides a characterization of wait-free solvable tasks which depends only on the topological properties of hI n ; O n ; i. By results of 15, 21], it is undecidable whether a task is solvable. However, if protocols are bounded wait-free, i.e., have to decide within a predetermined number of steps, and the input complex is nite 4 , then producing all ISE divided images of the input complex (a nite number given the bound on the number of steps) is recursive. In this case, we can check if a simplicial map as required exists. As mentioned before, any divided image of a simplex contains a divided image which is connected (Appendix A). Since the ISE complex for an input simplex is a divided image of the input simplex, it also contains a connected divided image of the input simplex. However, translating Theorem 3.7 to combinatorial topology implies a stronger property of the ISE complex for an input simplex|it is connected itself: 4 There are tasks solvable by wait-free algorithms, but not by bounded wait-free algorithms 1, 17]. To prove the other direction of the claim, consider some 2 bound( ( i )), and we show 2 (bound( i )). Since bound( ( i )) is full to dimension i ? 1, is a face of some i?1 2 bound( ( i )). Since i?1 is external in ( i ), it is a face of a single i 2 ( i ). Therefore, if ids( i )?ids( i?1 ) = fp j g, then p j is unseen in the execution corresponding to i , by Lemma 5.5. Thus, p j 6 2 observed( i?1 ), and therefore, observed( i?1 ) = ids( i?1 ). By the de nition, i?1 2 ( i?1 ), and thus, i?1 2 (bound( i )). This implies that 2 (bound( i )). We have shown in Lemma 3.3 that the uncertainty about another process is restricted to its last seen round, if it is seen. Thus, once we x the views of all processes but one, the remaining process may have only one of two views, which translates into: Lemma 5.7 Consider an immediate snapshot execution complex E n . Let i 1 be an i-simplex of E n , corresponding to an execution , such that ids( ) = ids( i 1 ), and j 2 ids( i 1 ). If p j is seen in , then there exists exactly one other i-simplex of E n , i 2 , that di ers only in p j 's view. We already know that if p j is seen in an execution , then corresponds to an internal simplex. We now show that an internal (i ?1)-simplex is contained in exactly two i-simplexes, which implies that the ISE complex is a pseudomanifold. Lemma 5.8 For every simplex i 2 I n , ( i ) is an i-pseudomanifold. Proof: As noted before, ( i ) is full to dimension i. We show that any simplex i?1 2 ( i ), is contained in at most two i-simplexes. Let i 2 ( i ) be such that i?1 is a face of i . Since i?1 and i are properly colored by the ids, ids( i ) ? ids( i?1 ) = fjg, for some process p j . Furthermore, any i-simplex of ( i ) containing i?1 has a vertex colored with p j . Let be the pre x of an execution with steps by processes in ids( i ), corresponding to i . We can take such a pre x because observed( i ) = ids( i ). There are two cases: Case 1: p j is unseen in . Then observed( i?1 ) = ids( i?1 ). Since p j does not see an id not in ids( i ), its view is determined. Hence, i is unique. Case 2: p j is seen in . Let k be the last seen round of p j in . Lemma 5.7 implies that that there are only two possible views for p j which are compatible with the views in i?1 . Lemma 5.6 and Lemma 5.8 imply Condition (5) of De nition 4.1. Therefore, we have: Theorem 5.9 E n is a chromatic divided image of I n under . The complex induced by immediate snapshot executions of the full-information protocol for some input complex I n is called the full divided image of I n . We have the following necessary and su cient condition for wait-free solvability. Lemma 5.2 Condition (2) holds. Proof: Consider a simplex 2 E n . Let n 2 E n be such that n . Then there is a simplex n 2 I n with inputs( n ) = inputs( n ). Since ids( n ) observed( n ), then observed( n ) = ids( n ), and n 2 ( n ). Since is a face of n , 2 ( n ). Since the protocol is deterministic, we have: Recall, that a process p j is unseen in an execution if and only if there is no other execution that di ers only in p j 's view (Lemma 3.2). This implies: Lemma 5.5 Consider an immediate snapshot execution complex E n . Let i 1 be an i-simplex of ( i ) corresponding to an execution , and j 2 ids( i 1 Since the boundary corresponds to executions in which some processes are unseen, the above lemma can be used to prove that preserves the boundary. Lemma 5.6 For every simplex i 2 I n , (bound( i )) = bound( ( i )). Proof: To prove one direction, consider 2 (bound( i )); we need to show that 2 bound( ( i )). This means that 2 ( i?1 ), for some face i?1 of i . Since ( i?1 ) is full to dimension i ? 1, there exists some i?1 2 ( i?1 ) such that i?1 ; we shall show that i?1 2 bound( ( i )). It follows from the de nition of that i?1 2 ( i ). Since ( i ) is full to dimension i, there exists some i 2 ( i ) such that i?1 i . Since i?1 2 ( i?1 ), it follows that observed( i?1 ) = ids( i?1 ). Let p j be the process id in ids( i ) ? ids( i?1 ). Note that j 6 2 observed( i?1 ), that is, no process sees a step by p j in i?1 . Furthermore, in i , p j sees only steps by processes in ids( i ). Therefore, since the protocol is deterministic, there is only one possible view for p j . Namely, i?1 is contained in a single i-simplex i , and hence, i?1 2 bound( ( i )). Since is a face of i?1 and is closed under inclusion, 2 bound( ( i )). First, we need a few simple de nitions. For a simplex of I n , O n , or E n , let ids( ) be the set of ids appearing as the rst component of vertices in . For a simplex of I n , let inputs( ) be equal to . For a simplex of E n , let inputs( ) be the set of pairs of ids with inputs appearing (taking the input component from the state) in vertices of . For a simplex of E n , let views( ) be the set of views appearing in vertices of and let observed( ) be the set of ids of processes whose operations appear in views( ). Intuitively, if p i is not in observed( ), then the views in are the same as in an execution in which p i does not take a step. Notice that by de nition of observed, ids( ) observed( ), since a process always \observes itself." We can now de ne . Intuitively, ( ) is a subcomplex of the protocol complex, containing the to executions starting in the input simplex , and in which only processes appearing in are observed taking steps. De nition 5.1 For 2 I n , let ( ) be the complex containing all simplexes 2 E n such that inputs( ) = inputs( ), and observed( ) = ids( ), and all their faces. Lemma 5.1 For any 2 E n and 2 I n , 2 ( ) if and only if inputs( ) inputs( ), and observed( ) ids( ). The converse direction is more interesting. Assume inputs( ) inputs( ), and observed( ) ids( ). Since the protocol is wait-free, the processes in ids( ) ? ids( ) (if there are any) should be able to run on their own, after all processes in ids( ) have obtained the views in , and decide. This implies that there is an execution in which all processes in ids( ) ? ids( ) (if any) observe only processes in ids( ), and processes in ids( ) have the same views as in . Let be the simplex in E n that corresponds to this execution. Note that inputs( ) = inputs( ), and observed( ) = ids( ). Therefore, 2 ( ). Since is a face of , the claim follows. The protocol complex shown in Figure 3 includes every execution, not only immediate snapshot executions, and is not a divided image of the input complex, since the subcomplex of the protocol complex for the input simplex f(p; 0); (q; 0)g is not a pseudomanifold. However, the ISE complex is a divided image of the input complex, as we show now. Clearly, the process ids are a proper Sperner coloring of E n . We proceed to prove that the conditions of De nition 4.1 hold. Condition (1) Figure 4 : The immediate snapshot executions complex, where each process takes at most one step. We start this section by proving that the subcomplex induced by immediate snapshot executions is a chromatic divided image of the input complex. This implies a necessary condition for tasks which are solvable by a wait-free protocol; this condition is also su cient since immediate snapshot executions can be emulated in any execution. Later, we prove additional properties of the subcomplex induced by immediate snapshot executions: connectivity and orientability; these properties make our condition stronger, and allows to prove the lower bound for renaming. Denote the subcomplex of the protocol complex which contains all immediate snapshot executions by E n . For an input simplex n 2 I n , E n ( n ) is the subcomplex of all immediate snapshot executions starting with n . Figure 4 contains an example of an immediate snapshot executions (ISE) complex for a single input simplex (the one on the left), where each 2-simplex corresponds to an execution in which each process takes exactly one one step. There are simplexes that correspond to executions 1 and 2 from Figure 1 . Indeed, the vertices that correspond to p 1 and to p 2 are the same in these simplexes, i.e., p 1 and p 2 have the same views. Notice also that 1-simplexes on the boundary correspond to executions in which the corresponding two processes take one step each, and do not see the third process. The 0-simplexes on the corners correspond to \solo" executions in which the process sees only itself. We now show that if the protocol is wait-free and uses only read/write operations, then the ISE complex is a chromatic divided image of the input complex. This is done by de ning a function that assigns a subcomplex of E n to each simplex of I n . unique. However, if two executions, and 0 , satisfy the above condition for a simplex of dimension n, then and 0 must be indistinguishable to all processes. Moreover, if contains a vertex with id p i , and is a face of two n-simplexes 1 and 2 , corresponding to executions 1 and 2 , then 1 pi 2 . The protocol complex, P n , is the union of the complexes P n ( ), over all input n-simplexes . If a protocol is deterministic and wait-free then P n ( ) is nite, since a process must write an output value after a nite number of steps. Observe that the protocol complex depends not only on the possible interleavings of steps (schedules), but also on the transitions of processes and their local states. One can regard P n as colored with four colors|an id, an input value, a view, and an output value. Note that the ids coloring is proper. The protocol implies a decision map P : P n ! O n , which speci es the output value for each nal view of a process. When P solves it holds that if 2 P n then P ( ) corresponds to an output simplex. Therefore, P is simplicial and preserves the ids coloring. Furthermore, for any input n-simplex , P (P n ( )) is a complex. For example, Figure 3 shows an input complex and an output complex for two processes, p and q. Each vertex of the input (output) complex contains an id and an input (output) value. A task is de ned by stating : for input f(p; 1); (q; 0)g the output can be f(p; 1); (q; 0)g or f(p; 1); (q; 1)g; for input f(p; 0); (q; 1)g the output can be f(p; 0); (q; 0)g; for input f(p; 0); (q; 0)g the output can be f(p; 0); (q; 1)g, f(p; 2); (q; 1)g, f(p; 2); (q; 2)g, f(p; 0); (q; 2)g or f(p; 0); (q; 1)g. The gure also includes a protocol complex (with all executions, not only immediate snapshot executions) that solves the task. Here a vertex is labeled with an id, then an input value, and then the output value. For input f(p; 1); (q; 0)g, each process executes one read (of all the variables) and one write operation. For input f(p; 0); (q; 0)g, p executes one write then one read and then one write, while q executes one write and one read. For input f(p; 0); (q; 1)g, p executes one write then one read and then one write, while q does not execute any steps. There are various ways of assigning output values to the processes so that the protocol solves the task. The above de nitions imply: Proposition 4.3 P solves hI n ; O n ; i if and only if P (P n ( )) (M( )), for every nsimplex 2 I n . We say that P agrees with . This is the topological interpretation of the operational de nition of a protocol solving a task (presented at the end of Section 2). Since the protocol depends only on the input values (see Section 2), if two input n-simplexes , 0 , have the same input values, i.e., di er only by a permutation of the ids, then P n ( ) can be obtained from P n ( 0 ) by applying the same permutation to the ids. Therefore, the decision map must be anonymous; i.e., P (P n ( )) determines P (P n ( 0 )).  Here we cast the notion of task (introduced in Section 2) in terms of combinatorial topology. Denote ids = f0; : : :; ng. For some domain of values V , let P(V ) be the set of all pairs consisting of an id from ids and a value from V . For a domain of inputs I, an input complex, I n , is a complex that includes n-simplexes (i.e., subsets of n + 1 elements) of P(I) and all their faces, such that the vertices in an n-simplex have di erent id elds. For a domain of outputs O, an output complex, O n , is de ned similarly over O. That is, if (i; val) is a vertex of I n then val denotes an input value for process p i , while if (i; val) is a vertex of O n then val is an output value for process p i . Note that I n and O n are properly colored by the id elds, and are full to dimension n. In addition, each complex is colored (not necessarily properly) by the corresponding domain of values. Using the combinatorial topology notions, a task is identi ed with a triple hI n ; O n ; i; I n is an input complex, O n is an output complex, and maps each n-simplex of I n to a non-empty set of n-simplexes in O n . We sometimes mention only when I n and O n are clear from the context. The simplexes in ( n ) are the admissible output simplexes for n . Intuitively, if n is an input simplex and n 2 ( n ) is an admissible simplex, then n is an admissible output con guration when the system starts with input n . We extend to input simplexes of dimension smaller than n in the natural way. Recall that it must be possible to complete the outputs of some processes in an execution to outputs for all processes that are allowed for the inputs of the execution. Therefore, maps an input simplex of dimension smaller than n to the faces of n-simplexes in ( n ) with the same dimension and ids, for all input simplexes n that contain . Extended in this manner, (M( n )) is a subcomplex of O n . Remark. There is another variant of wait-free solvability, which allows to explicitly de ne for input simplexes of dimension smaller than n. This can be captured in our model by adding as part of the input a bit that tells the process whether to participate or not. Non-participating processes are required to output some default value. For an execution , the set f(0; j0); : : :; (n; jn)g is denoted views( ). Given a protocol P, the protocol complex, P n , is de ned over the minimal nal views reachable in executions of P, as follows. The n-simplexes of P n are the sets of minimal nal views( ), for every execution of P, and all their faces. The protocol complex for an input n-simplex , P n ( ), is the subcomplex of P n containing all n-simplexes corresponding to executions of P where processes start with inputs , and all their faces. The carrier of a simplex 2 K m , denoted carr( ), is the simplex 2 L m of smallest dimension such that 2 ( ). Intuitively, the carrier of a simplex is the \smallest" simplex in L m which is mapped to . By De nition 4.1(2), every simplex 2 K m is in ( ), for some 2 L m . By Lemma 4.1(ii), the carrier is unique. Therefore, the carrier is well-de ned. For example, in Figure 2 , the carrier of 1 is 1 , while the carrier of 2 is 2 .  Connectivity However, divided images di er from subdivisions, even if the requirement of connectivity is added. For example, a 2-dimensional torus with a triangle removed from its surface is a divided image of a 2-simplex, since its boundary is a 1-dimensional triangle. However it is neither an acyclic carrier nor a subdivided simplex since it has \holes" (non-trivial homology groups). Remark. The concept of a divided image is reminiscent of the notion of acyclic carrier 3 of 25], in that it associates subcomplexes of one complex to simplexes of another. Munkres uses acyclic carriers to study subdivisions, a fundamental concept of algebraic topology (cf. 25, 27]). Not to be confused with the notion of carrier de ned later. The dimension of a simplex , dim( ), is the number of its elements minus one. A simplex of dimension m (with m + 1 elements) is called an m-simplex. The dimension of a complex K is the maximum dimension of its simplexes; we only consider complexes of nite dimension. A complex of dimension m is called an m-complex. We sometimes use a superscript notation to denote the dimension of simplexes and complexes, e.g., m is an m-simplex and K m is an m-complex. The vertex set of K is the union of the 0-simplexes of K. We identify the 0-simplex fvg with v. Consider two complexes K and L. Let f be a function from the vertices of K to the vertices of L. f is simplicial if for every simplex fv 0 ; : : :; v k g of K, ff(v 0 ); : : :; f(v k )g is a simplex of L, where ff(v 0 ); : : :; f(v k )g is treated as a set (since f need not be one-to-one and there may be repetitions). A simplicial map f can be extended to all simplexes of K: a simplicial map f maps every simplex of K to a simplex f( ) (perhaps of smaller dimension) of L. We extend f to a set S of simplexes of K, by de ning f(S) to be the set of simplexes f( ) in L, where ranges over all simplexes of S. Clearly, if S is a subcomplex of K then f(S) is a subcomplex of L. In topology, pseudomanifolds are assumed to have additional properties, which we do not require for our applications. 12 same manner, we get an execution k 2 , in which all processes have the same input values as in 0 , and 2 k 2 . Therefore, the rest of the proof assumes that all processes have the same input values in and in 0 . Apply Corollary 3.5 and Corollary 3.6 to all concurrency classes of 2 to obtain an ISE with only singleton sets, flat ( 2 ), in which the processes appear in order according to indices; that is, flat( 2 ) = fp 1 g fp 2 g ; ; fp n g . Next, apply Corollary 3.5 and Corollary 3.6 to all concurrency classes of 0 2 to obtain flat( 0 2 We have that flat( 2 ) and flat( 0 2 ) are executions of the protocol, with minimal nal views. Since the protocol is deterministic each process decides within the same number of steps; since the views are minimal nal, this implies that each process appears in the same number of (singleton) concurrency classes in flat( 2 ) and in flat( 0 2 ). Therefore, flat( 2 ) and flat( 0 2 ) are equal, and hence, 0 . Note that the theorem is proved completely within the domain of distributed computing. We believe that the proof technique is interesting in itself; it resembles lower bounds, proved in the synchronous model, on the number of rounds necessary for solving consensus, e.g., 13, 24] or k-set consensus 11]. In this section we model distributed tasks using combinatorial topology; this is an adaptation of 22, 23] to our framework. We start with the basic topological concepts used in this paper. Previous papers in this area, e.g., 11, 19, 22, 23, 26], used geometric or algebraic interpretations of topological structures; in contrast, our approach is purely combinatorial, abstracting ideas from 16, 25, 27]. The basis of our de nitions is the notion of a complex. A complex K is a collection of nite nonempty sets closed under containment; that is, if is an element of K, then every nonempty subset of is an element of K. A nonempty subset of is a face of . A face of is proper if it is not equal to . Each element of a complex is called a simplex. A complex K 0 is a subcomplex of a complex K if K 0 K. Since a concurrency class does not specify the order in which processes appear, the corollary allows us to reorder singleton concurrency classes. That is, we can take a pair of singleton concurrency classes, fp i g; fp j g, (i 6 = j), join it by part (1) of Lemma 3.4 to get fp j ; p i g, and then use part (2) Proof of Lemma 3.4: We prove the lemma by induction on j 2 j. The base case is when j 2 j = 0, i.e., 2 is empty. Thus, s k is the last concurrency class, and the claim follows immediately from Lemma 3.3. For the induction step, assume the lemma holds for any 2 , of length <`, and prove it for 2 of length`. Denote 2 = s k+1 ; : : :; s k+`. We describe case (2); case (1) is similar. The idea is to turn k into the last seen round of p i , and then apply Lemma 3.3. By the induction hypothesis, we can repeatedly apply Corollary 3.5 to atten all later concurrency classes, s k+1 ; ; s k+`, one by one from k +`down to k + 1. Denote the resulting IS execution by 0 = 1 s k 00 2 , and note that 00 2 contains only singleton concurrency classes. Furthermore, 00 1 . By the induction hypothesis, we can also apply Corollary 3.6 to the singleton sets in 00 2 and move all steps by p i to the end of 00 2 . Denote by 000 the resulting IS execution. Note that 000 1 00 , and therefore, 000 Furthermore, k is the last seen round of p i in 000 , and therefore we can apply Lemma 3.3 to move p i before the rest of the processes in s k . This implies the lemma for Case (2). We can now state and prove the main result of this section: Theorem 3.7 If and 0 are two ISE of the same protocol with a common pre x then 0 . Proof: Denote = 2 and 0 = 0 2 . First, we show that we may assume, without loss of generality, that all processes have the same input values in and in 0 . Otherwise, assume some processes, p i1 ; : : :; p ik , do not have the same input values in and in 0 ; since processes write their state in their rst step, it follows that p i1 ; : : :; p ik do not have steps in . We change, for each j = 1; : : :; k, the input of p ij from its value in to its value in 0 . Apply Corollary 3.5 and Corollary 3.6 to 2 to obtain flat( 2 ) with p i1 appearing in the tail. Since p i1 does not have steps in , we can change its input to be its input value in 0 , without any process distinguishing between the executions. Thus, there is an execution We now show that 0 is the only immediate snapshot execution where p j 's view is minimal nal, which has this property. If s k 6 = fp j g (Case (2)), then clearly, there is another process p i 2 s k . If s k = fp j g (Case (1)), then there is another process p i 2 s k+1 : s k+1 is not empty and does not include p j . Moreover, if some s r , r > k, includes p j , then s r 0 = fp j g for every non-empty round, with r 0 r (otherwise, k ? 1 is the last seen round of p j ). In both cases, for any immediate snapshot execution 00 , which is not or 0 , 6 pi 00 , which proves the uniqueness of 0 . In the similar execution, 0 , we either add p j to the next concurrency class, or take p j into an earlier singleton concurrency class (by itself). Executions 1 and 2 in Figure 1 provide a simple example, where p 0 's rst step is either in a singleton class (the rst concurrency class in 2 ) or it is merged with the next class, with p 2 (the rst concurrency class in 2 ). Note that every process other than p j takes the same number of steps in both executions. Process p j distinguishes between the executions and may take a di erent number of steps until it decides. However, p j does not distinguish between the executions before its last seen round, and therefore, it may take a di erent number of steps only in its tail, that is, after its last seen round. Thus, only the length of the tail may change. The main theorem of this section is that any pair of IS executions with a common pre x are \transitively indistinguishable". Speci cally, two IS executions and 0 are -similar, denoted 0 , if there exist IS executions 0 ; : : :; r , and processes, p i1 ; : : :; p ir , such that Before proving the lemma, we state two corollaries of it. The rst corollary says that we can \ atten" a concurrency class, replacing it with a sequence of singleton sets with its processes. The corollary follows by repeatedly applying part (2) 9 We say that process p j is unseen in an execution , if there exists a round k, such that p j = 2 s r for every round r < k and s r = fp j g for every non-empty round r k. Intuitively, this means that no other process ever sees a step by p j . If p j is unseen in an execution, then its steps are taken after all processes no longer take steps. Lemma 3.2 Let be an immediate snapshot execution. If a process p j is unseen in then there does not exist an immediate snapshot execution 0 6 = , such that :pj 0 . Proof: Let = s 1 . Assume process p j is unseen in , but there exists an immediate snapshot execution 0 = s 0 1 6 = , such that :pj 0 . Let k be the round such that s r = fp j g for every r k and p j = 2 s r for every round r < k. Let l be the rst round in which and 0 di er, that is, s l 6 = s 0 l . If l k then s l = fp j g in , while in 0 , s 0 l must include some other process, p i ; however, p i distinguishes between and 0 , a contradiction. If l < k then p j 6 2 s l . Since no process in s l distinguishes between and 0 , then the same processes must be in s 0 l , again contradicting the assumption that s l 6 = s 0 l . If p j is not unseen in , then it is seen in some round. Formally, a process p j is seen in round k, if p j 2 s k , and for some r k, there exists some process p i 6 = p j that is in s r . If p j is seen, then the last seen round of p j is de ned to the largest k for which p j is seen in the k-th round. We denote by fp j g a nite (possibly empty) sequence of singleton concurrency classes, each one being fp j g; if there are`classes, then we write fp j g`. Suppose that = s 1 ; : : :; s l is an immediate snapshot execution in which a process p j is seen, and let s k be p j 's last seen round in . This implies that we can write = s 1 ; : : :; s r ; fp j g . The tail position of p j in is the smallest value of r for which can be written as s 1 ; : : :; s r ; fp j g ; fp j g is the tail. Note that if t is the tail position of p j in then s t 6 = fp j g and s r 0 = fp j g for every r 0 , t < r 0 l. Lemma 3.3 Let = 1 s k ; : : :; s l be an immediate snapshot execution in which a process p j is seen, and let s k be the last seen round of p j in with tail-position t. De Proof: Clearly, 0 :pj , in both cases. Notice that p j does distinguish between both executions, but no other process does, since p j cannot communicate with other processes (its steps afterwards are not seen). Given a protocol, and given initial states for the processes (input values), an immediate snapshot execution, , is completely characterized by the sequence of concurrency classes. Therefore, we can abuse notation and write = s 1 ; s 2 ; : : :; s l . Sometimes, it will be useful to see an immediate snapshot execution as a concatenation of two sequences of concurrency classes, and we write = 1 2 if 1 = s 1 ; s 2 ; : : :; s r and 2 = s r+1 ; s r+2 ; : : :; s l . The number of steps of p i in is the number of rounds in which it is active. Immediate snapshot executions are of interest because they capture the computational power of the model. Lemma 3.1 Let hI n ; O n ; i be a task. There exists a wait-free protocol which solves this task if and only if there exists a wait-free protocol which solves this task only in immediate snapshot executions. Sketch of proof: Assume there exists a protocol P which solves . Without loss of generality, we are assuming that in P each process is a full-information protocol. Since P solves , it must solve in immediate snapshot executions, which are a subset of all executions. The converse direction is proved by using a protocol for the participating set problem 7]. This implies that the immediate snapshot executions can be simulated in a full-information manner. Although they are very well-structured, immediate snapshot executions still contain uncertainty, since a process does not know exactly which processes are active in the last round. That is, if p i is active in round k and observes some other process p j to be active (i.e., perform a write), p i does not know whether p j is active in round k ? 1 or in round k. Consider, for example, the executions in Figure 1 . Only p 0 distinguishes between executions 1 and 2 ; p 1 and p 2 have the same views in both executions and cannot distinguish between them. (Note that p 0 distinguishes between 1 and 2 , since in 2 , p 0 reads the initial value in p 2 's register, while in 1 , p 0 reads the rst write of p 2 .) However, as we prove below (Lemma 3.3), this is the only uncertainty processes have in immediate snapshot executions of full-information protocols. 7 component to the input value and output value described above. The history component of p i consists of the sequence of operations executed so far by p i , and their results. Initially, the sequence is empty; after p i executes a write i operation, write is appended to the sequence; after it executes a read i (R j ), returning the value v, read j; v] is appended. Note that in a full-information protocol, the view of p i in a nite execution , ji, is equivalent to p i 's state at the last con guration of . Additionally, we assume protocols are in a standard form, as follows: Each process p i cycles through phases; in each phase, it rst writes its entire state to R i , and then reads R 0 ; : : :; R n (in some order). Since we consider only deterministic protocols, the state of a process is uniquely determined by its history component. In fact, the behavior of all full-information protocols is very similar; protocols di er only in what value a process decides on, and when the process makes the decision. Thus, the decision value is a function of the input component and the history component, and various protocols di er only in this function. Clearly, a task can be solved if and only if it can be solved by a full-information protocol. We restrict our attention to this class because we are only interested in studying task solvability, and disregard e ciency issues. In the sequel, all executions we consider are of full-information protocols. Below, we rely on the notion of executions that cannot be distinguished by a process; for full information protocols, this happens exactly when the process has the same view in both  As mentioned in Section 2, in this paper, we only consider only full-information protocols which are in standard form; we now restrict our attention to a speci c subset of the executions of such a protocol, called immediate snapshot executions. An immediate snapshot execution (in short, ISE) of a protocol is a sequence of rounds; the k-th round is speci ed by a concurrency class (called a block in 26]) of process ids, s k . The processes in s k are called active in round k. In round k, rst each active process performs a write operation (in increasing order of ids), and then each active process reads all the registers, i.e., performs n + 1 read operations (in increasing order of ids). Each concurrency class can be thought of as a concurrent write by every active process, followed by a concurrent atomic snapshot by every active process. We assume that concurrency classes are always non-empty. A protocol is a collection P of local protocols P 0 ; : : :; P n . An event of p i is denoted below simply by p i 's index, i. An execution of a system is a nite or in nite alternating sequence of con gurations and events C 0 ; j 1 ; C 1 ; : : :; C k?1 ; j k ; : : :, where C 0 is an initial con guration and C k is the result of applying the event j k to C k?1 , for all k 1. The schedule of this execution is j 1 ; : : :; j k ; : : :. Given an execution = C 0 ; j 1 ; C 1 ; : : :, and a process p i , the view of p i in , denoted ji is the sequence state i (C 0 ); state i (C 1 ); : : :. To model decision tasks, we identify two special components of each process's state: an input value and an output value. It is assumed that initial states di er only in the input values; moreover, the input value component never changes. If we want to have a local protocol which depends on the process id, then the id has to be provided explicitly as part of the input. The output value component is irrevocable, i.e., the protocol cannot over-write the output value. A protocol is wait-free if in any execution of the protocol, each process either has a nite number of events (i.e., takes a nite number of steps) or it writes an output value. This implies that if a process takes an in nite number of steps, it must eventually (after a nite number of steps) write an output value. Our de nitions do not require processes to halt|they decide and complete the computation of the decision task by writing to the output value component. Processes can either continue to take steps (which are irrelevant) or halt. We typically consider the steps of a process until it decides, and therefore, the above distinction does not mater. For the rest of the paper, we restrict our attention to full-information protocols, in which a process remembers everything and writes everything it knows. Formally, we add a history 5 Section 2) with the combinatorial topology concepts (Sections 4.2 and 4.3) . The necessary and su cient condition for wait-free solvability is developed in Section 5. Additional mathematics is developed in Section 6, and is later used in Section 7, to prove impossibility of wait-free solutions for renaming and set consensus, under speci c circumstances. The discussion is in Section 8. A system con guration consists of the states of the processes and registers. Formally, a con guration C is a vector hs 0 ; : : :; s n ; v 0 ; : : :; v n i where s i is the local state of process p i and v j is the value of the shared variable R j . Denote state i (C) = s i . Each shared variable may attain values from some domain which includes a special \unde ned" value, ?. An initial con guration is a con guration in which every local state is an initial state and all shared variables are set to ?. We consider an interleaving model of concurrency, where executions are modeled as sequences of steps. Each step is performed by a single process. In each step, a process p i performs either a write i operation or a read i (R j ) operation, but not both, performs some local computation, and changes to its next local state. The next con guration is the result of these modi cations. The state machine of each process p i models a local protocol, P i , that determines p i 's next step|P i determines whether p i is to write or read, and (in case of a read) which variable R j to read|as a function of p i 's local state. If p i reads R j , then P i determines p i 's next state as a function of p i 's current state and the value v read from R j . If p i writes to R i , then P i determines p i 's next state as a function of p i 's current state. We assume that all local protocols are identical; i.e., processes have the same state machine, which do not depend on the process id. If the local protocol has to depend on the id, then the id has to be encoded in the input (see discussion below in this section and in Section 4.3). 4 topology, our framework distills the properties that are required for the study of wait-free solvability. It does not require any previous topology background from the reader. The combinatorial topology framework we develop for wait-free solvability is related to the 1-failure model of Biran, Moran and Zaks 5]; while they use graphs and edges (sets of two vertices), we use complexes and simplexes (sets of one or more vertices). Herlihy and Shavit also use simplexes 22, 23], but often given a geometric interpretation and considered as subsets of Euclidean space; in our work, we always consider combinatorial structures. Divided images play a role similar to spans (both the geometric version used in 22, 23, 19], and the algebraic version introduced in 20]). As discussed later (after De nition 4.1) divided images have weaker mathematical properties than geometric spans, in particular, they may have \holes". We show that an orientable divided image corresponds, in a natural manner, to an algebraic span. In 22] it was shown that geometric spans exist, but the proof requires a combination of algebraic (homology theory) and geometric (subdivided simplexes) arguments. The notion of immediate snapshot executions was introduced simultaneously by Borowsky and Gafni 6] and by Saks and Zaharoglou 26]. Many of the ideas needed to show that immediate snapshot executions induce a divided image already appeared in these works; of particular relevance to us is the more combinatorial approach of 6]. However, the goal of these papers was to prove the impossibility result for set consensus, and hence they centered on properties of immediate snapshot executions needed to prove this result. For this result it is not necessary to show that they are connected and orientable (properties used here for the renaming impossibility) or that they induce an algebraic span (or our simpler combinatorial notion of a divided image). No general conditions for wait-free solvability were derived from them, and no general model, like the one developed here, has appeared before. The necessary and su cient condition for wait-free solvability we derive is not exactly the same as the one proved by Herlihy and Shavit in 23]. On one hand, we explicitly construct a speci c well-structured divided image (induced by immediate snapshot executions), while Herlihy and Shavit show that an arbitrary span exists 22]. On the other hand, Herlihy and Shavit prove that the existence of a span (which is a natural topological structure) implies wait-free solvability 23], while our condition requires the exitence of a speci c divided image, induced by immediate snapshot executions. The rest of this paper is organized as follows. In Section 2 we describe the distributed computing model. In Section 3 we de ne immediate snapshot executions and study their properties. Section 4 starts with the topology concepts used in the rest of the paper, (Section 4.1) and then, we show we show how to model a task and a distributed computing system (described in 3 To provide a feeling for the mathematical framework we develop, we present the following rough description of key notions from combinatorial topology. A colored simplex is a set, in which each of the elements, called vertices, is colored with a process id. A colored complex is a collection of colored simplexes which is closed under containment. A mapping from the vertices of one colored complex to the vertices of another is simplicial if it maps a simplex to a simplex; it is color preserving if a vertex with id p i is mapped to vertex with id p i . Finally, a complex whose largest simplex contains m vertices is a pseudomanifold if every simplex with m?1 vertices is contained in either one or two simplexes with m vertices. Precise de nitions appear in Section 4.1; they do not rely on algebraic or geometric interpretations. The novel combinatorial concept we use is of a pseudomanifold being a divided image of a simplex. Very roughly, a pseudomanifold is a divided image of a simplex if it has the same boundary as the simplex. The divided image preserves some of (but not all) the topological structure of the simplex. We prove a new necessary condition for wait-free solvability (Theorem 5.9): if a task is wait-free solvable, then there exists a divided image of the complex of possible inputs; it is straightforward to see that the decisions made by the protocol must induce a simplicial map from this divided image to the complex of possible outputs which must agree with the task speci cation. We then present a necessary and su cient condition for wait-free solvability, i.e., a characterization of the wait-free solvable tasks. Consider a task, and a wait-free protocol that solves it. We explicitly show that a subset of the protocol's executions, called immediate snapshot executions 6, 26], induce a divided image of the complex of possible inputs. We use a solution for the participating set problem 7] to show that the above property is also su cient. Namely, if there exists a simplicial map from a divided image induced by immediate snapshots executions to the output complex which agrees with the task, then the problem is wait-free solvable. We prove that the divided image induced by immediate snapshot executions is orientable and connected. We then prove a combinatorial theorem about the number of monochromatic simplexes in any binary coloring of an orientable and connected divided image. This theorem is the key to a completely combinatorial proof that M-renaming is wait-free solvable only if M 2n. Using the standard Sperner's Lemma, we also show that k-set consensus is wait-free solvable only if k > n. (Both bounds are known to be tight, see 2] and 10], respectively.) The main contribution of this paper, in our opinion, is in providing an alternative, combinatorial framework in which further research related to distributed solvability can be pursued. 1 We believe our work is the rst to provide a completely self-contained and elementary, yet rigorous, treatment of this topic. From ideas that were developed in great generality in algebraic 1 In his tutorial, Herlihy 18, Remark 4.1] says: \: : : No doubt one could prove these results in a purely combinatorial way, but no one knows how. Even if we knew how, fully combinatorial proofs would probably not be as succinct and intuitively appealing : : : " Our results indicate that combinatorial proofs of these results can be fairly accessible. This paper studies the tasks that can be solved by a wait-free protocol in shared-memory asynchronous systems. A shared-memory system consists of n + 1 processes that communicate by reading and writing shared variables; here we assume only atomic read/write registers. We also assume that processes are completely asynchronous, i.e., each process runs at a completely arbitrary speed. Processes start with inputs and, after performing some protocol, have to decide on some outputs. A task speci es the sets of outputs that are allowable for each assignment of inputs to processes. A protocol is wait-free if each process halts with an output within a nite number of its own steps, regardless of the behavior of other processes. A task is wait-free solvable if there exists a wait-free protocol that solves it. The study of wait-free solvable tasks has been central to the theory of distributed computing. Early research studied speci c tasks and showed them to be solvable (e.g., approximate agreement 12], 2n-renaming 2], k-set consensus with at most k ?1 failures 10]) or unsolvable (e.g., consensus 14], n + 1-renaming 2]). In 1988, a necessary and su cient condition for the solvability of a task in the presence of a single process failure was presented 5]. In 1993, a signi cant advancement was made in the understanding of wait-free solvability 6, 22, 26]. This advancement yielded new impossibility results for k-set consensus ( 6, 22, 26], and later 9, 19, 20]) and renaming 22, 20], as well as a necessary and su cient condition for wait-free solvability 22, 23]. Of particular interest was the use of topological notions to investigate the problem, suggested in 22, 26] (and implicitly in 6]). Yet, much of this development remained inaccessible to many researchers, since it relied on algebraic and geometric tools of topology. Furthermore, di erent topology techniques were used in each of these works: For example, a direct, combinatorial application of Sperner's Lemma in 6], a more involved form of Brouwer xed point theorem in 26], and a combination of continuous and algebraic tools of simplicial approximation and Mayer-Vietoris sequences in 22]. In this paper, we present a self-contained study of wait-free solvable tasks starting from rst principles. We introduce a new necessary and su cient condition for wait-free solvability. This condition is used to prove the impossibility of solving the renaming and the k-set consensus problems under speci c circumstances. It is also used to derive an extension of the necessary condition of 5]. Our approach borrows critical ideas from previous works in this area, especially, 6, 7, 22, 23, 26], and integrates them into a uni ed framework. Our goal was to deepen the understanding of the wait-free solvability problem; in particular, to learn which tools of topology are needed to investigate this problem. We develop the rst detailed formal model that captures wait-free solvability in terms of combinatorial mathematics, inspired by topology.  This paper presents a self-contained study of wait-free solvable tasks. A new necessary and su cient condition for wait-free solvability is proved, providing a characterization of the wait-free solvable tasks. The condition is based on a restricted set of executions, which induce a very simple to understand structure. The necessary condition is used to prove tight bounds for renaming and k-set consensus. The framework is based on topology, but uses only elementary combinatorics, and, in contrast to previous works, does not rely on algebraic or geometric arguments.
The multi-round (single shared memory array) IS protocol complex is harder to analyze, combinatorially it can be shown to be a pseudomanifold REF .