The Combinatorial Structure of Wait-Free Solvable Tasks.
This paper presents a self-contained study of wait-free solvable tasks. A new necessary condition for wait-free solvability, based on a restricted set of executions, is proved. This set of executions induces a very simple-to-understand structure, which is used to prove tight bounds for k-set consensus and renaming. 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.
Introduction
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
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 halt with some
outputs. A task specifies 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 finite 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 specific tasks and showed them to be
solvable (e.g., approximate agreement [9], 2n-renaming [2], k-set consensus with
at most k \Gamma 1 failures [7]) or unsolvable (e.g., consensus [10], n+1-renaming [2]).
A necessary and sufficient condition for the solvability of a task in the presence
of one process failure was presented in [3]. In 1993, a significant advancement
??? Supported by grant No. 92-0233 from the United States-Israel Binational Science
Foundation (BSF), Jerusalem, Israel, and the fund for the promotion of research in
the Technion. Email: hagit@cs.technion.ac.il.
y Part of this work was done while visiting the MIT Laboratory for Computer Science,
and the Cambridge Research Laboratory of DEC. Supported by CONACyT and
DGAPA Projects, UNAM. Email: rajsbaum@servidor.unam.mx.
was made in the understanding of this problem with [4, 17, 20]. This advancement
yielded new impossibility results for k-set consensus ([4, 17, 20], and later
[6, 14, 15]) and renaming ([17, 15]), as well as a necessary and sufficient condition
for wait-free solvability ([17, 18]). Of particular interest was the use of
topological notions to investigate the problem, suggested in [17, 20]. Yet, much
of this development remained inaccessible to many researchers, since it relied on
algebraic and geometric tools of topology.
In this paper, we present a self-contained study of wait-free solvable tasks
starting from first principles. We introduce a new necessary and sufficient condition
for wait-free solvability. This condition is used to prove tight bounds on
renaming and k-set consensus. It is also used to derive an extension of the necessary
condition of [3]. Our approach borrows critical ideas from previous works
in this area (especially, [4, 5, 17, 18, 20]), and integrates them into a unified
framework. Below we discuss the relationships between our work and previous
work.
To provide a feeling for our results, 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
is contained in either one or two simplexes with m vertices. Precise definitions
appear in Section 3; 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 (Corollary 13): 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 specification.
We present a necessary and sufficient 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 [4, 20], induce a divided image
of the complex of possible inputs. We use a solution for the participating set
problem ([5]) to show that the above property is also sufficient. 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. We then prove a combinatorial theorem which extends Sperner's
Lemma (for orientable divided images). This theorem is the key to a completely
combinatorial proof that M-renaming is wait-free solvable only if M - 2n.
Using the basic Sperner's Lemma, we also show that k-set consensus is wait-free
solvable only if k ? n. (These bounds are known to be tight, see [2] and [7],
respectively.)
Divided images play a role similar to spans (both the geometric version used
in [17, 18, 14], and the algebraic version introduced in [15]). As discussed below
(after Definition 1) divided images have weaker mathematical properties than
geometric spans, in particular, they may have "holes". We show (in the full version
of the paper) that an orientable divided image corresponds in a natural
manner to an algebraic span. It was shown that such spans exist (in [17]), but
this proof requires a combination of algebraic (homology theory) and geometric
(subdivided simplexes) arguments. The existence of algebraic spans with certain
properties imply impossibilities of set consensus and renaming [15], without
relying on the more involved arguments of [17].
The necessary and sufficient condition we derive is not exactly the same as the
one proved by Herlihy and Shavit in [18]. We explicitly construct a specific well-structured
divided image (induced by immediate snapshot executions), while
Herlihy and Shavit show that an arbitrary span exists ([17]). The notion of
immediate snapshot executions was introduced in [4, 20]. The basic ideas needed
to show that immediate snapshot executions induce a divided image already
appeared in Borowsky and Gafni's paper [4]. However, they were interested in
properties of immediate snapshot executions to prove the impossibility result for
set consensus. It was not shown that they are orientable (a property used for the
renaming impossibility) or that they induce an algebraic span (or our simpler
combinatorial notion of a divided image), and no general conditions for wait-free
solvability were derived from them.
In the full version of this paper, we derive another necessary condition for
wait-free solvability from Corollary 13, of a different nature. This condition is
based on connectivity, and is therefore computable. This condition extends the
condition for solvability in the presence of one failure [3]. It follows from [11,
16] that there is no computable necessary and sufficient condition for wait-free
solvability.
2 Model of Computation
Our model is standard and was used in many papers; we follow [1].
A system consists of n Each process is a deterministic
state machine, with a possibly infinite number of states. We associate with
each process a set of local states. Among the states of each process is a subset
called the initial states and another subset called the output states. Processes
communicate by means of a finite number of single-writer multi-reader atomic
registers (also called shared variables). No assumption is made regarding the size
of the registers, and therefore we may assume that each process p i has only one
register R i . Each process p i has two atomic operations available to it:
its entire state to R i .
reads the shared variable R and returns its value v.
A system configuration consists of the states of the processes and registers.
Formally, a configuration C is a vector hs is the
local state of process p i and v j is the value of the shared variable R j . Denote
state Each shared variable may attain values from some domain which
includes a special "undefined" value, ?. An initial configuration is a configuration
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) operation, but
not both, performs some local computation, and changes to its next local state.
The next configuration is the result of these modifications.
We assume that each process p i follows a local protocol P i that deterministically
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 to read, as a function of p i 's local state. If
next state as a function of p i 's current state
and the value v read from R. If p i writes R, then P i determines p i 's next state
and as a function of p i 's current state. We assume that all local protocols are
identical, i.e., depend only on the state, but not on the process id. A protocol is
a collection P of local protocols P
An event of p i is simply p i 's index i. A schedule is a finite or infinite sequence
of events. An execution is a finite or infinite alternating sequence of configurations
and events C is the initial configuration and
C k is the result of applying the event j k to C k\Gamma1 , for all k - 1. The schedule of
this execution is
Given an execution and a process p i , the view of p i in ff,
denoted ffji is the sequence state i (C 0 ); state i (C Intuitively, for example, if
decides in ff without taking any steps, then the only information contained
in ffji is p i 's initial state.
A process p i is faulty in an infinite schedule oe if it takes a finite number of
steps (i.e., has a finite number of events) in oe, and nonfaulty otherwise. These
definitions also apply to executions by means of their schedules.
We assume that each process has two special parts of its state, an input value
and an output value. Initial configurations differ only in the input values of the
processes. 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. We assume that
the output value is irrevocable, i.e., the protocol cannot over-write the output
value. Note that in our definition processes do not halt; they decide by writing
the output value, but continue to take steps (which are irrelevant).
task \Delta has some domain I of input values and domain O of output values;
specifies for each assignment of input values to the processes which output
values can be written by the processes. A protocol solves \Delta if for any finite
execution, the output values already written by the processes can be completed
(in any infinite extension of the execution where all processes are nonfaulty)
to output values for all processes that are allowable for the input values in the
execution. The protocol is wait-free if every nonfaulty process eventually writes
an output value.
3 Combinatorial Topology Concepts
In this section, we introduce the basic topological concepts we use in this pa-
per. Previous papers in this area, e.g., [8, 14, 17, 18, 20], used geometric or
algebraic interpretations of topological structures; in contrast, our approach is
purely combinatorial, abstracting ideas from [12, 19, 21].
Basic Notions: The basis of our definitions is the notion of a complex. A complex
K is a collection of finite nonempty sets closed under containment; that is, if
oe is an element of K, then every nonempty subset of oe is an element of K. A
nonempty subset of oe is a face of oe. A face of oe is proper if it is not equal to oe.
Each element of a complex is called a simplex. A complex K 0 is a subcomplex of
a complex K if K 0 ' K.
The dimension of a simplex oe, dim(oe), 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 finite 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., oe 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
vertex v and the 0-simplex fvg.
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 of K,
is a simplex of L. (Note that ff(v 0 treated as
a set, since f need not be one-to-one and there may be repetitions.) This implies
that a simplicial map f can be extended to all simplexes of K. Intuitively, a
simplicial map f maps every simplex oe of K to a simplex f(oe) (perhaps of
smaller dimension) of L. We extend f to a set of simplexes of K, S, by defining
f(S) to be the set of simplexes f(oe) in L, where oe ranges over all simplexes of
S. Clearly, if S is a subcomplex of K then f(S) is a subcomplex of L.
Divided Images: An m-complex K m is full to dimension m if every simplex of
K m is contained in some m-simplex of K m .
Let K m be a complex full to dimension m. An (m \Gamma 1)-simplex of K m is
external if it is contained in exactly one m-simplex; otherwise, it is internal. The
boundary complex of K m , denoted bound(K m ), is the subcomplex containing all
the faces of external simplexes of K m . Clearly, bound(K m ) is full to dimension
Abusing notation, let bound(oe m ) be the set of (m \Gamma 1)-faces of simplex
oe m .
A complex K m is an m-pseudomanifold, if it is full to dimension m and every
contained in either one or two m-simplexes. 5 An m-manifold
is an m-pseudomanifold in which every (m \Gamma 1)-simplex is contained in two
m-simplexes, i.e., it has no external simplexes.
The following combinatorial definition will play a key role later when we cast
the structure of a protocol in the topological framework.
be a complex. A complex K m is a weak divided image of
there exists a function / that assigns to each simplex of L m a subcomplex
of K m , such that:
1. for every - 2 K m there exists a simplex oe 2 L m such that - 2 /(oe),
2. for every oe single vertex, and
3. for every oe; oe assume that
K m is a divided image of L m if it also satisfies the following condition:
4. for every oe 2 L m , /(oe) is a dim(oe)-pseudomanifold with
We say that K m is a divided image of L m under /.
Intuitively, a divided image is obtained from L m by replacing each simplex of
with a pseudomanifold, making sure that they "fit together" (in the sense of
Condition 3). In addition, Condition 1 guarantees that / maps
Condition 2 guarantees that / maps vertices of L m to vertices of K finally,
Condition 4 guarantees that / preserves the dimension and the boundary of
simplexes in L m .
Fig. 1 shows an example of the divided image of a complex containing two
simplexes. In the figure, solid lines show the boundary of L 2 and their image
under /, in K 2 .
Consider a set oe m and let M (oe m ) be the complex consisting of oe m and all its
proper subsets; M (oe m ) is an m-pseudomanifold consisting of a single m-simplex
and all its faces. Of particular importance for us is the case where K m is a
divided image of M (oe m ). In this case, /(oe m
Remark. The concept of a divided image is reminiscent of the notion of acyclic
carrier 7 of [19], 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. [19, 21]). However, divided images differ 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
5 In algebraic topology, pseudomanifolds are assumed to have additional properties,
which we do not require for our applications.
6 Notice that bound(oe) is a set of simplexes, and /(bound(oe)) is the complex which is
the union over these simplexes - of /(- ).
7 Not to be confused with the notion of carrier defined later.
Fig. 1. K 2 is a divided image of L 2 under /.
neither an acyclic carrier nor a subdivided simplex since it has "holes" (non-
trivial homology groups).
The next proposition states some simple properties of divided images; its
proof is left to the full paper.
Proposition2. Let K m be a divided image of L m under /.
(i) For every oe, oe
(ii) For every pair of j-simplexes oe j; oe j2 L m , if oe j6= oe j
2 , and oe j" oe j6= ;, then
is a pseudomanifold of dimension strictly smaller than j.
(iii) For every i-simplex oe divided image of M (oe i ) under
(iv) A simplex - external if and only if for some external simplex
oe
The carrier of a simplex - 2 K m , denoted carr(- ), is the simplex oe 2 L m of
smallest dimension such that - 2 /(oe). Intuitively, the carrier of a simplex - is
the "smallest" simplex in L m which is mapped to - . By Definition 1(1), every
simplex - 2 K m is in /(oe), for some oe 2 L m . By Proposition 2(ii), the carrier
is unique. Therefore, the carrier is well-defined.
Connectivity: For any j, 0 m, the j-graph of K m consists of one vertex
for every j-simplex of K m , and there is an edge between two vertices if and only
if their intersection is a (j \Gamma 1)-simplex of K m . K m is j-connected if its j-graph
is connected; K m is 0-connected if it consists of a single vertex.
Lemma 3. Let K m be a divided image of oe m under /. There exists a complex
~
/, a restriction of / to ~
K m is a divided
image of oe m under ~
for every i ? 1, and every oe i 2 oe m .
Colorings: A complex K is colored by associating a value from some set of colors
with each of its vertices. A coloring is proper if different vertices in the same
simplex have different colors. A simplicial preserving if
for every vertex v of K, that if a coloring is proper
and a simplicial map is color preserving, then for any simplex fv the
vertices are different, i.e., f(oe) is of the same dimension as oe.
Let K m be a divided image of L m . A simplicial map
Sperner coloring if for every v 2 K m , -(v) 2 carr(v). Intuitively, - "folds" K m
into L m with the requirement that each vertex of K m goes to a vertex of its
carrier. The main combinatorial definition we use is:
A complex K m is a (weak) chromatic divided image of L m , if it
is a (weak) divided image of L m with a proper Sperner coloring -.
Let K m be a divided image of M (oe m ). The next well-known lemma says that
an odd number of m-simplexes of K m must go to oe m (and in particular, at least
one simplex). This lemma is used in Section 7; it follows from the Index Lemma
(Lemma 17), presented later.
Lemma 5 (Sperner Lemma). Consider a divided image K m of M (oe m ) under
/, and a Sperner coloring - : K There exists an odd number of
Modeling Tasks and Protocols
In this section we model distributed tasks using combinatorial topology; this is
an adaptation of [17, 18] to our framework.
Tasks: Denote ids 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 different id fields. For a domain of outputs O,
an output complex, O n , is defined 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 fields, 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 identified with a triple
I n is an input complex, O n is an output complex, and \Delta maps
each n-simplex of I n to a non-empty set of n-simplexes in O n . We sometimes
mention only \Delta when I n and O n are clear from the context. The simplexes in
\Delta(oe n ) are the admissible output simplexes for oe n . Intuitively, if oe n is an input
simplex and - n 2 \Delta(oe n ) is an admissible simplex, then - n is an admissible
output configuration when the system starts with input oe n .
We extend \Delta to simplexes of dimension smaller than n, i.e., for executions in
which n processes or less take steps, as follows. 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, \Delta maps
an input simplex oe of dimension smaller than n to the faces of n-simplexes in
\Delta(oe n ) with the same dimension and ids, for all input simplexes oe n that contain
oe. Extended in this manner, \Delta(M (oe n )) is a subcomplex of O n . There is another
variant of wait-free solvability, which allows to explicitly define \Delta for 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.
Protocol Complexes: We say that a view of a process is final if the process has
written an output. For an execution ff, the set f(0;
views(ff). Given a protocol P, the protocol complex, P n , is defined over the final
views reachable in executions of P, as follows. An n-simplex of final views is in P n
if and only if it is views(ff) for some execution ff of P. In addition, P n contains
all the faces of the n-simplexes. The protocol complex for an input n-simplex
oe, P n (oe), is the subcomplex of P n containing all n-simplexes corresponding
to executions of P where processes start with inputs oe, and all their faces.
Intuitively, only if there exists an execution ff with initial
values oe, such that the views of processes in - are the same as in ff. Note
however that ff is not necessarily unique.
The protocol complex, P n , is the union of the complexes P n (oe), over all input
n-simplexes oe. If a protocol is wait-free then P n (oe) is finite, since a process
terminates after a finite 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 which specifies the
output value for each final view of a process. When P solves \Delta it holds that if - 2
corresponds to an output simplex. Therefore, ffi P is simplicial and
preserves the ids coloring. Furthermore, for any input n-simplex oe, ffi P (P n (oe))
is a complex.
Since the protocol depends only on the input values, if two input n-simplexes
oe, oe 0 , have the same input values, i.e., differ only by a permutation of the ids,
then P n (oe) can be obtained from P n (oe 0 ) by applying the same permutation
to the ids. Therefore, the decision map must be anonymous; i.e., ffi P (P n (oe))
determines ffi P (P n (oe 0 )). If the protocol has to depend on the ids, then they have
to be given as part of the inputs.
The above definitions imply:
solves hI n ; O n ; \Deltai if and only if ffi P (P n (oe)) ' \Delta(M (oe)), for every
n-simplex oe 2 I n .
We say that agrees with \Delta.
Round
(a) Execution ff 1 .
Round
(b) Execution ff 2 .
Fig. 2. Executions ff 1 and ff 2 are indistinguishable to p1 and p2 .
This is the topological interpretation of the operational definition of a protocol
solving a task (presented at the end of Section 2).
5 A Condition for Wait-Free Solvability
In this section we define immediate snapshot executions and prove that the
subcomplex they induce 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 sufficient since immediate snapshot executions
can be emulated in any execution.
An immediate snapshot execution (in short, ISE) of a protocol is a sequence
of rounds, defined as follows. Round k is specified by a concurrency class (called
a block in [20]) of process ids, s k . The processes in s k are called active in round
k. In round k, first each active process performs a write operation (in increasing
order of ids), and then each active process reads all the registers, i.e., performs
operations (in increasing order of ids). We assume that the concurrency
class is always non-empty. It can be seen that, for a given protocol, an
immediate snapshot execution, ff, is completely characterized by the sequence
of concurrency classes. Therefore, we can write
Immediate snapshot executions are of interest because they capture the computational
power of the model. That is, a task \Delta is wait-free solvable if and only
if there exists a wait-free protocol which solves \Delta in immediate snapshot executions
(this is shown as part of the proof of Theorem 14 below). Although they are
very well-structured, immediate snapshot executions still contain some degree of
uncertainty, since a process does not know exactly which processes are active in
the last round 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 \Gamma 1 or in round k.
Consider for example, Fig. 2. Only p 0 distinguishes between executions ff 1
and have the same views in both executions and cannot distinguish
between them. However, as we prove below (in Proposition 8) this is the only
uncertainty processes have in immediate snapshot executions.
Denote the subcomplex of the protocol complex which contains all immediate
snapshot executions by E n . For an input simplex oe n 2 I n , E n (oe n ) is the
subcomplex of all immediate snapshot executions starting with oe n .
Fig. 3. The ISE complex, when each process takes at most one step.
We now show that if the protocol is wait-free and uses only read/write op-
erations, then the ISE complex is a divided image of the input complex. This is
done by defining a function / that assigns a subcomplex of E n to each simplex
of I n .
Fig. 3 contains an example of an immediate snapshot executions complex for
a single input simplex. This is the complex where each process takes at most one
step. Note that there are simplexes that correspond to the executions ff 1 and ff 2
from Fig. 2. 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.
First, we need a few simple definitions. For a simplex oe of I n , O n , or E n ,
let ids(oe) be the set of ids appearing in vertices of oe. For a simplex oe of I n or
inputs(oe) be the set of pairs of inputs with corresponding ids appearing
in vertices of oe. Finally, for a simplex oe of E n , let views(oe) be the set of views
appearing in vertices of oe and let observed(oe) be the set of ids of processes whose
operations appear in views(oe). 8 Intuitively, if p i is not in observed(oe), then the
views in oe are the same as in an execution in which p i does not take a step.
Notice that ids(- ) ' observed(- ), since a process always "observes itself."
We can now define /. For oe 2 I n , /(oe) is the complex containing all
simplexes
faces. Notice that /(oe) is full to dimension
dim(oe). A fact we use later is:
Proposition6. For any - 2 E n and oe 2 I n , - 2 /(oe) if and only if ids(-
Proof. If - 0 is a face of - , then ids(- 0
Thus, the definition of / implies that if - 2 /(oe)
then ids(-
8 Recall that these ids are not known by the processes', unless explicitly given in the
inputs. To make this definition concrete, a special part of the process' state captures
its identity. We defer the exact details to the full version.
ids(oe). Since the protocol is wait-free, there exists an execution in which all processes
in only processes in ids(oe), and processes
in ids(- ) have the same views as in - . Let - the simplex in E n that corresponds
to this execution. Note that
and is a face of -, the claim
follows. ut
We first show that the ISE complex is a weak divided image of the input
complex. In fact, this property does not depend on the protocol being wait-free
or on the type of memory operations used, i.e., that the protocol uses only atomic
read/write operations.
Lemma 7. E n is a weak chromatic divided image of I n under /.
Proof. Clearly, the process ids are a proper Sperner coloring of E n . We proceed
to prove that the three conditions of weak divided images (Definition 1) hold.
Condition (1): Consider a simplex be such that - n . Then
there is a simplex oe n 2 I n with ids(- n
is a face of - n , - 2 /(oe n ).
Condition (2) follows since the protocol is deterministic.
Condition (3) follows from Proposition
happens
if and only if -
We say that process p j is silent in an execution ff, if there exists a round
for every round r - k.
Intuitively, this means that no other process ever sees a step by p j . If p j is not
silent in ff, then it is seen in some round. Formally, a process p j is seen in round
k, and there exists some process p 0
. The last seen round of p j is the largest round k in which p j is seen.
These definitions imply:
Proposition8. Consider a finite immediate snapshot execution ff. If p j is not
silent in ff, then k is the last seen round of p j in ff if and only if (a) s for
every round r ? k, (b) s k 6= fp j g, and (c) either (i) g.
As a consequence, we have the next lemma.
Lemma 9. Consider an immediate snapshot execution complex E n . Let - i
1 be an
i-simplex of E n corresponding to an execution ff, and p i 2 ids(- i).
(i) If p i is not silent in ff, then there exists - i
another i-simplex of E n , that
differs only in p i 's view, corresponding to ff 0 .
(ii) If there exists - i
another i-simplex of E n , that differs only in p i 's view,
corresponding to ff 0 , then p j is not silent in ff; ff 0 . If k is the last seen round
of p j in ff, then, without loss of generality, p j is in the kth concurrency class
of - i
1 and the kth concurrency class of - i
2 is fp j g.
Lemma 10. For every simplex oe
Proof. Let
It follows from the definition of /
that - To show that -
notice that observed(- be a process id
in ids(oe i sees a step by p j , and in - i ,
does not see a step by any process not in ids(oe i ), it follows that p j 's view is
determined (because the protocol is deterministic). Namely, - i\Gamma1 is contained in
a single i-simplex - i , and hence - is a face of -
by the definition of /, - 2 bound(/(oe i )).
The other direction of the proof is similar. Since - 2 bound(/(oe i
that - is a face of some - This implies that - i\Gamma1 is a face of a
single is not in observed(-
(by Lemma 9(i)). Hence, observed(- It follows that -
This implies that - 2 /(bound(oe i )). ut
Intuitively, the next lemma implies that once we fix the views of all processes
but one, the remaining process may have only one of two views, which correspond
to the two options in Proposition 8(c). This shows that the uncertainty about
another process is restricted to its last seen round.
Lemma 11. For every simplex oe i 2 I n , /(oe i ) is an i-pseudomanifold.
Proof. As noted before, /(oe i ) is full to dimension i. We show that any simplex
contained in at most two i-simplexes. Let - i 2 /(oe i ) be such
that - i\Gamma1 is a face of - i . Since - i\Gamma1 and - i are properly colored by the ids, there
exists some id p j , such that p j appears in - i but not in - i\Gamma1 . In fact, any i-
simplex of /(oe i includes p j . Let ff be the prefix of an execution
with steps by processes in ids(oe i ), corresponding to - i . We can take such a prefix
because There are two cases:
Case 1: p j is silent in ff. Then observed(- does not see
an id not in ids(oe i ), its view is determined. Hence, - i is unique.
Case 2: p j is not silent in ff. Let k be the last seen round of p j in ff. Lemma 9(ii)
implies that that there are only two possible views for compatible with the
views in - g. ut
By Lemma 7, E n is a weak chromatic divided image of I n . Lemma 11 and
imply Condition (4) of Definition 1. Therefore, we have:
Theorem12. E n is a chromatic divided image of I n under /.
This implies the following necessary condition for wait-free solvability:
\Deltai be a task. If there exists a wait-free protocol
which solves this task then there exists a chromatic divided image E n of I n and
a color-preserving (on ids), anonymous simplicial map ffi from E n to O n that
agrees with \Delta.
We now restrict our attention to full-information protocols, in which a process
writes its whole state in every write to its shared register. 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 sufficient condition for wait-free solvability.
Theorem 14. Let hI n ; O n ; \Deltai be a task. There exists a wait-free protocol which
solves this task if and only if there exists an full divided image E n of I n and
a color-preserving (on ids), anonymous simplicial map ffi from E n to O n that
agrees with \Delta.
Sketch of proof. Assume there exists a protocol P which solves \Delta. Without loss
of generality, we may assume that in P each process operates by writing and
then reading the registers R solves \Delta, it must solve \Delta in immediate
snapshot executions. By Theorem 12, 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, ffi P is a color-preserving (on ids), anonymous simplicial map from
to O n that agrees with \Delta.
Assume there exists an full divided image E n of I n and a color-preserving
(on ids), anonymous simplicial map ffi from E n to O n that agrees with \Delta. By
using a protocol for the participating set problem ([5]), the immediate snapshot
executions can be simulated in a full-information manner. Using ffi as the output
rule of the protocol, we get the "only if" direction of the theorem. ut
Remark. The above theorem ignores the issue of computability. Clearly, the sufficient
condition requires that ffi is computable; furthermore, if a task is solvable
then it implies a way to compute ffi . Therefore, we can add the requirement that
is computable to the necessary and sufficient condition for wait-free solvability.
The previous theorem provides a characterization of wait-free solvable tasks
which depends only on the topological properties of hI To see if a task
is solvable, when the input complex is finite, we produce all E-divided images
of I n and check if a simplicial map ffi as required exists. Note that if we are
interested only in protocols that are bounded wait-free, i.e., where the protocol
has to hold within a predetermined number of steps N , then producing all E-
divided images of the input complex (which is finite) is recursive.
Orientability: We now show that the ISE complex, E n , is an orientable chromatic
divided image. This is used to prove that it induces an algebraic span [15]. We
leave the proof that an orientable chromatic divided image induces an algebraic
span to the full paper, since obviously, it requires the definition of algebraic span,
an algebraic concept of a different flavor from the rest of this paper.
be an m-pseudomanifold. An orientation of a simplex is an equivalence
class of orderings of its vertices, consisting of one particular ordering and
all even permutations of it. If the vertices are colored with ids, we could consider
the positive orientation to be the one in which the vertices are ordered
Fig. 4. An oriented 2-pseudomanifold, with a coloring (in brackets).
with the ids from small to large, and the negative to be the one where the two
vertices with smallest ids are exchanged (each orientation together with all its
even permutations). Denote by oe (i) the face of oe m in which the vertex with id
i is removed; e.g., oe (1) is the face with ids f0; mg. An orientation of an
m-simplex induces an orientation on each of its faces, oe (i) , according to the sign
of (\Gamma1) i . For example, if oe 2 is oriented hv then the induced orientations
are
K m is orientable if there exists an orientation for each of its m-simplexes
such that an m \Gamma 1-simplex contained in two m-simplexes gets opposite induced
orientations. K m together with such an orientation is an oriented pseudoman-
ifold. (See an example in Fig. 4 of a simple oriented 2-pseudomanifold and the
induced orientations.)
In the sequel, we sometimes use a combinatorial notion of orientability. In
the full paper, we prove that the previous (usual) definition of orientability is
equivalent to the combinatorial definition, for chromatic pseudomanifolds.
Lemma 15. 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 \Gamma 1)-face then they belong to different classes.
We say that a chromatic divided image of M (oe m ) under /, K m , is orientable
if, for every oe 2 M (oe m ), /(oe) is orientable.
Theorem16. Let E n be a chromatic divided image of M (oe n ) under /, that
corresponds to the ISE complex starting with input oe n , in which any processor
takes the same number of steps in every execution. Then E n is orientable.
Proof. Let oe i be a face of oe m . We explicitly partition the i-simplexes of /(oe i )
into two disjoint classes, positive and negative.
Let the length of an immediate snapshot execution be the number of concurrency
classes in it. An i-simplex - 2 /(oe i ) is in positive if the length of the
immediate snapshot execution corresponding to - is even; otherwise, it is in neg-
ative. Consider two i-simplexes, - iand - i, that share an (i \Gamma 1)-face, and let p j
be the processor whose view is different. By Lemma 9, without loss of generality,
is in the kth concurrency class of - iand the kth concurrency class of - iis
is the last seen round of p j in - i. Furthermore, since the views of
all other processors are exactly the same, it follows that the lengths of the corresponding
executions differ exactly by one. Hence, the corresponding simplexes
are in different classes, i.e., have different orientations. ut
6 The Number of Monochromatic Simplexes
In this section we prove a combinatorial lemma about the number of monochromatic
simplexes in any binary coloring of an orientable divided image; this lemma
is used in the next section to show a lower bound on renaming.
be an orientable, chromatic divided image of oe m under /. Fix an
orientation of K m , and an induced orientation on its boundary. K m is symmetric
if, for any two i-faces of oe, oe iand oe i, /(oe i) and /(oe i) are isomorphic, under a
one-to-one simplicial map i that is order preserving on the ids: if v and w belong
to the same simplex, and id(v) ! id(w) then binary
coloring, b, of K m is symmetric, if
This definition is motivated by the notion of comparison-based protocols for
renaming, presented in the next section.
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 \Gamma1. For example, if K m consists of just two
m-simplexes, both monochromatic, then the count would be 0, since they would
have opposite orientations, and hence one would count +1 and the other \Gamma1.
The main theorem of this section states that, if K m is a symmetric, oriented
chromatic divided image of oe m under /, with a symmetric binary coloring b,
The proof of this theorem relies on the Index Lemma-a
classical result of combinatorial topology, generalizing Sperner's Lemma (cf. [12,
p. 201]).
To state and prove the Index Lemma, we need the following definitions. Fix
a coloring c of K m with mg. A k-simplex of K m is complete under c,
if it is colored with k. The content, C, of c is the number of complete
m-simplexes, counted by orientation. That is, a complete simplex - m is counted
+1, if the order of the vertices given by the colors agrees with the orientation of
counts +1 if the order given by the colors belongs
to the equivalence class of orderings of the orientation, and else it counts \Gamma1.
For example, the 2-simplex - 1 in Fig. 4 is ordered hv and the colors
are under this order are h0; 1; 2i, hence, it would count +1. On the other hand,
the 2-simplex - 2 in Fig. 4 is ordered and the colors are under this
order are h1; 0; 2i, hence, it would count \Gamma1. The index, I, of c is the number of
1)-simplexes on the boundary of K m , also counted by orientation
(the orientation induced by the unique m-simplex that contains it).
where the (m \Gamma 1)-simplexes in each m-simplex are considered
separately, and counted as +1 or \Gamma1, by their induced orientations. We argue
that I and
To prove that consider the following cases. If an (m \Gamma 1)-face is inter-
nal, then it contributes 0 to S, since the contributions of the two m-simplexes
containing it cancel each other. Obviously, an internal (m \Gamma 1)-face contributes
0 to I. An external (m \Gamma 1)-face in the boundary of K m is counted the same,
or \Gamma1 by orientation, in both S and I. Therefore,
To prove that consider an m-simplex - m , and look at the following
cases. If - m contains two 1)-faces which are completely colored, then - m is
not completely colored and contributes 0 to C. Note that - m contributes 0 also
to S, since the contributions of the two faces cancel each other. If - m contains
exactly one (m \Gamma 1)-face which is completely colored (with
must be completely colored and contributes +1 or \Gamma1, by orientation, to C
as well as to S. If - m does not contain any (m \Gamma 1)-face which is completely
colored, then - m is not completely colored and therefore, it contributes 0 to C
as well as to S. Finally, note that - m cannot contain more than two
which are completely colored. ut
Theorem18 (Binary Coloring Theorem). Let K m be a symmetric, oriented
chromatic divided image of oe m under /, with a symmetric binary coloring b.
Proof. Let ae be the simplicial map from oe m to itself that maps the vertex v
whose id is i to the vertex whose id is (i (that is, the mapping
the rotates the id's). In the rest of the proof, we assume that sub-indices are
taken
Define a coloring of K m , 1), for every v.
Notice that an m-simplex, - m , is completely colored by c if and only if - m is
monochromatic under b. Moreover, for every v,
Let C and I be the content and index of K m under c. Clearly,
I 6= 0. The proof is by induction on m.
I 6= 0.
For the induction step, we consider bound(K m ), and "squeeze" it, 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 .
Consider an internal (m \Gamma 2)-simplex, - m\Gamma2 2 bound(K m ), which is contained
in two Its link vertices are v 1 , which is the vertex of
- 1 not in - m\Gamma2 , and v 2 , which is the vertex of - 2 not in - m\Gamma2 . A binary coloring
is irreducible if the link vertices of any internal (m \Gamma 2)-simplex simplex of /(oe (i) )
have different binary colors.
The first stage of the proof applies a sequence of specific contractions to
its coloring is irreducible, while preserving all other
properties.
The contractions we apply are symmetric contractions, in which we choose
an internal (m \Gamma 2)-simplex, - m\Gamma2 2 /(oe (m) ), to which a contraction can be
applied; that is, such that its two link vertices have the same binary coloring.
We contract - m\Gamma2 and simplexes symmetric to it in /(oe (i) ), for all i. (This is a
sequence of m+ 1 contractions.) Notice that the simplexes which are symmetric
to - m\Gamma2 are also internal and their link vertices have the same binary coloring.
A boundary is proper symmetric if it is the boundary of a symmetric, oriented
chromatic divided image of oe m under /, with a symmetric binary coloring b. In
the next claim we show that a symmetric contraction preserves all properties of
a proper symmetric boundary.
Assume we apply a symmetric contraction to bound(K m ), and get a
complex bound 0 . Then bound 0 is a non-empty, proper symmetric boundary under
Furthermore, I(bound 0
Proof. Given note that we have
that Therefore, bound 0 is chromatic. Also, it is easy to see that
the orientation on bound 0 is still well defined: two (m \Gamma 1)-simplexes that did
not have an (m \Gamma 2)-face in common before the contraction will have it after
the contraction, only if they differ in exactly one vertex, in addition to v 1 and
Thus, two such simplexes have opposite orientations. By the definition of
symmetric contraction, bound 0 remains symmetric.
By induction hypothesis of the theorem, #mono(/(oe (i) )) 6= 0, for every i.
Since a contraction removes simplexes with opposite orientations and the same
binary colorings, #mono(/(oe (i) for every i, and
This implies that bound 0 is non-empty. ut
By Claim 19, for the rest of the proof, we can assume that /(bound(oe m
non-empty, proper symmetric boundary with an irreducible
binary coloring. Recall that
1)-simplexes on the boundary of K m are counted
with the same sign by I.
Proof. We first argue that every complete (m \Gamma 1)-simplex in /(oe (i) ) is counted
with the same sign by I, for any i. To see this, assume, without loss of generality,
that consider an colored with
(the first component of a vertex is the
id and the second is its binary color).
Consider a path to any other (m \Gamma 1)-simplex - 2 colored with the same ids and
colors; such a path must exist since, by Lemma 3, we can assume that /(oe (i) ) is
1)-connected. Notice that the colors assigned by c are the same in - 1 and
will be counted by I. It remains to show that - 1 and
have the same orientation and hence are counted with the same sign by I.
Note that this path consists of a sequence of (m \Gamma 1)-simplexes, each sharing
an (m\Gamma2)-face with the previous simplex, and differing from the previous simplex
in exactly one binary color. Thus the path corresponds to a sequence of binary
vectors, starting with the all 0's vector and ending with the all 0's vector, and
each vector differing from the previous vector 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 the complex is oriented, consecutive simplexes
on the path have different orientations. Since the length of the path is even, - 1
have the same orientation. Hence, - 1 and - 2 are counted with the same
sign by I.
Next, we show that complete (m \Gamma 1)-simplexes in different /(oe (i) )'s are also
counted with the same sign by I. Again, without loss of generality, assume that
counted by I. Note that the c
coloring of - 1 is f(0; 0); (1; 1)g.
We now show that any complete (m \Gamma 1)-simplex - 3 2 /(oe (i) ) will be counted
with the same sign by I. Without loss of generality, assume
- 3 is complete, with id's mg. Thus, the binary color of the vertex
with process id m must be 1, in order to get the color 0 under c. This implies
that the c coloring of - 3 is f(1; 1); (2; its binary coloring
is 1)g.
Consider the simplex - 2 2 /(oe (0) ), which is the image of - 1 under the symmetry
map, ae. That is, 0)g. Consider a path in /(oe (0) )
and - 3
. Since the binary coloring vector of - 3
differs from the binary
coloring vector of - 2
in exactly one position, the length of this path must be odd.
Therefore,
and - 3
must have different orientations.
The c coloring of - 3 , f(1; 1); (2; rotated w.r.t. its ids, and
hence the orderings of - 2 and - 3 agree (on the sign of the permutation) if and
only if m is odd. E.g., if
0)g. Finally, the orientation of - 1 is (\Gamma1) m times the orientation
of - 2 , since they are symmetric simplexes in /(oe (m) ) and /(oe (0) ). That
is, the orientations of - 1 and - 2 agree when m is even, and disagree otherwise.
Therefore, the orientations of - 1 and - 3 agree, and they are counted with the
same sign by I. ut
Since bound is non-empty and contains at least one simplex, Claim 20 implies
I 6= 0, which proves the theorem. ut
Applications
In this section, we apply the condition for wait-free solvability presented earlier
(Corollary 13) to derive two lower bounds, for renaming and for k-set consensus.
The first lower bound also relies on Theorem 18, and therefore, on the fact
that the chromatic divided image induced by immediate snapshot executions
is orientable. In the full version of the paper we also derive another necessary
condition, based on connectivity.
7.1 Renaming
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 contains all subsets of some domain D (of original
names) with different values, M n contains all subsets of [0::M ] (of new names)
with different values, and \Delta maps each oe n 2 D n to all n-simplexes of M n . We
use Theorem 12 and Theorem to prove that there is no wait-free anonymous
protocol for the M-renaming task, if M - 2n \Gamma 1. The bound is tight, since there
exists an anonymous wait-free protocol ([2]) for the 2n-renaming problem.
Theorem 21. If M ! 2n, then there is no anonymous wait-free protocol that
solves the M -renaming task.
Proof. Assume, by way of contradiction, that P is a wait-free protocol for the
M-renaming task, M - 2n \Gamma 1. Without loss of generality, we assume that every
process executes the same number of steps. Also, P is comparison-based, i.e.,
the protocol produces the same outputs on inputs which are order-equivalent.
(See Herlihy [13], who attributes this observation to Eli Gafni).
Assume that assume that the original names are only between
0 and 2n. By Corollary 13, there exists a a chromatic full divided image
of the input complex D n , be the decision map implied by P. By Theorem
16, S is orientable. Since the protocol is comparison-based and anonymous,
it follows that for any two i-simplexes, oe iand oe iof D n , ffi P maps /(oe i) and
/(oe i) to simplexes that have the same output values (perhaps with different
process ids).
be the binary coloring which is the parity of the new names assigned by
Therefore, the assumption of Theorem is satisfied for S(oe n ), and therefore,
at least one simplex of S(oe n ) is monochromatic under ffi 0 .
On the other hand, note that the domain [0; 2n \Gamma 1] does not include n
different odd names; similarly, the domain [0; 2n \Gamma 1] does not include n
different even names. This implies that ffi 0 cannot color any simplex of S with all
zeroes or with all ones; i.e., no simplex of S is monochromatic. A contradiction.
ut
7.2 k-Set Consensus
Intuitively, in the k-set consensus task ([7]), processes start with input values
from some domain and are required to produce at most k different 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 ; \Deltai. D n is P (D), for some domain D, and \Delta maps each
to the subset of n-simplexes in D n that contain at most k different
values from the values in oe n . In the full version of the paper, we use Theorem 12
and Sperner's Lemma to prove that any wait-free protocol for this problem
must have at least one execution in which k +1 different values are output. This
implies:
Theorem22. If k - n then there does not exists a wait-free protocol that solves
the k-set consensus task.
This bound is tight, by the protocol of [7].
This paper presents a study of wait-free solvability based on combinatorial topol-
ogy. Informally, we have defined 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 specification. We were able to use theorems about
combinatorial properties of divided images to derive tight lower bounds for renaming
and k-set consensus. Our results do not use homology groups, whose
computation may be complicated. We also derive a new necessary and sufficient
condition, based on a specific, well structured chromatic divided image.
Many questions remain open. First, it is of interest to find other applications
to the necessary and sufficient condition presented here; in particular, can we derive
interesting protocols from the sufficient 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 [3]), to handle other primitive objects besides read/write
registers (cf. [14, 6]), and to incorporate on-going tasks.

Acknowledgments

We would like to thank Javier Bracho, Eli Gafni, Maurice
Herlihy, Nir Shavit and Mark Tuttle for comments on the paper and very useful
discussions.



--R

"Are Wait-Free Algorithms Fast?"
"Renaming in an asynchronous environment,"
"A combinatorial characterization of the distributed 1.solvable tasks,"
"Generalized FLP impossibility result for t-resilient asynchronous computations,"
"Immediate atomic snapshots and fast renaming,"
"The implication of the Borowsky-Gafni simulation on the set consensus hierarchy,"
"More Choices Allow More Faults: Set Consensus Problems in Totally Asynchronous Systems,"
"A tight lower bound for k-set agreement,"
"Reaching Approximate Agreement in the Presence of Faults,"
"Impossibility of distributed commit with one faulty process,"
"3-processor tasks are undecidable,"
A Combinatorial Introduction to Topology
A. Tutorial on
"Set Consensus Using Arbitrary Objects,"
"Algebraic Spans,"
"On the Decidability of Distributed Decision Tasks,"
"The asynchronous computability theorem for t- resilient tasks,"
"A simple constructive computability theorem for wait-free computation,"
Elements of
"Wait-free k-set agreement is impossible: The topology of public knowledge,"

--TR

--CTR
Faith Fich , Eric Ruppert, Hundreds of impossibility results for distributed computing, Distributed Computing, v.16 n.2-3, p.121-163, September
atomic read/write registers;set consensus;consensus;combinatorial topology;renaming;distributed systems;shared memory systems;wait-free solvable tasks