Towards a Topological Characterization of Asynchronous Complexity

(Latest Draft – Do Not Distribute)

Gunnar Hoest M.I.T. and Nir Shavit Tel-Aviv University and M.I.T.

This paper introduces the use of topological models and methods, formerly used to analyze computability, as tools for the quantification and classification of asynchronous complexity. We present the first asynchronous complexity theorem, applied to decision tasks in the IIS memory model of Borowsky and Gafni. We do so by introducing a novel form of topological tool called the nonuniform chromatic subdivision. Building on the framework of Herlihy and Shavit’s topological computability model, our theorem states that the time complexity of any asynchronous algorithm is directly proportional to the level of non-uniform chromatic subdivisions necessary to allow a simplicial map from the complex representing a task’s inputs to the one representing its outputs.

To show the power of our theorem, we use it to derive two new results. The first is a tight upper/lower bound on the time to acheive N process approximate agreement: ⌊log_{d} \frac{input range}{ϵ} ⌋ where d = 3 for two processes and d = 2 for 3 or more. The second is the first time-complexity/number-of-names upper bound tradoff for the renaming problem:

\frac{N(N + 1)}{2} − Σ_{i=2}^{time(N)}N − i ≤ names(N) < \frac{N(N + 1)}{2} − Σ_{i=2}^{time(N)−1}N − i.

This upper bound formula quantifies an interesting non-linear relationship between the number of names and the computation time used to solve N process renaming.

More than the new bounds themselves, we beleive the importance of our asynchronous complexity theorem is that the algorithms and lower bounds it allows us to derive are intuitive and simple, with topological proofs that require no mention of concurrency at all.

A Characterization of Asynchronous Complexity · 1

1. INTRODUCTION

As we enter the 21st century, computers are being used more and more as coordination devices, making standard (Turing) notions of computability and complexity insufficient for evaluating their behaviour in our mostly asynchronous world. In the last few years, techniques of modeling and analysis based on classical algebraic topology [2; 7; ?; 10; ?; 11; 12; 13; 14; ?; 17] in conjunction with distributed simulation methods [7; 5; 6; ?] have brought about significant progress in our understanding of computability problems in an asynchronous distributed setting. We feel the time is ripe to extend these techniques to address asynchronous complexity.

This paper studies the class of problems called decision tasks, input/output problems in which N asynchronous processes start with input values, communicate via shared memory and halt with private output values. We focus on a generalized version of Borosky and Gafni’s Iterated Immediate Snapshot (IIS) model [7], called the Non-uniform Iterated Immediate Snapshot (NIIS) Model. The IIS model has already been successfully used by Borowsky and Gafni [7] as part of their new simplified proof of the asynchronous computability theorem [?]. The model is a restriction of atomic snapshot memory that guarantees that processes’ scan operations return views that contain non-decreasing sets of the participating processes’ inputs. We believe it is a good first candidate for topological modeling since it has a particularly nice geometric representation, and hence easily lends itself to topological analysis.

Keeping in style with Herlihy and Shavit’s topological computability framework [?], our theorem states that the worst case time complexity for solving a decision task in the NIIS model is equivalent to the minimal number of non-uniform chromatic subdivisions of the input complex necessary to allow a simplicial map from the input complex to the output complex. The theorem also immediately provides a matching upper bound given the subdivision and mapping.

The non-uniform chromatic subdivisions we introduce (See Figure 1 for examples) are a looser and more general form of standard chromatic subdivisions [?]. Unlike the iterated standard chromatic subdivisions used in the computability work of [?; 7], they allow individual simplices in a complex to be subdivided a different number of times, while assuring that the subdivision of the complex as a whole remains consistent. Non-uniformity is a necessary property when analyzing complexity, since the time complexity and hence the level of subdivision of an input simplex may differ from one set of inputs to the next. Considering just the complexity of the worst case execution over all input sets would in many cases make a complexity theorem useless, since for example, for the approximate agreement problem Aspnes and Herlihy [1] have shown that for any k one can find a set of inputs that will require time k in the worst case.

The power of our theorem lies in its ability to allow one to reason about the complexity of problems in a purely topological setting. As we show, the subdivisions of a complex are a clean and higher level way of thinking about the multitude of different length executions of a concurrent protocol. We found this topological representation helpful and are sure that it will prove to be an invaluable tool for

2 · G. Hoest and N. Shavit

time=  1  2  3 4 5
N=2  3  3  3 3 3
N=3  6  5  5 5 5
N=4  10  8  7 7 7
N=5  15 12 10 9 9

Table 1. Number of names of solution as a function of N and time.

designing and analyzing concurrent algorithms.

We provide two example applications of our theorem. In Section 5 we show tight upper and lower bounds on the time to achieve N process approximate agreement. The best known results, due to Aspnes and Herlihy [1], imply an O(log_{2} N) upper bound and an Ω(log_{3} N) lower bound computation, which will be specified in Section ??. We close this gap, proving matching upper and lower bounds of ⌊log_{d} \frac{input−range}{ϵ}⌋ where d = 3 for two processes and d = 2 for 3 or more.

Our second result, in Section 6, is the first upper bound result for the N-process renaming problem [3] of Attiya et. al that provides a tradeoff between the number of available names and the time complexity. We show that there exists an algorithm in the NIIS model with time complexity time(N) and number of names names(N) if:

\frac{N(N + 1)}{2} − ∑_{i=2}N − i^{time(N)} ≤ names(N) < \frac{N(N + 1)}{2} − ∑_{i=2}N − i^{time(N)−1}

where

2N − 1 ≤ names(N) ≤ N(N + 1)/2

and

1 ≤ time(N) ≤ N − 1.

This formula quantifies an interesting arithmetic relationship between the number of names and the computation time used by a protocol solving N process renaming. It conforms with the 2N − 1 ≤ names(N) lower bound due to Herlihy and Shavit [?] and extends the time(N) = N upper bound of Borowsky and Gafni [6] using 2N − 1 names. Table 1 shows several examples of how the time complexity and number of names vary for different values of N based on our formula. We derive the class of algorithms implied by the formula and their proofs in a purely geometric way ^{1}.

Our formula implies a time(N) = 1 algorithm when names(N) = N(N + 1)/2. Though optimal in our model, this falls short of the O(N) bound of Anderson and Moir [?] in the Multi-reader Single-writer register model (MRSW) [?], since known implementations of IIS from MRSW take Θ(N^{2}) time.

Since we must introduce quite a bit of mathematical machinery in order to present our main theorem, we start out by describing it on an intuitive level.

1We believe the upper bound formula is tight, and are currently working on a matching lower bound.

1.1 A Bit of Intuition

It is perhaps best to explain our theorem by way of a simple example. Consider any comparison-based protocol solving the two-process version of the renaming problem with 3 names. The left hand side of Figure 1 describes the input and output complexes. Recall that the name space of processes is very large, that is, the input complex contains many vertices corresponding to many possible process names. However, since this is a comparison-based protocol, they can be represented by two vertices p and q and two edges (1-simplices) between them representing the case where p > q and the case where p < q. The output complex is a cycle of 1-simplices the describes all the possible combinations of legal output values in two-process executions of renaming with three output names.

Our complexity theorem says that the complexity of any protocol solving the renaming problem in the NIIS model is exactly the number of non-uniform chromatic subdivisions necessary to allow a simplicial map ^{2} from the subdivided input complex to the output complex. And indeed a single subdivision will allow such a map as depicted on the right hand side. Hence this problem is solvable in the NIIS model in exactly one step by each process.

As will be shown in great detail later, the idea is that the added nodes of the subdivision actually capture the possible different executions that may result from processes accessing an IS object. This can be seen in the labeling of the vertices that correspond to whether they saw the other process in the view returned from the IS object. The implied symmetric protocol appears in the middle of Figure 1.

What happens when we go to three processes? Well, a single subdivision of a 2-simplex looks like the left hand side of Figure 2. Notice that, with 6 possible output names, we can label this complex so that all 2-simplices are labeled with 3 different names, one for each vertex. In general, as we show in Section 6, one can label a subdivided n-simplex corresponding to the N = n + 1 process executions of a protocol with N(N + 1)/2 names. Such a labeling corresponds to a simplicial map from the subdivided input complex to the output complex satisfying the task

2Meeting the problem restrictions – i.e. the map must be symmetric for all cases where processes have the same relative id order.

Fig. 1. Two Process Renaming

requirements. By our complexity theorem, this implies that one can solve renaming in this case with a single IS object (one step in the NIIS model). This offers a partial explanation for Anderson and Moir’s ability to beat all known renaming upper bounds for the case where there are N(N + 1)/2 names [?].

Fig. 2. Three Process Renaming with Five and Six Names

However, if we only have 5 names, the readers can convince themselves that one needs to subdivide once more in order to subdivide the 2-simplex so that all subsimplices can be labeled with different names so as to satisfy the task requirement. The right hand side of Figure 2 shows how this can be done, and is an example of a non-uniform subdivision – some simplices are subdivided more than others ^{3} This figure implies that with 5 names the time complexity of solving 3 process renaming is two. As with the two process case, the various “stacked” subdivided 2-simplexes in the figure correspond to the many possible input simplexes with different orders among the processes. The subdivision completely describes the solution algorithm 4, which is presented in Figure 22. Extending this reasoning to higher dimensions allows us to derive our upper bound formula.

Finally, consider the approximate agreement problem, which we discuss in detail in Section 5. We are able to explain and close the upper/lower bound gap implied by Aspnes and Herlihy’s approximate agreement work [1]. Consider Figure ??, which shows the subdivisions induced by a three process approximate agreement protocol on some given input set. Aspnes and Herlihy derive their lower bound for any N process algorithm from a “bad” execution in which only the two processes with inputs farthest apart participate. Such an execution in the figure corresponds to a sequence of subdivisions of the edge between P and Q. Since each subdivision introduces two new vertices and splits the edge in three, one can only get a log_{3} bound in this way. However, note that if one considers three processes, a 2-simplex rather than just an edge must be subdivided, and as we show, no matter how one subdivides it, there will always be a path between P and Q that includes vertices

3One could also in this case provide a uniform/canonical chromatic subdivision, but it would be significantly more complicated and the implied algorithm would have all processes take the two steps. 4We choose in Figure 22 to make the unique process be the one with highest id, but it could just as well be the one with smallest id or any other such quantification based only on comparison of ids.

A Characterization of Asynchronous Complexity · 5

of R (marked by a darker color in the figure) that will be cut by at most a half in each subdivision, implying a tight log_{2} lower bound.

2. MODEL

In order to develop a useful and applicable complexity theory for asynchronous, distributed computer systems, we need to define some reasonable model of such systems. This model must be detailed enough so as to accurately and faithfully capture the inherent complexity of solving tasks in real distributed systems, yet be simple enough so as to easily lend itself to some practical form of complexity analysis. The model we consider in this consists of a restricted class of one-shot distributed problems, called decision tasks, together with a novel model of computation, a type of shared memory called the non-uniform immediate snapshot model. This section contains a detailed description of these fundamental concepts. It also contains the complexity measures that will be used to analyze the complexity of solving decision tasks in the non-uniform immediate snapshot model.

2.1 Informal Synopsis

We begin with an informal synopsis of our model, which largely follows that of Herlihy and Shavit [13; 14]. Some fixed number N = n + 1 of sequential threads of control, called processes, communicate by asynchronously accessing shared memory in order to solve decision tasks. In such a task, each process starts with a private input value and halts with a private output value. For example, in the well-known binary consensus task, the processes have binary inputs, and must agree on some process’s input [9]. A protocol is a distributed program that solves a decision task in such a system. A protocol is wait-free if it guarantees that every non-faulty process will halt in a finite number of steps, independent of the progress of the other processes. The time complexity of solving a decision task in this model on a given input set is the supremum of the number of accesses to shared memory made by any process on that input set.

2.2 Decision Tasks

In this subsection, we define decision tasks more precisely. This class of tasks is intended to provide a simple model of reactive systems, such as databases, file systems, or automatic teller machines. An input value represents information entering the system from the surrounding environment, such as a character typed at a keyboard, a message from another computer, or a signal from a sensor. An output value models an effect on the outside world, such as an irrevocable decision to commit a transaction, to dispense cash, or to launch a missile. A decision task is, informally speaking, a relation between vectors of input values and vectors of output values. We define this more precisely below.

Let D_{I} and D_{O} be two data types, possibly identical, called the input data type and the output data type, respectively. We first define the concept of an input vector.

Definition 2.1. An n+1-process input vector I⃗ is an n+1-dimensional vector, indexed by ℤ_{n+1}(the integers mod n), each component of which is either an object of type D_{I}, or the distinguished value ⊥, with the additional requirement that at least one component of I⃗ must be different from ⊥.

The definition of output vectors is similar to that for input vectors:

Definition 2.2. An n + 1-process output vector O⃗ is an n + 1-dimensional vector, indexed by ℤ_{n+1}, each component of which is either an object of type D_{O}, or the distinguished value ⊥,

When it is clear from the context, we omit mentioning the number of processes in specifying input and output vectors. We denote the i-th component of an input vector I⃗ by I⃗[i], and similarly, we denote the i-th component of an output vector O⃗ by O⃗[i]. In the sequel, unless stated otherwise, we will assume that i and j are index values in the set ℤ_{n+1}. These index values will be used both for specifying vector elements and also to index processes.

Definition 2.3. A vector U⃗ is a prefix of V⃗ if V⃗ [i] = ⊥ implies that U⃗[i] = ⊥ and for all i such that U⃗[i] ≠ ⊥, U⃗[i] = V⃗ [i].

Definition 2.4. A set V of vectors is prefix-closed if for all V⃗ ∈ V, every prefix U⃗ of V⃗ is in V.

In this paper we will only consider sets of input and output vectors that are prefixclosed.

Definition 2.5. An input set is a fnite, prefix-closed set of input vectors. An output set is a finite, prefix-closed set of output vectors.

Next, we define the notion of a task specification map, which is essentially a relation between the input set of and the output set.

Definition 2.6. Let I and O be input and output sets, respectively. A task specification relating the two sets is a map γ, carrying each input vector I⃗ to a prefix-closed, non-empty set γ(I⃗) of output vectors, with the additional requirement that, for all i, I⃗[i] = ⊥ if and only if for all O⃗ ∈ γ(I⃗), O⃗[i] = ⊥.

For a given input vector I⃗, the set of vectors γ(I⃗) represents the set of legitimate output vectors for the set of inputs specified by I⃗. This set will generally contain more than one allowable output vector.

We are now ready to give a precise definition of decision tasks.

Definition 2.7. A decision task D = ⟨I, O, γ⟩ is a tuple consisting of a set I of input vectors, a set O of output vectors, and a task specification map γ relating these two sets.

We note that, by definition, decision tasks are inherently one-shot, since all participating processes have a single input and must decide on a single output exactly once.

Not all entries in a given input vector need contain an input value; Some may contain the special value ⊥, indicating that some processes do not receive an input value. We formalize this notion of participation in the definition below.

Definition 2.8. For any input vector I⃗, if the i-th component is not ⊥, then i participates in I⃗. Otherwise, we say that i does not participate in I⃗. Moreover, we define the participating set in I⃗ to be set of participating indexes.

As noted by Herlihy and Shavit [13; 14], the reason for incorporating an explicit notion of participating indexes in our formalism for decision tasks is that it is convenient for distinguishing between tasks such as the following, which have the same sets of input and output vectors, but different task specification maps.

Example 2.9. The n + 1-process Unique-Id task is defined as follows:

—I = {[0, …, n] | x_{i} ∈ {i, ⊥}}. —O = {[x_{1}, …, x_{n}] | x_{i} ∈ ℤ_{n+1} ∪ {⊥}, (x_{i} = x_{j}) ⇒ (x_{i} = ⊥)}.

—∀I⃗ ∈ I : O⃗ ∈ γ(I⃗) iff for all i, j, (O⃗[i] = O⃗[j]) ⇒ (O⃗[i] = ⊥).

Example 2.10. The n + 1-process Fetch-And-Increment task is defined as follows:

—I = {[x_{0}, …, x_{n}] | x_{i} ∈ {i, ⊥}}. —O = {[x_{1}, …, x_{n}] | x_{i} ∈ ℤ_{n+1} ∪ {⊥}, (x_{i} = x_{j}) ⇒ (x_{i} = ⊥)}.

—∀I⃗ ∈ I : O⃗ ∈ γ(I⃗) iff for all i, j, the following two conditions hold:

—(O⃗[i] = O⃗[j]) ⇒ (O⃗[i] = ⊥).

—O⃗[i] must be less than the size of the participating set of I⃗..

The two decision tasks above differ in that the task specification map of Fetch-And-Increment involves explicit mention of the participating set of the input vectors in order to capture the fact that indexes are handed out in an increasing order while that of Unique-Id does not.

2.3 One-Shot Immediate Snapshot

Borowsky and Gafni’s Immediate Snapshot object (IS) [6] has by now been proven to be a useful building block for the construction and analysis of protocols in asynchronous, distributed systems [6; ?; 13; 7].

Informally, an n + 1-process IS object consists of a shared n + 1-dimensional memory array, and supports a single type of external operation, called writeread. The IS object has n + 1 ports, one for each process. We typically associate process i with the i-th port. Each writereadoperation writes a value to a single shared memory array cell, and then immediately returns a snapshot view of the entire array. There is a separate writereadoperation for each of the IS object’s n+1 ports. A writereadoperation on port i writes its value to the i-th cell of the memory array.

IS_{D}^{n+1} object named IS_{x}

Signature

Inputs:

inv writeread(v)_{i,IS_{x}}, v ∈ D, i ∈ {0, …, n}. Internals:

update(U), U ⊆ {0, …, n}. Outputs:

ret writeread(S)_{i,IS_{x}}, S ∈ ϑ(D), i ∈ {0, …, n}.

State

memory ∈ ϑ(D), initially (⊥, …, ⊥). input value ∈ ϑ(D), initially (⊥, …, ⊥). return value ∈ ϑ^{2}(D), initially (⊥, …, ⊥). interface ∈ {inv, ret, ⊥}^{n+1}, (⊥, …, ⊥)

Transitions

input: inv writeread(v)_{i,IS_{x}}

Eff: input value[i] := v interface[i] := inv

internal: update(U)

Pre: U ⊆ {i | interface[i] = inv} Eff: For all i in U do

memory[i] := v For all i in U do

return value[i] := memory For all i in U do

interface[i] := ret output: ret writeread(S)_{i,IS_{x}} Pre: interface[i] = ret

return value[i] = S Eff: interface[i] := ⊥

Fig. 3. I/O Automaton for an IS_{D}^{n+1} object with name IS_{x}.

Formally, we can specify IS objects as I/O automata [15]. Let D be any data type, and define ϑ(D) to be the data type (D ∪ {⊥})^{n+1}, the set of all n + 1-arrays each of whose cells contains either an element of D, or ⊥. We index the elements of ϑ(D) using the numbers in ℤ_{n+1}. An IS automaton for n + 1 processes and data type D called IS_{x} is defined as in Figure 3. We refer to such an object as an IS_{D}^{n+1} object. When the data type and number of processes are clear from the context, we usually omit the sub- and superscripts above.

For all i, the inv writeread(v)_{i,IS_{x}}action simply writes the input value v to the ith cell of the input valuearray. This array provides temporary storage for inputs to the IS_{D}^{n+1} object. At the same time, the flag “inv” is written to the i-th cell of the interfacearray, which indicates that an input has arrived on port i. The update(U)action periodically copies a set of values corresponding to the indices in U, from the input valuearray to the memoryarray. The set U must be a subset of the indices i with the property that interface[i]= inv. Additionally, a copy of the memoryarray is written to the ith cell of the return valuearray for each i ∈ U. Finally, the flag ret is written to the i-th cell of the interface array for each i ∈ U, indicating that a response value to the invocation on port i is available. The ret writeread(S)_{i,IS_{x}}output action provides a response to a previous invocation on port i. Its only effect on the IS object is to reset the value interface[i]to ⊥, thereby preventing more than one response to an invocation. The ret writeread(S)_{i,IS_{x}}action can only occur after a return value has been written to the i-th cell of the return valuearray, and the flag “ret” has been written to the corresponding cell in the interfacearray.

In the remainder of this subsection, we will state and prove a few basic properties about IS objects. These properties will be useful later, when we prove the correctness of a topological framework for analyzing the complexity of protocols in models of computation that include multiple IS objects. For the purpose of this discussion, let us for the remainder of this subsection fix our attention on a single IS_{D}^{n+1} object, which we will call IS_{x}.

Definition 2.11. An execution of IS_{x} is an alternating sequence of object states and actions s_{0}, a_{1}, s_{1}, a_{2}, s_{2}, …, where s_{0} is a start state of IS_{x}, and for all k, where k ≥ 1, the action a_{k} brings the object from state s_{k−1} to state s_{k}.

It is clear that, in any execution α of IS_{x}, writereadinvocations and responses will occur in alternating order, starting with an invocation, on each port i. The following definition provides a convenient notation for matching pairs of invocations and responses in α.

Definition 2.12. For all i, a writeread(v, S)_{i,IS_{x}}operation in an execution α is an inv writeread(v)_{i,IS_{x}}action together with the next ret writeread(S)_{i,IS_{x}}action on the same port.

The operation writeread(v, S)_{i,IS_{x}}uses the i-th port of IS_{x} to write the value v to the i-th cell of memory, and subsequently return a snapshot S.

Definition 2.13. For all i, an incomplete operation in an execution α is an inv writeread(v)_{i,IS_{x}}action for which there is no subsequent ret writeread(S)_{i,IS_{x}}action on the same port.

An incomplete operation inv writeread(v)_{i,IS_{x}}in α uses the i-th port of IS_{x} to write a value v to the i-th cell of memory, but there is no subsequent response on the i-th port in α.

We note that the specification of IS_{x} does not in any way restrict the number of accesses that may occur on any given port in an execution. In fact, it even allows two invocations on a port i before any response is given to the first invocation. In this paper, however, we will only be using IS objects as building blocks to construct more complicated, long-lived models of computation, not as a long-lived object in its own right. Therefore, we will only consider a restricted class of executions of IS_{x}, called one-shot executions, as defined below.

Definition 2.14. A one-shot execution of IS_{x} is an execution for which there is at most one invocation and at most one response on each port.

In the remainder of this subsection we will be considering only on-shot executions of IS_{x}.

Lemma 2.15. For any two distinct actions update(U)and update(U′) in a oneshot execution α if IS_{x}, the index sets U and U′ are disjoint.

Proof. Suppose without loss of generality that U occurs before U′, and suppose i ∈ U. Immediately after the actionupdate(U), interface[i]is equal to “ret”. Since we are considering a one-shot execution, interface[i]will remain equal to “ret” for the remainder of the execution. Hence, the precondition of the update(U′) action guarantees that i ∉ U′. □

We can now define what we mean by concurrent operations of IS_{x}.

Definition 2.16. Two operations writeread(v_{i}, S_{i})_{i,IS_{x}} and writeread(v_{j}, S_{j})_{j,IS_{x}} in a one-shot execution α of IS_{x} are concurrent if there exists an action update(U)in α such that i, j ∈ U.

IS_{x} exhibits a property called self-containment. A snapshot returned on port i by a ret writeread(S)_{i,IS_{x}}action in a one-shot execution α, must necessarily contain the value written to memoryin the matching, preceding inv writeread(v)_{i,IS_{x}}action on port i that is part of the same operation. This property is proven in Lemma 2.17.

Lemma 2.17. Consider any operation writeread(v_{i}, S_{i})_{i,IS_{x}} in a one-shot execution α of IS_{x}. Then S_{i}[i] ≠ ⊥.

Proof. The input value v_{i} is written to memoryby an action update(U_{i}). In the same action, after the v_{i} has been written to memory, the memoryvariable is copied to return value[i]. This value is then returned as a response on port i. It follows that S_{i}[i] ≠ ⊥ for all i. □

The values returned by a ret writeread(S)_{i,IS_{x}}action are n-dimensional arrays of type ϑ(D). The following definition provides an order relation on the set of such arrays.

Definition 2.18. An array A_{1} is a prefix of A_{2} if A_{1}[i] = ⊥ implies that A_{2}[i] = ⊥, and for all i such that A_{2}[i] ≠ ⊥, A_{2}[i] = A_{1}[i].

In the following lemma, we prove that IS_{x} exhibits the property that the set of snapshots returned in any one-shot execution can be totally ordered by the prefix relation defined above.

Lemma 2.19. Consider any two writereadoperations in α, writeread(v_{i}, S_{i})_{i,IS_{x}} and writeread(v_{j}, S_{j})_{j,IS_{x}}. Either S_{i} is a prefix of S_{j} or S_{j} is a prefix of S_{i}.

Proof. Suppose the values v_{i} and v_{j} are written to memoryby the actions update(U_{i}) and update(U_{j}), respectively.

If these actions are the same, that is, if U_{i} = U_{j}, the two operations writeread(v_{i}, S_{i})_{i,IS_{x}} and writeread(v_{j}, S_{j})_{j,IS_{x}} are concurrent. In this case, the value of memorythat is copied to return value[i]is identical to the value copied to return value[j], since both are copied by the same update(U_{i}) action. It follows that S_{i} = S_{j}. Now suppose U_{i} ≠ U_{j}, and suppose update(U_{i}) occurs after update(U_{j}). Since no memorycells are ever reset, it follows that the memoryversion that is written to return value[j] during update(U_{j}) is a prefix of the version that is written to return value[i]during update(U_{i}). Hence S_{j} is a prefix of S_{i}. The case where update(U_{j}) occurs after update(U_{i}) is similar, and in this case we have that S_{i} is a prefix of S_{j}. The lemma follows. □

The final lemma concerns what is referred to as the immediacy property of IS_{x}. If a value written to memoryby an invocation on port j is contained in a snapshot on port i, then the snapshot returned on port j is a prefix of that returned on port i. This corresponds to the informal notion of a writereadoperation on port j happening before a writeread operation on port i.

Lemma 2.20. Consider any two writereadoperations in α, writeread(v_{i}, S_{i})_{i,IS_{x}} and writeread(v_{j}, S_{j})_{j,IS_{x}}. If S_{i}[j] ≠ ⊥ then S_{j} is a prefix of S_{i}.

Proof. Suppose the values v_{i} and v_{j} are written to memoryby the actions update(U_{i}) and update(U_{j}), respectively, and suppose S_{i}[j] ≠ ⊥. This implies that v_{j} was written to memoryduring update(U_{i}), in which case U_{i} = U_{j}, or the action update(U_{j}) occured before update(U_{i}). In either case, since no memorycells are ever reset or written to more than once in a one-shot execution, we have that S_{j} must be a prefix of S_{i}. □

Figure 4 shows a stylized diagram of the IS object IS_{x}.

2.4 The Iterated Immediate Snapshot (IIS) Model

The Iterated Immediate Snapshot (IIS) Model, first used by Herlihy and Shavit [14], was recently formulated as a computation model by Borowsky and Gafni [7]. The model assumes a finite sequence IS_{D}^{n+1}, IS_{ϑ(D)}^{n+1}, IS_{ϑ^{2}(D)}^{n+1}, …, IS_{ϑ^{k−1}(D)} of IS objects, denoted IS_{1}, IS_{2}, IS_{3}, …, IS_{k}, where k > 0. In the k-shot IIS model, there are k available IS objects in sequence.

Each protocol in the IIS model is fully determined by the maximum number n + 1 of processes that can participate, the number k of IS objects available, and a decision map δ : ϑ^{k}(D) → D_{O}, where D_{O} is an arbitrary data type, which we call the protocol’s output data type. We refer to the protocol obtained by fixing these parameters as P_{(n,k,δ)}.

We can specify the P_{(n,k,δ)} protocol using I/O automata [15] as follows. Each IS object is specified as in figure 3, and each process i is specified as in Figure 5. The protocol P_{(n,k,δ)} can then be specified by composing the automata for the processes with the IS object automata by matching up operations as follows. Assume that for each process i, and each x, where 1 ≤ x ≤ k, the object IS_{x} is

Fig. 4. Diagram of IS_{x}.

connected to the x-th port on i, and the i-th process is connected to the i-th port on IS_{x}. For each processor i and IS object IS_{x}, we match up i’s and IS_{x}’s inv writeread(v)_{i,IS_{x}}and ret writeread(S)_{i,IS_{x}}actions. The resulting protocol automaton is denoted P_{(n,k,δ)} = {0, 1, …, n; IS_{1}, IS_{2}, …, IS_{k}}.

In any execution α, the first action executed by any process i is a start(v)_{i}action, which stores an input value v in its local statevariable. A process i may not have a start(v)_{i}action in α, however, in which case it takes no steps at all in this particular execution.

Definition 2.21. A process i is said to participate in an execution α of the protocol P_{(n,k,δ)} if α contains a start(v)_{i}action. The set of participating processes in α is called the participating set in α.

A process i is said to decide in an execution α when it executes a finish(S)_{i}action. After executing a finish(S)_{i}action, a process i does not take any further steps in α. The value S returned by the finish(S)_{i}action is process i’s output value in α.

For any execution α of P_{(n,k,δ)}, the processes’ input values can conveniently be represented using an n + 1-dimensional input vector I⃗, as specified in the previous subsection, with input data type D. The i-th entry of I⃗ is the input of process i. Similarly, the processes’ output values in α can be represented using an n + 1dimensional output vector O⃗. The i-th entry of O⃗ is the output of process i.

It should be noted that the notions of participating processes and sets defined for executions and input vectors are consistent; A process i participates in an execution α if and only if the index i participates in the input vector I⃗ corresponding to α. Therefore, when the meaning is clear from the context, we usually omit qualifying a participating set with an execution or input vector.

In any execution α of P_{(n,k,δ)}, each participating, non-failing process i starts by accessing the first IS object by executing a writeread(v)_{i,IS_{1}} action, where v is equal to local state, which initially contains the input of process i. The response consists of a snapshot S_{i} ∈ ϑ(D) of the first IS object’s shared memory vector, containing the input values of some of the participating processes. In particular, process i’s input is always contained in the output i receives. Upon receiving the response S_{i}, process i copies this value to its local statevariable, after which it accesses the second IS object by executing a writeread(local state)_{i,IS_{2}}action. In effect, the output from the first IS object is used as an input to the second. Each non-failing, participating process accesses exactly k IS objects in sequence in this manner, for some integer k, before deciding. The number k of IS objects accessed is the same for each non-failing, participating process in any execution of the protocol. Once a process has received an output from the k-th IS object and stored this value in the local statevariable, it applies a task specific decision map μ to this value, stores the result in local state, and halts. The local statevariable now contains the process’ decision value.

A stylized interconnection diagram of the k-shot IIS model is given in Figure 6. The diagram does not show any internal actions, nor does it show the startand decideactions of the processes.

2.5 The Non-Uniform Iterated Immediate Snapshot (NIIS) Model

In this subsection, we generalize the IIS model by introducing the Non-Uniform IIS (NIIS) model. In the standard IIS model, the number of IS objects available is finite, and the number of IS objects accessed is fixed over all processes and all executions. The NIIS model, however, assumes an infinite sequence IS_{D}^{n+1}, IS_{ϑ(D)}^{n+1}, IS_{ϑ^{2}(D)}^{n+1}, … of IS objects, denoted IS_{1}, IS_{2}, IS_{3}, . . .. The number of IS objects accessed by any two distinct processes in a given execution need not be the same, and, moreover, the number of objects accessed by any fixed process may vary from execution to execution. The motivation behind this is to be able to model complexity more accurately, as will be shown in later subsections.

Each protocol in the NIIS model is characterized by the maximum number n + 1 of processes that can participate, a predicate function τ : ⋃_{l=0}^{k} ϑ^{l}(D) → {true, false}, which each process applies to its local statevariable after each complete writereadoperation to determine whether or not to decide, and a decision map

Process i

Signature

Inputs:

ret writeread(S)_{i,IS_{x}}S ∈ ⋃_{l=1}^{k} ϑ^{l}(D).

start(v)_{i} v ∈ D. Internals:

Outputs:

inv writeread(v)_{i,IS_{x}}v ∈ ⋃_{l=0}^{k} ϑ^{l}(D). finish(S)_{i} S ∈ ϑ^{k}(D).

State

local state ∈ (⋃_{l=0}^{k} ϑ^{l}(D)) ∪ {⊥}, initially in the fresh state ⊥. counter ∈ ℤ, initially 1.

Transitions

input: ret writeread(S)_{i,IS_{x}}

Eff: local state := S counter := counter+1

output: inv writeread(v)_{i,IS_{x}}

Pre: counter = j ≤ k

local state = v ≠ ⊥ Eff: input: start(v)_{i}

Eff: local state := v

output: finish(S)_{i} Pre: counter > k

μ(local state) = S

Eff:

Fig. 5. I/O Automaton for process i running k-shot IIS protocol.

δ : ⋃_{l=0}^{k} ϑ^{l}(D) → D_{O}, where D_{O} is an arbitrary data type, which we call the protocol’s output data type. We refer to the protocol obtained by fixing these parameters as P_{(n,τ,δ)}.

We can specify the P_{(n,τ,δ)} protocol using I/O automata [15] As Follows. Each IS Object is specified as in Figure 3, and each process i is specified as in Figure 7. The protocol P_{(n,τ,μ)} can then be specified by composing the automata for the processes with the IS object automata by matching up operations as follows. Assume that for each process i, the x-th IS object, IS_{x}, is connected to the x-th port on i, and for each IS object IS_{x}, the i-th process is connected to the i-th port on IS_{x}. For each processor i and IS object IS_{x}, we match up i’s and IS_{x}’s inv writeread(v)_{i,IS_{x}}and ret writeread(S)_{i,IS_{x}}actions. The resulting protocol automaton is denoted P_{(n,k,μ)} = {0, 1, …, n; IS_{1}, IS_{2}, …, IS_{k}}.

The only difference between protocol P_{(n,τ,δ)} is the NIIS model and a protocol in the IIS model is that after each complete writereadoperation, each process checks whether it has reached a final state by applying the predicate τ to the local statevariable. If τ returns true, the process executes a finish(S)_{i}action and halts. Otherwise, it accesses the next IS object as in the IIS model, and so on. In fact, any protocol P_{(n,k,δ)} in the IIS model is in fact equivalent to a protocol P_{(n,τ,δ)} in the NIIS model, in which the predicate τ simply checks whether or not the local statevariable is of type ϑ^{k}(D) or not.

Fig. 6. Diagram of the k-shot IIS model.

A stylized interconnection diagram of the NIIS model is given in Figure 6. The diagram does not show any internal actions, nor does it show the startand decideactions of the processes

2.6 Solvability of Decision Tasks

In this subsection we specify more precisely what it means to solve a decision task in the NIIS model. Since the IS and IIS models are equivalent to special cases of the NIIS model, the definitions below also apply directly to these models.

Definition 2.22. Suppose we are given a decision task D = ⟨I, O, γ⟩, and an execution α of a protocol P_{(n,τ,δ)} in the NIIS model, with corresponding input and output vectors I⃗ and O⃗, respectively. Then P_{(n,τ,δ)} solves D in α if the following two conditions hold:

—No process takes an infinite number of steps in α. —O⃗ is a vector in γ(I⃗).

Process i

Signature

Inputs:

ret writeread(S)_{i,IS_{x}}S ∈ ⋃_{l=1}^{k} ϑ^{l}(D).

start(v)_{i} v ∈ D. Internals:

Outputs:

inv writeread(v)_{i,IS_{x}}v ∈ ⋃_{l=0}^{k} ϑ^{l}(D). finish(S)_{i} S ∈ ⋃_{l=0}^{k} ϑ^{l}(D).

State

local state ∈ (⋃_{l=0}^{k} ϑ^{l}(D)) ∪ {⊥}, initially in the fresh state ⊥.

Transitions

input: ret writeread(S)_{i,IS_{x}} Eff: local state := S

output: inv writeread(v)_{i,IS_{x}}

Pre: τ(local state) = false local state = v ≠ ⊥

Eff: input: start(v)_{i}

Eff: local state := v

output: finish(S)_{i}

Pre: τ(local state) = true μ(local state) = S

Eff:

Fig. 7. I/O Automaton for process i running NIIS protocol.

Note that γ(I⃗) is prefix-closed by assumption, so the vector O⃗ does not necessarily contain an output value for each non-⊥ i in I⃗. Informally, this means that if P_{(n,τ,δ)} solves a task in an execution α, its partial outputs in any prefix α′ of α are also a valid solution to the task.

Definition 2.23. A protocol P_{(n,τ,δ)} solves a decision task D = ⟨I, O, γ⟩ if it solves it in every execution α.

We are particularly interested in protocols that guarantee strong fault-tolerance conditions. The failure model model we shall be concerned with only involves stopping failures, that is, we assume that processes may simply stop without warning. We do not consider other, more complicated models, such as the Byzantine failure model, in which processes may exhibit arbitrary behaviour. In this paper, we will focus on protocols with the property that any non-failing process will eventually decide, independent of the progress of the other processes;

Definition 2.24. A protocol P_{(n,τ,δ)} solves a decision task D = ⟨I, O, γ⟩ waitfree if it solves it in every execution where up to n processes can fail.

Fig. 8. Diagram of the NIIS model.

2.7 Complexity Measures for the IIS and NIIS Models

We now define the complexity measures to be used for analyzing the performance of protocols in the NIIS model. Since the IIS model is equivalent to a special case of the NIIS model, these measures also apply directly to the IIS model.

Let P_{(n,τ,δ)} be a protocol in the NIIS model solving a given decision task D, let I be an input vector, and let α be any execution of P_{(n,τ,δ)} that starts with the inputs in I. For all i, let t_{i} be the number of IS objects accessed by process i in α. Clearly, t_{i} is an integer. We first define the time complexity of the execution α.

Definition 2.25. The time complexity of α, denoted t_{α}, is max_{i} t_{i}, the maximum number of IS objects accessed by any process.

We note that t_{α} is well-defined, since the number of processes n + 1 is finite. Moreover, by definition of the max function, t_{α} is an integer value. We use the definition given above to define the time complexity of the protocol P on the input vector I⃗.

Definition 2.26. The time complexity of P_{(n,τ,δ)} on I⃗, denoted tI⃗, is the supremum of the set {t_{α} | t_{α} is an execution starting from I⃗}.

Finally, we define the complexity of a protocol P_{(n,τ,δ)} on a set of input vectors I.

Definition 2.27. The time complexity of P_{(n,τ,δ)} on I, denoted t_{I}, is the supremum of the set {t_{α} | tI⃗ ∈ I}.

The reason for preferring these simple, discrete complexity measures over other, more elaborate measures such as real time, for instance, is the highly regular structure of the NIIS model. We make the assumption that each access to an IS object takes the same amount of time, and do not worry about breaking up the time required to complete each access to an IS object into subparts. Instead, we group the time spent on invocation, response, and on local computation at the IS object. This assumption is somewhat strong, as the presence of asynchrony in our model will tend to introduce varying delays for each access to an object. However, we believe that, as a first step towards a complexity theory, this assumption is justifiable, as it allows for complexity measures that are simple and easy to apply, and that have a particularly nice topological representation, as we will see in Section 3.

The motivation behind introducing non-uniformity to the IIS model is to give a more accurate description of the complexity of solving decision tasks. The required amount of computation in order to solve a given decision task may vary from process to process, from input value to input value, and indeed from execution to execution. In a uniform model such as the IIS model, however, all processes will always take the same number of steps in a given execution, and any process will take the same number of steps in all executions in which it participates. This property makes it impossible to construct a satisfactory complexity theory in such a model. Thus, the introduction of non-uniformity allows us to more accurately capture the complexity of solving decision tasks.

3. A TOPOLOGICAL FRAMEWORK

In this section we first introduce some known tools from the field of algebraic topology and show how they may be used to model decision tasks and protocols in the NIIS model of computation. We then introduce a new tool for analyzing complexity in this setting, called the non-uniform iterated chromatic subdivision.

3.1 Basic Topological Definitions and Concepts

This subsection introduces the basic topological definitions and concepts that we shall need for modeling decision tasks and wait-free protocols in the NIIS model. Some of these definitions are fairly standard, and are mainly taken from popular textbooks on algebraic topology [16; ?], whilst others are due to Herlihy and Shavit [13; 14]. Some of the figures used in this subsection are also adopted from Herlihy and Shavit’s work [13; 14].

A vertex v⃗ is a point in a high-dimensional Euclidian space R^{l}. A set {v⃗_{0}, …, v⃗_{n}} of vertexes is geometrically independent if and only if the set of vectors {v⃗_{i} − v⃗_{0}}_{i=1}^{n} is linearly independent. We can now define the concept of a geometric simplex, or simplex for short.

Definition 3.1. Let {v⃗_{0}, …, v⃗_{n}} be a geometrically independent set of vertexes in R^{l}. We define the n-simplex S spanned by v⃗_{0}, …, v⃗_{n} to be the set of all points x such that x = ∑_{i=0}^{n} t_{i}v⃗_{i} where ∑_{i=0}^{n} t_{i} = 1 and t_{i} ≥ 0 for all i.

For example, a 0-simplex is a vertex, a 1-simplex a line segment, a 2-simplex a solid triangle, and a 3-simplex a solid tetrahedron. For an example of a 2simplex see Figure 9. For simplicity, we often denote the simplex spanned by a set {v⃗_{0}, …, v⃗_{n}} of geometrically independent vertexes as (v⃗_{0}, …, v⃗_{n}). The number n is called the dimension of the simplex S, and is often denoted by dim(S). For clarity, we sometimes will include the number n as an explicit superscript when referring to a simplex, that is, we will write S^{n} to refer to the simplex spanned by the vertexes in {v⃗_{0}, …, v⃗_{n}}.

Any simplex T spanned by a subset of {v⃗_{0}, …, v⃗_{n}} is called a face of S. The faces of S different from S itself are called the proper faces of S. The simplex spanned by the vertexes {v⃗_{0}, v⃗_{1}} is a proper face of the 2-simplex in Figure 9.

The union of the proper faces of S is called the boundary of S, and is denoted Bd(S). The interior of S, denoted Int(S), is defined by the set equation Int(S) = S − Bd(S).

We will use a vertex to model the state of a single process, and a simplex to model consistent states of all the processes involved in solving a decision task or in running a wait-free protocol. To model a collection of such states we need the concept of a geometric, simplicial complex, or complex for short, which is defined below.

Definition 3.2. A geometric simplicial complex K in the Euclidean space R^{l} is a collection of geometric simplexes in R^{l} such that

Fig. 9. Example of a 2-simplex.

—Every face T of every simplex S in K, where dim(T) ≤ dim(S), is contained in

K. —The intersection U of any two simplexes S, T in K, where dim(U) ≤ dim(S), dim(T),

is contained in K.

In this paper we will only consider finite complexes. The dimension of a complex K, often denoted by dim(K), is the highest dimension of any of its simplexes, and is also sometimes indicated explicitly by a superscript. An n-dimensional complex (or n-complex) is pure if every simplex is a face of some n-simplex. All complexes considered in this paper are pure, unless stated otherwise. A simplex S in K with dimension dim(S) = dim(K) is called a maximal simplex.

Given a simplex S, let S denote the complex of all faces of S, and let Ṡ denote the complex consisting of all proper faces of S. We note that, since Ṡ contains all faces of S except S itself, dim(Ṡ) = dim(S) − 1. An example of a pure, 2-dimensional simplicial complex, which we call K, is shown in Figure 10. This complex equals the union of Ṡ and Ṫ, where S is the 2-simplex spanned by {v⃗_{0}, v⃗_{1}, v⃗_{2}}, and T is the 2-simplex spanned by {v⃗_{0}, v⃗_{1}, v⃗_{3}}. Both S and T are maximal simplexes in this example.

If L is a subcollection of K that is closed under containment and intersection, where dim(L) ≤ dim(K), then L is a complex in its own right. It is called a subcomplex of K. For example, the complex Ṡ of faces of S is a subcomplex of K in Figure 10

One subcomplex of a complex K of particular interest is the subcomplex of all

Fig. 10. Example of a pure, 2-dimensional simplicial complex.

simplexes in K of dimension at most p, where p is some integer between 0 and dim(K). We call this subcomplex the p-th skeleton of a K, denoted skel^{p}(K). The elements of the collection skel^{0}(K) are called the vertexes of K. The 0-skeleton of the complex K in Figure 10 is the collection of vertexes {{v⃗_{0}}, …, {v⃗_{3}}}. Similarly, the 1-skeleton of K is the union of the 0-skeleton described above and the collection {{v⃗_{0}, v⃗_{1}}, … {v⃗_{0}, v⃗_{3}}, {v⃗_{1}, v⃗_{2}}, {v⃗_{1}, v⃗_{3}}}.

Let |K| be the subset ⋃_{S∈K} S of R^{l} that is the union of the simplexes of K. Giving each simplex its natural topology as a subspace of R^{l}, we topologize |K| by declaring a subset A of |K| to be closed iff A ∩ S is closed for all S ∈ K. This space is called the polytope of K. Conversely, K is called a triangulation of |K|.

In practice, the geometric representations we have given for simplexes and complexes are not always convenient, since the analytic geometry involved can get quite involved. Therefore, we introduce the notions of abstract simplexes and abstract complexes.

Definition 3.3. An abstract simplex S is a finite, nonempty set.

The dimension of S is its cardinality. Each nonempty subset T of S is called a face of S. Each element of S is called a vertex of S. There is a close relationship between geometric simplexes and abstract simplexes; Any geometrically independent set of vectors {v⃗_{0}, …, v⃗_{n}} not only span a geometric simplex, they also form an abstract simplex.

Definition 3.4. An abstract complex K_{a} is a collection of abstract simplexes, such that if S is in K_{a}, so is any face of S.

Most concepts defined for geometric complexes immediately carry over to abstract complexes; The dimension of K_{a}, often denoted by dim(K_{a}), is the highest dimension of any of its simplexes. An n-dimensional abstract complex (or n-complex) is pure if every simplex is a face of some n-simplex. If L_{a} is a subcollection of K_{a} that is itself an abstract complex, then L_{a} is called a subcomplex of K_{a}.

Definition 3.5. Let K be a geometric complex, and let V be the vertex set of K. Let K_{a} be the collection of all subsets S of V such that S spans a simplex in K. Then K_{a} is called the vertex scheme of K.

Definition 3.6. Two abstract complexes K_{a} and L_{a} are isomorphic if there is a bijective correspondence ψ between their vertex sets such that a set S of vertexes is in K_{a} iff ψ(S) ∈ L_{a}. The bijective correspondense ψ is called an isomorphism.

Theorem 3.7. Every abstract complex K_{a} is isomorphic to the vertex scheme of some geometric complex K in ℝ^{2 dim(K_{a})+1}.

We will not prove this theorem here. For a proof, see any standard textbook on algebraic topology [16; ?]. In the rest of this paper, for convenience, we will often use abstract and geometric representations of simplexes and complexes interchangeably. The remainder of this subsection, however, which introduces a number of important topological concepts, such as simplicial maps, subdivisions and carriers, is set in the context of geometric complexes.

We first define the notions of simplicial vertex maps and simplicial maps from one complex into another.

Definition 3.8. Let K and L be complexes, possibly of different dimensions, and let μ : skel^{0}(K) → skel^{0}(L) be a function mapping vertexes to vertexes. Suppose that whenever the vertexes v⃗_{0}, …, v⃗_{n} of K span a simplex of K, the vertexes μ(v⃗_{0}), …, μ(v⃗_{n}) span a simplex of L. Then μ is called a simplicial vertex map from K to L. μ can be extended to a continuous map μ_{∗} : |K| → |L| such that

x = ∑_{i=0}^{n} t_{i}v⃗_{i} ⇒ μ_{∗}(x) = ∑_{i=0}^{n} t_{i}μ_{∗}(v⃗_{i})

This continuous extension is called a simplicial map from K to L.

For simplicity, we henceforth refer to the simplicial vertex map μ as the simplicial map, without actual reference to the continous extension μ_{∗}, which is less relevant for our purposes. As a further abuse of notation, we usually write μ : K → L when we refer to the simplicial vertex map, glossing over the fact that this map is in fact only defined on the vertexes of K, and that the image of the map is a subset of the

Fig. 11. Example of a simplicial map between two complexes.

vertex set of L. Henceforth, unless stated otherwise, all maps between complexes are assumed to be simplicial. An example of a simplicial map is given in Figure 11

We note that a simplex and its image under a simplicial map need not have the same dimension. A simplicial map μ : K → L is non-collapsing if it preserves dimension, that is, for all S ∈ K: dim(μ(S)) = dim(S).

Definition 3.9. A coloring of an n-dimensional complex K is a non-collapsing simplicial map χ : K → S, where S is an n-simplex.

Intuitively, a coloring corresponds to a labeling of the vertexes of the complex such that no two neighbouring vertexes (connected by a 1-simplex) have the same label. A chromatic complex (K, χ) is a complex K together with a coloring χ of K. An example of a chromatic complex is given in Figure 12, where the colors are the values {1, 2, 3}. When it is clear from the context, we specify the chromatic complex (K, χ) simply as the complex K, omitting explicit mention of the coloring χ.

Let (K, χ_{K}) and (L, χ_{L}) be chromatic complexes, and let μ : K → L be a simplicial map. We say that μ is chromatic if, for every vertex v⃗ ∈ K, χ_{K}(v⃗) = χ_{L}(μ(v⃗)), that is, if μ maps each vertex in K to a vertex in L of the same color. All the simplicial maps we consider in this paper are chromatic.

We can now define the concepts of a subdivision of a complex, and the carrier of a simplex in a subdivision.

Definition 3.10. Let K be a complex in R^{l}. A complex σ(K) is said to be a subdivision of K if the following two conditions hold:

—Each simplex in σ(K) is contained in a simplex in K. —Each simplex of K equals the union of finitely many simplexes in σ(K).

Fig. 12. Example of a 1-dimensional chromatic complex.

An example of a complex and its subdivision is given in Figure 13.

Definition 3.11. If S is a simplex of σ(K), the carrier of S, denoted carrier(S) is the unique smallest T ∈ K such that S ⊂ |T |.

The concept of a carrier of a simplex is illustrated in Figure 14. The original complex is shown on the right, and the subdivided complex is shown on the left. A simplex S in the subdivision and the corresponding carrier carrier(S) in the original complex are highlighted in the figure.

A chromatic subdivision of (K, χ_{K}) is a chromatic complex σ(K), χ_{σ(K)}) such that σ(K) is a subdivision of K, and for all S in σ(K), χ_{σ(K)}(S) ⊆ χ_{K}(carrier(S)). A simplicial map μ : σ_{1}(K) → σ_{2}(K) between chromatic subdivisions of K is carrier

Fig. 13. Example of a pure, 2-dimensional simplicial complex and a subdivision of it.

Fig. 14. The Carrier of a Simplex

preserving if for all S ∈ σ_{1}(K), carrier(S) = carrier(μ(S)). All subdivisions we consider in this paper will be chromatic, unless explicitly stated otherwise.

3.2 Topological Modeling of Decision Tasks

Earlier in this subsection, we defined the notion of a decision task in terms of input and output vectors. That definition was intended to help the reader understand what a decision task is, but it lacks the mathematical structure necessary to prove interesting results. We now reformulate this definition in terms of simplicial complexes.

To illustrate our constructions, we will use the well-known Unique-Id task as an informal example. We will give a formal, topological definition of decision tasks later. The Unique-Id task was introduced earlier, but we restate it here for convenience.

Example 3.12. The n + 1-process Unique-Id task is defined as follows:

—I = {[0, …, n]}. —O = {[x_{1}, …, x_{n}] | ∀i, j : x_{i} ∈ (ℤ)_{n+1} ∪ {⊥} ∧ (x_{i} = x_{j}) ⇒ (x_{i} = ⊥)}. —∀I⃗ ∈ I : O⃗ ∈ γ(I⃗) iff for all i, j, (O⃗[i] = O⃗[j]) ⇒ (O⃗[i] = ⊥).

We represent the (unique) n + 1-dimensional input vector I⃗ = [0, …, n] to the Unique-Id task as a simplex S, called an input simplex, with dimension 0 ≤ dim(S) ≤ n. The dimension of S equals the number of non-⊥ elements in the vector. Each vertex v⃗ in S is labeled with a process id and an input value: ⟨i, v_{i}⟩, where I⃗[i] = v_{i}. We use ids(S) to denote the simplex’s set of process ids, and vals(S) to denote the multiset of values. If J⃗ is a prefix of I⃗, then the simplex corresponding to J⃗ is a face of S. The set I of input vectors is thus modeled as a complex I of input simplexes, called the input complex.

Similarly, we represent each n + 1-dimensional output vector O⃗ = [x_{1}, …, x_{n}], where for all i, j, either x_{i} = ⊥ or 0 ≤ x_{i} ≤ n and (x_{i} = x_{j}) ⇒ (x_{i} = ⊥), as a simplex T, called an output simplex, with dimension 0 ≤ dim(T) ≤ n. Each vertex v⃗ in T is labeled with a process id and an output value: ⟨i, v_{i}⟩, where O⃗[i] = v_{i}. We use ids(T) to denote the simplex’s set of process ids, and vals(T) to denote the multiset of values. If P⃗ is a prefix of O⃗, then the simplex corresponding to P⃗ is a face of T. The set O of input vectors is thus modeled as a complex O of output simplexes, called the output complex.

The task specification map γ induces a topological task specificatin map Γ for the Unique-Id task in the natural way, mapping each input simplex S ∈ I to a set Γ(S) of output simplexes in O, with the property that for all T ∈ Γ(S), the set vals(T) contains no non-⊥ duplicates.

We can now give an alternative, topological representation of the Unique-Id decision task by simply specifying it as a tuple D = ⟨I, O, Γ⟩ consisting of an input complex I, and output complex O, and a topological task specification map, Γ.

Figure 15 shows two triangles (2-simplexes) corresponding to two distinct outputs for the 3-process Unique-Id task, one given by the output vector O⃗_{1} = [0, 1, 2], the other given by the output vector O⃗_{2} = [3, 1, 2]. Notice that the vertexes of each simplex are colored by the appropriate process ids.

This topological representation gives an alternative interpretation of the notion of “similar” system states. The processes corresponding to vertexes on the common boundary of the two simplexes cannot distinguish between the two global output sets based on their own output values. Unlike graph-theoretic models (e.g., [4]), simplicial complexes capture in a natural way the notion of the degree of similarity

Fig. 15. Part of output complex for the 3-proc Unique-Id task.

between the two global output sets: it is the dimension of the intersection of the two 2-simplexes.

We now give a formal procedure for how to specify a given decision task D = ⟨I, O, γ⟩ topologically. We first construct a representation using abstract simplexes and complexes, and then use Theorem 3.7 to construct a representation using geometric simplexes and complexes.

Definition 3.13. Let I⃗ ∈ I be an input vector. The input simplex corresponding to I⃗, denoted S(I⃗), is the abstract simplex (⟨i_{0}, v_{i_{0}}⟩, …, ⟨i_{m}, v_{i_{m}}⟩), where for all i_{j}, where i_{0} ≤ i_{j} ≤ i_{m}, i_{j} ∈ {0, …, n} ∧ I⃗[i_{j}] ≠ ⊥, and for all i, (I⃗[i] = ⊥) ⇒ (i ∉ {i_{0}, …, i_{m}}).

Definition 3.14. Let O⃗ ∈ O be an output vector. The output simplex corresponding to O⃗, denoted T (O⃗), is the abstract simplex (⟨i_{0}, v_{i_{1}}⟩, …, ⟨i_{m}, v_{i_{m}}⟩), where for all i_{j}, where i_{0} ≤ i_{j} ≤ i_{m}, i_{j} ∈ {0, …, n} ∧ O⃗[i_{j}] ≠ ⊥, and for all i, (O⃗[i] = ⊥) ⇒ (i ∉ {i_{0}, …, i_{m}}).

Having defined input and output simplexes, we can define input and output complexes.

Definition 3.15. The input complex corresponding to I, denoted I, is the collection of input simplices S(I⃗) corresponding to the input vectors of I.

Definition 3.16. The output complex corresponding to O, denoted O, is the collection of output simplices T (O⃗) corresponding to the output vectors of O.

We have to prove that these definitions make sense topologically, that is, that the input and output complexes thus defined are in fact abstract complexes. We will do the proof for input complexes in the lemma below. The proof relies on the requirement that the sets of input vectors we consider are prefix-closed.

Lemma 3.17. Given a set I of input vectors. The corresponding input complex I, as defined in Definition 3.15, is an abstract, chromatic complex.

Proof. Clearly, I as defined above is a collection of abstract simplexes. We must show that this collection satisfies the requirements of Definition 3.4, that is, we must establish that I is closed under containment.

Let S(I⃗) = (s⃗_{0}, …, s⃗_{m}) be an abstract simplex of I, and let T = (t⃗_{0}, …, t⃗_{m′}), where m′ ≤ m, be a face of S(I⃗). It follows that skel^{0}(T) ⊆ skel^{0}(S(I⃗)). Consider the vector J⃗, the i-th entry of which is ⊥ iff i ∉ ids(T), and otherwise val(t⃗_{j}), where i = id(t⃗_{j}). We claim that this vector is a prefix of I⃗. Suppose I⃗[i] = ⊥. Then i ∉ ids(S(I⃗)), and hence i ∉ ids(T). It follows that J⃗[i] = ⊥. Now suppose that vJ[i] ≠ ⊥. Then there is a vertex t⃗_{j} in T with id(t⃗_{j}) = i and val(t⃗_{j}) = J⃗[i]. Since skel^{0}(T) ⊆ skel^{0}(S(I⃗)), this vertex is also a vertex of S(I⃗), and so it follows that I⃗[i] = val(t⃗_{j}) = J⃗[i]. It follows that J⃗ is a prefix of I⃗. Since we only consider prefix-closed sets of input vectors, J⃗ must be in I. The simplex corresponding to J⃗, denoted S(J⃗) is equal to T, and hence T is in I.

It follows that I is an abstract complex. Moreover, let S = (s⃗_{0}, …, s⃗_{n}) be any n-simplex. Then the map χ : I → S defined by χ(v⃗) = s⃗_{i}, where i = id(v⃗) is a chromatic and simplicial map from I to S, and hence I is a chromatic, abstract complex, as required. □

Lemma 3.18. Given a set O of output vectors. The corresponding output complex O, as defined in Definition 3.15, is an abstract, chromatic complex.

The proof is identical to the proof of Lemma 3.17, and will be omitted here. Given a pair of (abstract) input and output complexes, we may apply Theorem 3.7 to construct a corresponding pair of geometric chromatic input and output complexes by embedding the abstract complexes in ℝ^{2n+1}. As discussed in Subsection ??, the abstract and geometric representations of a complex are equivalent up to linear isomorphism, and thus we will work with both interchangeably in the remainder of this paper.

We now construct a topological equivalent of the task specification map γ : I → O.

Definition 3.19. The topological task specification map corresponding to γ, denoted Γ, is the map carrying each simplex S(I⃗) of I to a non-empty set of simplexes of O defined as follows.

T (O⃗) ∈ Γ(S(I⃗)) ⟺ O⃗ ∈ γ(I⃗)

Usually, we simply refer to a topological task specification map as a “task specification map”. We now prove two crucial properties of such maps.

Lemma 3.20. For all S(I⃗) ∈ I, and all i, i ∉ ids(S(I⃗)) iff for all T (O⃗) ∈ Γ(S(I⃗)), i ∉ ids(T (O⃗)).

Proof. Suppose i ∉ ids(S(I⃗)). Then I⃗[i] = ⊥ by Definition 3.13, and hence by Definition 2.6, O⃗[i] = ⊥. It follows from Definition 3.14 that i ∉ ids(T (O⃗)). □

Lemma 3.21. The map Γ as defined above preserves process ids: for any simplex S in I, and all T in Γ(T), ids(T) ⊆ ids(S).

Proof. Let S(I⃗) be any simplex in I, and let T (O⃗) ∈ Γ(S(I⃗)). Then O⃗ ∈ γ(I⃗). It follows from Definition 2.6 that, for all i, I⃗[i] = ⊥ ⇒ O⃗[i] = ⊥. Suppose i ∈ ids(T (O⃗)). Then O⃗[i] ≠ ⊥, and hence I⃗[i] ≠ ⊥. It follows from the construction of S(I⃗) that i ∈ ids(S(I⃗)). The claim follows. □

An illustration of a pair of input and output complexes, together with a task specification map relating them, is given in Figure 16.

Definition 3.22. Given a decision task D = ⟨I, O, γ⟩, the corresponding topological representation of the task, denoted D = ⟨I, O, Γ⟩, consists of an input complex I corresponding to I, and output complex O corresponding to O, and a task specification map Gamma corresponding to γ.

In the remainder of this paper, we will specify decision tasks using both Definition 2.7 and Definition 3.22 interchangeably. A set of inputs or outputs may thus be specified as either a vector or as a simplex the vertexes of which are lebeled with process ids and values.

3.3 Topological Modeling of NIIS Protocols

We model protocols in the NIIS model in much the same way that we model decision tasks. As discussed in Section 2, the sets of inputs and outputs for any execution α of a protocol P_{(n,τ,δ)} in the NIIS model can be modeled using n + 1 process input and output vectors. We denote the sets of input vectors and output vectors of a protocol by I and O, respectively. We are only interested in protocols that solve decision tasks, so we may assume that the set I of possible input vectors to a protocol is prefix-closed. The following lemma states that for any protocol in the NIIS model, the set O of possible output vectors must necessarily be prefix-closed.

Lemma 3.23. Let O be the set of possible output vectors of a protocol P_{(n,τ,δ)} in the NIIS model, with corresponding set of input vectors I. Then O is prefix-closed.

Fig. 16. A Decision Task

Proof. Let O⃗ be an output vector produced by the execution α_{O}, and let P⃗ be a prefix of O⃗. We construct an execution α_{P} as follows: For each i such that O⃗[i] = v_{i} ≠ ⊥ = P⃗ [i], remove the action finish(S)_{i}from α_{O}, where S is the snapshot returned by that action (meaning that process i fail-stopped before finishing). Clearly, the execution thus obatined is a possible execution of P_{(n,τ,δ)}, and its output vector is P⃗. Hence P⃗ is in O, and O is prefix-closed. □

Given that both the set of input vectors I and the set of output vectors O associated with a protocol P_{(n,τ,δ)} are prefix-closed sets of vectors, we can construct corresponding input and output complexes, denoted I and P_{(n,τ,δ)}(I), respectively. These complexes are constructed in the same way as the complexes corresponding to input and output sets of vectors for decision tasks, and the proofs that they are indeed chromatic complexes are also identical. The output complex P_{(n,τ,δ)}(I) is called a protocol complex.

Let J be a subcomplex of the input complex I. The set of possible outputs when the protocol is given inputs corresponding to simplexes in J is denoted P_{(n,τ,δ)}(J).

Lemma 3.24. Let J be a subcomplex of I. Then P_{(n,τ,δ)}(J) is a subcomplex of P_{(n,τ,δ)}(I).

Proof. It suffices to show that P_{(n,τ,δ)}(J) is a complex, since P_{(n,τ,δ)}(J) is clearly a subset of P_{(n,τ,δ)}(I). We simply look at the set of vectors J corresponding to the subcomplex J in isloation, as the set of input vectors to the protocol P_{(n,τ,δ)}. This set is prefix-closed since J is a complex, and hence closed under containment. Hence the set P of output vectors given input vecors in J is prefix-closed by Lemma 3.23. It follows from Lemma 3.18 that P_{(n,τ,δ)}(J), the complex corresponding P, is a complex, and hence a subcomplex of P_{(n,τ,δ)}(I). □

In the remainder of this paper, we will specify protocols in NIIS using both its formal specification from Subsection 2.5 as well as protocol complexes as described in this subsection interchangeably. A set of inputs or outputs may thus be specified as either a vector or as a simplex the vertexes of which are lebeled with process ids and values.

3.4 Subdivisions

The standard chromatic subdivision was introduced by Herlihy and Shavit [13; 14], and has since been used by a number of researchers. It is essentially a chromatic generalization of the standard barycentric subdivision from classical algebraic topology [16; ?]. In this subsection, we will present the first complete, formal definition of the iterated standard chromatic subdivision, together with a proof that this definition does indeed correspond to a chromatic subdivision of a given complex. We also introduce the concept of a non-uniform chromatic subdivision, a generalization of the standard chromatic subdivision, in which the different simplexes of a complex are not necessarily subdivided the same number of times. Informally, a non-uniform chromatic subdivision of level 1 of a complex K, denoted by X̃^{1}(K), is constructed by choosing, for each n-simplex in K, a single face of the simplex (a face can be of any dimension and could also be the whole simplex) to which we apply the standard chromatic subdivision. We then induce the subdivision onto the rest of the simplex. This is best seen in Figure 17. Its right hand side shows a valid non-uniform chromatic subdivision of a complex where, for example, the simplex (b, c, d)’s subdivision is the result of subdividing the 1-face (c, d) once and then inducing this subdivision onto the rest of the simplex. The left hand side structure is not a legal subdivision (it is in fact not even a complex). A k-th level non-uniform chromatic subdivision of a complex K, denoted by X̃^{k}(K), is generated by repeating this process k times, where only simplexes in faces that were subdivided in round k − 1 can be subdivided in phase k. The complex on the right hand side of Figure 17 is an example of a non-uniform chromatic subdivision of level 2, since the face (a, d) is subdivided twice.

Later, we will show that these structures correspond in a natural way to the set of protocol complexes in the NIIS model of computation. In fact, it turns out that each non-uniform standard chromatic subdivision is equal to some NIIS protocol complex (up to isomorphism).

3.5 The Standard Chromatic Subdivision

In this subsection we define the standard chromatic subdivision, and prove that this definition does indeed specify a chromatic subdivision of a given complex.

Let K be a pure, n-dimensional, chromatic geometric complex, where the colors are the numbers in ℤ_{n+1}. Label each vertex v⃗ in K with ⟨i, v_{i}⟩, where i is the color of v⃗, and v_{i} is a value in some set D_{I} chosen such that no two vertexes in K have the same label. In order to define the standard chromatic subdivision of K, we inductively define a sequence of subdivisions L_{p} of the skeletons of K, where 0 ≤ p ≤ n as follows. Let L_{0} = skel^{0}(K). Now suppose that L_{p−1} is a

Fig. 17. Valid and Invalid Non-uniform Subdivisions

chromatic subdivision of the p − 1-skeleton of K. Each vertex v⃗ in L_{p−1} is labeled ⟨i, S_{i}⟩, where S_{i} is the vertex scheme of some simplex in skel^{p−1}(K). The labels ⟨i, S_{i}⟩ are such that any T = (t⃗_{0}, …, t⃗_{r}), where r ≤ p − 1, is a simplex in L_{p−1} iff ids(T) ⊆ ids(carrier(T) and the following conditions hold for all 1 ≤ i, j ≤ r:

—id(t_{i}) ≠ id(t_{j}). —id(t⃗_{i}) ∈ ids(val(t⃗_{i})) —val(t⃗_{i}) is a face of val(t⃗_{j}) or vice versa —id(t⃗_{j}) ∈ ids(val(t⃗_{i})) ⇒ val(t⃗_{j}) is a face of val(t⃗_{i})

Let S = (s⃗_{0}, …, s⃗_{p}) be a p-simplex in K. The set Bd(S) is the polytope of a subcomplex of the p−1-skeleton of K, and hence of a subcomplex of L_{p−1}, which we denote L_{Bd(S)}. Let b⃗ be the barycenter of S, and let δ be some positive real number such that 0 < δ < 1. For each 1 ≤ i ≤ p, define m⃗_{i} to be the point (1 + δ)b⃗ − δs⃗_{i}. These points are called the midpoints of S. Label m⃗_{i} with ⟨i, S⟩, S here being the vertex scheme of the geometric simplex S. Let M_{S} be the set of midpoints of S. We define L_{S} to be the union of L_{Bd(S)} and all the faces of all chromatic p-simplexes T = (t⃗_{0}, …, t⃗_{p}), such that for all 1 ≤ i, j ≤ p : t⃗_{i} ∈ skel^{0}(L_{Bd(S)}) ∪ M_{S}, and the following conditions hold:

—id(t_{i}) ≠ id(t_{j}). —id(t⃗_{i}) ∈ ids(val(t⃗_{i})) —val(t⃗_{i}) is a face of val(t⃗_{j}) or vice versa —id(t⃗_{j}) ∈ ids(val(t⃗_{i})) ⇒ val(t⃗_{j}) is a face of val(t⃗_{i})

We now define L_{p} to be the complex consisting of the union of the complexes L_{S}, as S ranges over all the p-simplexes of K. We now prove that this structure makes sense mathematically, that is, that it is in fact a subdivision of the p-skeleton of K.

Lemma 3.25. For all 0 ≤ p ≤ n, L_{p} is a chromatic subdivision of skel^{p}(K).

Proof. We argue by induction. The case p = 0 is trivial. So suppose p > 0, and suppose the claim holds for L_{0}, …, L_{p−1}. We will first prove that L_{p} is a chromatic simplicial complex. To that end, we prove the following auxiliary lemma.

Lemma 3.26. For all p-simplexes S in K, L_{S} is a chromatic complex.

Proof. We must show that L_{S} is closed under containment and intersection. Let U be a simplex in L_{S}, and let V be a face of U, where 0 ≤ dim(V) ≤ dim(U) ≤ p. If U is in L_{Bd(S)}, then so is V, since L_{Bd(S)} is a complex (since L_{p} is a subdivision and hence a complex by assumption). Hence V is in L_{S}. Suppose U is not contained in L_{Bd(S)}. Then U must be the face of a p-simplex T as described above. By definition of L_{S}, all the faces of T, and hence all faces of U, must be in L_{S}. It follows that L_{S} is closed under containment.

Let U, V be simplexes in L_{S}, and suppose their intersection, denoted by W, is nonempty. If U, V are both in L_{Bd(S)}, it follows immediately that V^{r} is in L_{Bd(S)} and hence in L_{S}. Similarly, if U is in L_{Bd(S)} but V is not, then W = U ∩ V = U ∩(V ∩|L_{Bd(S)}|). Note that V ∩|L_{Bd(S)}| is a simplex in L_{Bd(S)}, since all the criteria given above are satisfied. Hence it follows that W is in L_{Bd(S)}, and hence in L_{S}. If neither U nor V is in L_{Bd(S)}, then since all faces of U and V are in L_{S}, then so is W. It follows that L_{S} is closed under intersection, and hence is a complex. That L_{S} is chromatic follows from the fact that we only include chromatic simplexes in L_{S} in our construction (note that L_{p−1} and hence L_{Bd(S)} are chromatic by assumption).

□

Notice that for all distinct p-simplexes S, T we have that |L_{S}| ∩ |L_{T} | = S ∩ T, which is a simplex in skel^{p−1}(K), and hence is the polytope of a subcomplex of L_{p−1}, and hence of both L_{S} and L_{T}. It follows that L_{p} is a simplicial complex [16]. It remains to show that L_{p} is a chromatic subdivision. To this end, we must first show that every simplex in L_{p} is contained in some simplex in skel^{p}(K), and that every simplex in skel^{p}(K) is the union of finitely many simplexes in L_{p}. Now, it is clear from our construction that any simplex T_{q} in L_{p} is contained in some simplex S in skel^{p}(K). Also, since for all simplexes S in skel^{p}(K), the set of midpoints

Fig. 18. Example of a 2-dimensional complex and its standard chromatic subdivision.

is finite, and L_{p−1} is a subdivision of skel^{p−1}(K) by assumption, it follows that S is the union of finitely many simplexes in L_{p}. Hence L_{p} is a subdivision. This subdivision is chromatic, since L_{p−1} is chromatic by assumption, since the colors used to color the midpoints of any simplex S are exactly the colors used to color S, and since any simplex in L_{p} including midpoints must satisfy the requirement that no two vertexes have the same color (id). □

We are now ready to give our definition of the standard chromatic subdivision of a complex K.

Definition 3.27. The standard chromatic subdivision of K, denoted X (K), is the complex L_{n}.

An example of a complex and its standard chromatic subdivision is given in Figure 18.

Applying the standard chromatic subdivision k times, where k > 1, yields a subdivision X^{k}(K) = X (X^{k−1}(K)), which we call the kth iterated standard chromatic subdivision [13; 14]. Since the standard chromatic subdivision of a complex is again a complex, and a chromatic subdivision of a chromatic subdivision of K is itself a chromatic subdivision of K, X^{k}(K) is a chromatic subdivision of K. The number k is called the level of the subdivision.

We will mostly use the vertex scheme representation of the standard chromatic subdivision, as it has a particularly compact representation, as stated in the lemma below.

Lemma 3.28. Let K be a pure, chromatic complex of dimension n. The vertex scheme of X (K) is the closure under containment of the set of all n-simplexes of the form S = (⟨0, S_{0}⟩, …, ⟨n, S_{n}⟩), where for all i, S_{i} is the vertex scheme of some face of a simplex S in K, and the following conditions hold for all i, j:

—i ∈ ids(S_{i}).

—S_{i} is a face of S_{j} or vice versa.

—If j ∈ ids(S_{i}), then S_{j} is a face of S_{i}.

Proof. We argue by induction on k, where 0 ≤ k ≤ n. It is immediate that the simplexes of X (K) lying in the subdivision L_{0} of skel^{0}(K) are of this form (each such simplex is a vertex of K labeled with a process id and a value), and the requirements above are all satisfied trivially.

Now suppose the claim holds for 0, …, k − 1. Consider a simplex T lying in the subdivision L_{k} of skel^{k}(K) and not in L_{k−1}. Then T = U ⋆ V, where U is a simplex in L_{k−1}, and V is a simplex each vertex of which is one of the midpoints in M_{S}, where S = carrier(T). By assumption, V is non-trivial, meaning that there is at least one vertex in V. Howeover, U may be trivial. For each vertex v⃗ in V, val(v⃗) = S, the vertex scheme of S. Hence for i, j in ids(V), since ids(V) ⊆ ids(S), all the conditions listed above are clearly satisfied. For i, j in ids(U), the conditions are satisfied by induction. Now suppose i is in ids(U), while j is in ids(V). Notice that S_{i} = carrier(U), and S_{j} = carrier(V) = S.

The first condition follows by induction (for i) and since ids(V) ⊆ ids(S) = vals(V) (for j). Since carrier(U) is a face of S, it follows that S_{i} is a proper face of S, and hence of S_{j}, which equals the vertex scheme of S, and so the second condition is satisfied. It is clear that i is in ids(S_{j}), since S_{j} equals the vertex scheme of S, and i is in ids(carrier(U)), which is a subset of ids(S). That S_{i} is a face of S_{j} has already been established. It follows that, since X (K) is chromatic, ids(U)∩ids(V) = emptyset, ids(S_{i}) ⊆ ids(carrier(U)), and j is not in ids(carrier(U)), j cannot be in ids(S_{i}). It follows that the third condition is satisfied. □

In the remainder of this paper, we will usually work with this description of the standard chromatic subdivision, and refer to it as X (K). Whenever the distinction between the geometric and abstract representations of X (K) is significant, it will be mentioned explicitly.

3.6 The Non-Uniform Chromatic Subdivision

In this subsection, we define the non-uniform chromatic subdivision, and prove that this definition does indeed specify a chromatic subdivision of a given complex.

Definition 3.29. Let K be a pure n-dimensional chromatic complex, where the colors are the numbers in Z_{n+1}. We will give a recursive definition of a non-uniform chromatic subdivision of K. In general, we denote a k-level non-uniform chromatic subdivision of a complex K by X̃^{k}(K), for k ≥ 0.

If dim(K) = 0, then for all k ≥ 0, X̃^{k}(K) is K itself. Now suppose dim(K) > 0. Then X̃^{0}(K) is K itself. For k > 0, X̃^{k}(K) is given by the following procedure: Partition the vertexes of K into two disjoint sets, A and B, where A is nonempty. From these sets we construct two complexes, denoted by A and B, respectively, as follows: A simplex S in K is in A if the vertexes spanning S are all in A, and it is in B if its spanning vertexes are all in B. The subdivision X̃^{k}(K) is the complex consisting of all simplexes in B, all simplexes in X̃^{k−1}(X (A)), and all simplexes of the form S ⋆ T, where S is a simplex in X̃^{k−1}(X (A)), T is a simplex in B, and carrier(S) ⋆ T is a simplex in K.

Informally speaking, a non-uniform chromatic subdivision of level k is one in which there is some simplex in K which is subdivided k times, but no simplex that is subdivided more than k times. Note that the k level standard chromatic subdivision is a special case of the k level non-uniform chromatic subdivision. Hence for all k ≥ 0, there exists some non-uniform chromatic subdivision of level k. Our definition of non-uniform chromatic subdivisions is designed to easily model protocol complexes of the NIIS model. At any level of the recursion, the vertexes in A can be thought of as corresponding to processes that continue computing given their current local state, while the vertexes in B correspond to processes that decide. An example of a level 1 non-uniform chromatic subdivision of a 2-complex K is given in Figure 19, and an example of a level 2 non-uniform chromatic subdivision of a slightly bigger 2-complex L is given in Figure 20. Note that in Figure 20 the complex A for the second level of recursion is isomorphic to the complex A for the first level of recursion in Figure 19.

Lemma 3.30. Any non-uniform chromatic subdivision X̃^{k}(K) is a chromatic subdivision of K.

Proof. We first note that X̃^{k}(K) is well-defined, since each recursive step lowers the level of subdivision by 1, and X̃^{0}(K) is defined for all K. We will prove that X̃^{k}(K) is a chromatic subdivision by induction on k.

The case where k = 0 is trivial, since X̃^{0}(K) = K. Now suppose that k > 0, and that for 0 ≤ l ≤ k − 1, and any complex K, X̃^{l}(K) is a chromatic subdivision of K. If B = ∅, the result follows by induction and by Lemma 3.25. So suppose that B is nonempty.

We first show that X̃^{k}(K) is closed under containment. Let U be a simplex in X̃^{k}(K), and let V be a face of U. If U is in B, then so is V, since B is a complex. Hence V is in X̃^{k}(K). Similarly, if U is in X̃^{k−1}(X (A)), then so is V, since X̃^{k−1}(X (A)) is a complex by our induction hypothesis. Now suppose U = S⋆T for some S in X̃^{k−1}(X (A)), T in B. Then S ∩ V is in X̃^{k−1}(X (A)), and T ∩ V is in B. It follows that V = (S ∩ V) ⋆ (T ∩ V), where carrier(S ∩ V) ⋆ (T ∩ V) is a simplex in K. By Definition 3.29, V is in X̃^{k}(K). It follows that X̃^{k}(K) is closed under containment.

Let U, V be simplexes in X̃^{k}(K), and let W be their intersection. If both U, V are in B, then so is W, since B is closed under intersection. Similarly, if both

Fig. 19. Example of level 1 non-uniform chromatic subdivision of a 2-complex.

U and V are in X̃^{k−1}(X (A)), then so is W, since X̃^{k−1}(X (A)) is closed under intersection. If U is in B and V is in X̃^{k−1}(X (A)), or vice versa, then U ∩ V = ∅, and so containment under intersection holds vacuosly. We now consider the case where either U or V is not contained in either complex, that is, suppose U = S ⋆ T for some S in X̃^{k−1}(X (A)), T in B, and V = X ⋆ Y for some X in X̃^{k−1}(X (A)), Y in B. Now, U ∩ V = (S ⋆ T) ∩ (X ⋆ Y), and (S ⋆ T) ∩ (X ⋆ Y) = (S ∩ X) ⋆ (T ∩ Y) [16]. If S ∩ X = ∅ or T ∩ Y = ∅, then one of the cases discussed above applies, and V is in X̃^{k}(K). So suppose now that S, T, X, Y, and the intersections S ∩ X and Y ∩ T are all nonempty. Since carrier(S ∩ X) is a face of both carrier(S) and carrier(X), it follows that carrier(S ∩ X) ⋆ T and carrier(S ∩ X) ⋆ Y are simplexes in K, and so is their intersection carrier(S ∩ X) ⋆ (T ∩ Y), since K is a complex. It follows that V is inX̃^{k}(K). This concludes the proof that X̃^{k}(K) is a complex. That it is a chromatic complex follows directly from Lemma 3.25.

We now prove that X̃^{k}(K) is a chromatic subdivision. Given a simplex U in X̃^{k}(K). If U is in B then U is clearly contained in a simplex in K, namely itself, and that the colors of U are contained in the set of colors of its carrier. If U is in X̃^{k−1}(X (A)), it follows by induction and Lemma 3.25 that U is contained in some some simplex carrier(U) in A, and hence in K, and that the colors of U are a subset of the colors of its carrier. Now suppose U = S ⋆ T, where carrier(S) ⋆ T

Fig. 20. Example of level 2 non-uniform chromatic subdivision of a 2-complex.

is in K. Then U is contained in carrier(S) ⋆ T, and the colors of U are a subset of the colors of carrier(S) ⋆ T. Now consider any simplex U in K. We can decompose it into two disjoint faces S and T, such that S ∈ A and T ∈ B. The simplex S is subdivided according to X̃^{k−1}(X (A)), which by induction and Lemma 3.25 consists of finitely many simplexes. The simplex T is not subdivided at all. It follows that the subdivision X̃^{k}(K) subdivides U into finitely many simplexes (those in X̃^{k−1}(X (S)) ⋆ T). This completes the proof that X̃^{k}(K) is a chromatic subdivision.

□

A non-uniform subdivision X̃^{k}(K) of a complex induces a non-uniform chromatic subdivision of any subcomplex L of K. The level of the induced subdivision of L may vary from subcomplex to subcomplex.

Definition 3.31. Let K be a chromatic complex, L a subcomplex or simplex of K, and let X̃^{k}(K) be a non-uniform iterated chromatic subdivision of K. We denote its restriction to simplexes in L for X̃^{k}(L). The level of X̃^{k}(K) on L is the maximal level of subdivision of X̃^{k}(L), which we denote by k_{L}.

It is clear that for any subcomplex or simplex L of K, it must be the case that the level of X̃^{k}(K) on L is less than or equal to k.

4. THE ASYNCHRONOUS COMPLEXITY THEOREM

The strength and usefulness of the NIIS model of computation comes from the fact that each of its associated protocol complexes has a nice, recursive structure. In fact, it turns out that any protocol complex of NIIS is equal to some non-uniform iterated chromatic subdivision of the input complex, and vice versa. This is the essence of our main theorem, which we state and prove in this section.

The level of subdivision necessary for the existence of a simplicial map from the input to the ouput complex of a decision task that agrees with the task specification can be interpreted as a topological measure of the task’s time complexity. The following definition introduces the concept of mapability, which is a useful construct for reasoning about this topological measure.

Definition 4.1. Given a decision task D = ⟨I, O, Γ⟩ and a non-negative integer k, we say that X̃^{k}(I) is a mapable subdivision of the input complex, and k is a mapable level of subdivision if there exists some chromatic simplicial map μ from X̃^{k}(I) to O such that for all T in X̃^{k}(I), μ(T) ∈ Γ(T).

This definition extends naturally to individual simplexes as the map induces different levels of subdivision on the individual simplexes in accordance with the idea that, in order to solve a decision task, some processes may have to do more computational work than others, and some inputs may require more computation than others. We can now state our main theorem:

Theorem Time Complexity. A decision task D = ⟨I, O, Γ⟩ has a wait-free protocol in the NIIS model with worst case time complexity k_{S} on inputs in S, where S is a simplex in I, if and only if there is a mapable non-uniform iterated chromatic subdivision X̃^{k}(I^{n}) with level k_{S} on S.

Keeping in style with Herlihy and Shavit [13; 14], the theorem simply states that solvability of a decision task D = ⟨I, O, Γ⟩ in the IIS model is equivalent to the existence of a chromatic simplicial map μ from some non-uniform chromatic subdivision X̃^{k}(I) to O that agrees with the task specification Γ, that is, for all T in X̃^{k}(I), μ(T^{m}) ∈ Γ(T). The level k_{S} is a lower bound on the worst case time complexity of solving this task with inputs in S in the IIS model.

The theorem also immediately provides a matching upper bound given the subdivision and simplicial mapping. Simply run the normal form protocol of Figure 7. Since each process can locally store the subdivision and mapping, the termination predicate vmap τ just needs to test if the local statevariable is equal to some node v in the subdivison and if so return μ(v).

In the remainder of this section, we will give a proof of our asynchronous time complexity theorem. We first state and prove a lemma about the protocol complex of a protocol in the IIS model with only one available IS object, which we call the 1-Shot IS model.

Lemma 4.3. Let A be an input complex in the 1-Shot IS model. The corresponding protocol complex is isomorphic to X (A).

Proof. We will construct an isomorphism Ψ from the abstract complex P_{(n,τ,δ)}(A) to the abstract complex (vertex scheme) X (A). Let v⃗ = ⟨i, S_{i}⟩ be any vertex in P_{(n,τ,δ)}(A). Then Ψ(v⃗) = ⟨i, T_{i}⟩, where T_{i} is the simplex in A such that for all j, S_{i}[j] = v_{j} if and only if ⟨j, v_{j}⟩ ∈ T_{i}. Notice that this isomorphism is chromatic, that is, the id of a vertex equals the id of its image under Ψ.

We must show that a set of vertexes v⃗_{0}, …, v⃗_{m} in skel^{0}(P_{(n,τ,δ)}(A)), where m ≤ n, form a simplex in P_{(n,τ,δ)}(A) if and only if the set of vertexes Ψ(v⃗_{0}), …, Ψ(v⃗_{m}) in skel^{0}(X (A)) form a simplex in X (A). Suppose without loss of generality that for all i, where 0 ≤ i ≤ m, v⃗_{i} = ⟨i, S_{i}⟩, where S_{i} ∈ ϑ(D_{I}), and D_{I} is the input data type (that is, the id of the i-th vertex is i).

Suppose that the vertexes v⃗_{0}, …, v⃗_{m} do form a simplex V in in P_{(n,τ,δ)}(A). This output simplex corresponds to some execution α in the 1-shot IS model, with corresponding input simplex U in A. Each vertex in U is labeled with a process id i and an input value v_{i} ∈ D_{I}. Notice that dim(V) ≤ dim(U), since some participating processes may not decide, that is, they may fail before executing a finishaction.

From Lemma 2.17, we have that, for any vertex v⃗_{i} = ⟨i, S_{i}⟩ in V, S_{i}[i] = v_{i}. This implies that ⟨i, v_{i}⟩ is in T_{i}. From Lemma 2.19, we have that, for any two vertexes v⃗_{i} = ⟨i, S_{i}⟩ and v⃗_{j} = ⟨j, S_{j}⟩ in V, either S_{i} is a prefix of S_{j} or vice cersa. Suppose without loss of generality that S_{j} is a prefix of S_{i}. Then for all x, where 0 ≤ x ≤ n, if S_{i}[x] = ⊥, then S_{j}[x] = ⊥, and if S_{j}[x] ≠ ⊥¡ then S_{i}[x] = S_{j}[x]. It follows that if ⟨x, v_{x}⟩ is in T_{j} it is also in T_{i}, and if x is not in ids(T_{i}), then it is also not in ids(T_{j}) This implies that T_{j} is a face of T_{i}. From Lemma 2.20, it follows that, if S_{i}[j] = v_{j}, then S_{j} is a prefix of S_{i}. This means that, if ⟨j, v_{j}⟩ is in T_{i}, then T_{j} is a face of T_{i}.

Now suppose that the vertexes Ψ(v⃗_{0}), …, Ψ(v⃗_{m}) in skel^{0}(X (A)) form a simplex V in X (A). We will construct an execution α with corresponding output simplex U such that Ψ(U) = V. Let W = carrier(V). Partition the set ids(V) into a collection of nonempty concurrency classes of process ids, C_{1}, …, C_{k} for some k ≥ 0, such that any two process indices i, j are in the same concurrency class if and only if T_{i} = T_{j}.

We can define a total order ≺ on this collection of concurrency classes as follows. Let C_{x}, C_{y} be distinct concurrency classes. Then C_{x} ∩ C_{y} = ∅. Since both classes are nonempty, we can pick an element from each, say i ∈ C_{x} and j ∈ C_{y}. By assumption, T_{i} ≠ T_{j}. Then be Lemma 3.28, either T_{i} is a face of T_{j} or T_{j} is a face of T_{i}. In the first case, let C_{x} ≺ C_{y}, and in the second case, let C_{y} ≺ C_{x}. The faces of a simplex are totally ordered, and hence ≺ is a total order of the concurrency classes.

Now use this ordered partition of the participating processes in α to define a second partition C′_{1}, …, C′_{k} of the set ids(W) as follows. For each concurrency class C of ids(V), define a concurrency class C′ of ids(W) as follows. C′ is the union of C and all i ∈ ids(W) − ids(V) such that C is the least concurrency class (as determined by ≺) such that for all j ∈ C, i ∈ T_{j}. Note that this is a partition of all of ids(W) since W = carrier(S). This partition gives us a new collection of concurrency classes C′_{1}, …, C′_{k}.

We are now ready to construct α. First position update_{C′_{i}} actions in increasing order according to the ≺ ordering. For each concurrency class C′_{x}, position the inv writeread(v)_{i,IS_{1}} actions of all i such that i ∈ C_{x} immediately before the update_{C′_{x}} action (their internal ordering does not matter). Similarly, position the ret writeread(v)_{i,IS_{1}} actions of all i such that i ∈ C_{x} and i ∈ ids(V) immediately after the update_{C′_{x}} action, but before the inv writeread(v)_{i,IS_{1}} actions associated with the next concurrency class C′_{j}. Processes i whose index is not in ids(W) do not participate and hence take no steps in α. Processes i whose index is not in ids(V) do not execute a ret writeread(v)_{i,IS_{1}}action. By construction, each deciding process i decides S_{i} in α, as required. The lemma follows. □

We now consider the protocol complex of a protocol in NIIS with time complexity 1 on the input complex I.

Lemma 4.4. The protocol complex P_{(n,τ,δ)}(I) of any NIIS protocol of time complexity 1 with input complex I is equal to some non-uniform chromatic subdivision X̃^{1}(I).

Proof. We will show how to construct the protocol complex P_{(n,τ,δ)}(I), and prove this construction is in accordance with Definition 3.29.

Consider any vertex v⃗ in I. It is labeled with ⟨i, v_{i}⟩, where i is a process id and v_{i} represents an input value to process i. According to the specification of NIIS protocols in Section ??, process i will (provided it does not fail), upon having received the input v_{i}, either execute an action inv writeread(v)_{i,IS_{1}} or finish(S)_{i}, depending on whether τ(local state) evaluates to true or not. In this way, the predicate map τ induces a partition of the vertexes of I into two disjoint sets A and B. Since the time complexity of P_{(n,τ,δ)} on any input simplex in I is 1, the set A must be nonempty. We now construct complexes A and B as in Definition 3.29, that is, a simplex T in I is in A if and only if all its vertexes are in A, and it is in B if and only if all its vertexes are in B.

The vertexes in A correspond to processes that, based on their input values, execute an inv writeread(v)_{i,IS_{1}} action with the object IS_{1}. By Lemma 4.3, the protocol complex P_{(n,τ,δ)}(A) equals X (A). A simplex U is in P_{(n,τ,δ)}(I) if and only if it corresponds to an output vector of an execution α of the protocol. In any execution α of the protocol, some of the participating, non-failing processes decide on their input values (corresponding to vertexes in B), while some decide on the snapshots they receive from the object IS_{1} (corresponding to vertexes in P_{(n,τ,δ)}(A)). It follows that P_{(n,τ,δ)}(I) contains any simplex in B, any simplex in P_{(n,τ,δ)}(A) = X (A), and any simplex of the form S ⋆ T, where S is in X (A), T is in B, and carrier(S) ⋆ T is in I. The lemma follows. □

Lemma 4.5. For all k > 0, the protocol complex P_{(n,τ,δ)}(I) of any protocol in the NIIS model with time complexity k on inputs in I is equal to some non-uniform chromatic subdivision X̃^{k}(I).

Proof. We use induction on the time complexity k. By Lemma 4.4, the result holds for k = 1. Now suppose k > 1, and that the result holds for 1, …, k − 1.

Consider the protocol complex P_{(n,τ,δ)}(I) of any protocol in the NIIS model with time complexity k on inputs in I.

Any vertex v⃗ in I is labeled with ⟨i, v_{i}⟩, where i is a process id and v_{i} represents an input value to process i. According to the specification of NIIS protocols in Section ??, process i will, upon having received the input v_{i}, either execute an action inv writeread(v)_{i,IS_{1}} or finish(S)_{i}, depending on whether τ(v_{i}) evaluates to true or not. In this way, the predicate map τ induces a partition of the vertexes of I into two disjoint sets A and B. Since the time complexity of P_{(n,τ,δ)} on inputs in I is k, the set A must be nonempty. We now construct complexes A and B as in Definition 3.29, that is, a simplex T in I is in A iff all its vertexes are in A, and it is in B iff all its vertexes are in B.

The vertexes in A correspond to processes that, based on their input values, execute an inv writeread(v)_{i,IS_{1}}action with the object IS_{1}. By Lemma 4.3, the output protocol complex on inputs in A after the first IS access equals X (A). The final protocol complex P_{(n,τ,δ)}(A) is given by applying X (A) as an input complex to the Protocol. Since the complexity of the protocol on inputs in I, and hence on inputs in A, is k, the complexity of the protocol on inputs in X (A) must be k − 1. It follows by induction that the protocol complex P_{(n,τ,δ)}(A) equals some non-uniform chromatic subdivision X̃^{k−1}(X (A)) of X (A). A simplex U is in P_{(n,τ,δ)}(I) iff it corresponds to a valid set of outputs of an execution α of the protocol. In any execution α of the protocol, some of the participating, non-failing processes decide on their input values, while some decide on the snapshots they receive from some IS object. It follows that P_{(n,τ,δ)}(I) contains any simplex in B, and simplex in P_{(n,τ,δ)}(A) = X̃^{k−1}(X (A)), and any simplex of the form S ⋆ T, where S is in X̃^{k−1}(X (A)), T is in B, and carrier(S) ⋆ T is in I. It follows from Definition 3.29 that the protocol complex P_{(n,τ,δ)}(I) equals some non-uniform chromatic subdivision X̃^{k}(I) of I. □

We must also prove that, for any non-uniform chromatic subdivision X̃^{k}(I) of an input complex I, there is a matching protocol P_{(n,τ,δ)} in the NIIS model.

Lemma 4.6. For any non-uniform chromatic subdivision X̃^{k}(I) of an input complex I, there is a matching protocol P_{(n,τ,δ)} in the NIIS model such that the protocol complex P_{(n,τ,δ)}(I) = X̃^{k}(I).

Proof. Given a vertex v⃗ in I. The definition of the subdivision X̃^{k}(I) induces a sequence of non-uniform chromatic subdivisions I, X̃^{1}(I), …, X̃^{k}(I), and corresponding sequences A_{0}, …, A_{k−1} and B_{0}, …, B_{k−1} of complexes, the former sequence specifying the subcomplex to be subdivided further at each level of recursion.

In order to construct a protocol for n + 1 processes, we must specify the function τ : ⋃_{l=0}^{k} ϑ^{l}(D) → {true, false}. We specify τ to be true for all values v such that there is a vertex v⃗ in one of the complexes A_{0}, …, A_{k−1} with val(v⃗) = v, and τ to be false for all values v such that there is a vertex v⃗ in one of the complexes B_{0}, …, B_{k−1} with val(v⃗) = v. For all other values v, τ evaluates to false. This definition is well-formed, since for all p, where 0 ≤ p ≤ k, it follows from Definition 3.27 and Definition 3.29 that there are no two vertexes in X̃^{p}(I) with the same process-value label pair, and for all p, q, where 0 ≤ p, q ≤ k and p ≠ q, B_{p} and B_{q} have no vertexes with common labels (process id and value label).

□

We now give the proof of Theorem 4.2.

Proof. (Of Theorem 4.2) Given a decision task D = ⟨I, O, Γ⟩. It follows immediately from the previous lemma that any non-uniform protocol complex P^{k} with worst case complexity k_{S} on input S and decision map δ : P^{k} → O^{n} that agrees with Γ corresponds to a non-uniform chromatic subdivision X̃^{k}(I^{n}) with level k_{S} on S together with a simplicial map μ : X̃^{k}(I^{n}) → O^{n} that agrees with Γ, and vice versa. The theorem follows. □

rep sour

5. APPROXIMATE AGREEMENT

As an application of Theorem 4.2, we will analyze the well-known Approximate Agreement task [8], in which each process i is given an input x_{i} taken from some finite subset of the real numbers, and is required to decide on some output y_{i} such that, for some predetermined ϵ > 0, max_{i} y_{i} − min_{i} y_{i} < ϵ, and for all i, y_{i} ∈ [min_{i} x_{i}, max_{i} x_{i}]. Aspnes and Herlihy [1] proved a lower bound that implies a worst case time complexity of ⌊log_{3} \frac{max_{i} x_{i}−min_{i} x_{i}}{ϵ} ⌋ and an upper bound of ⌊log_{2} \frac{max_{i} x_{i}−min_{i} x_{i}}{ϵ} ⌋ in the NIIS model^{5}. In this section, we will show that this gap is not simply a technical fluke. We specify the finite n+1-process Approximate Agreement problem for ϵ > 0 as follows:

—I = {[x_{0}, …, x_{n}] | x_{i} ∈ V ∪ {⊥}}, where V is a finite subset of ℝ. —O = {[y_{0}, …, y_{n}] | y_{i} ∈ V ∪ {⊥}, |y_{i} − y_{j}| ≤ ϵ}.

—γ = {(I⃗, O⃗) | O⃗[i] ∈ [min_{i} I⃗[i], max_{i} I⃗[i]]}.

Theorem 5.1. Given ϵ > 0, there is a protocol P_{(n,τ,δ)} solving Approximate

Agreement with complexity ⌊log_{d} \frac{max_{i} I⃗[i]−min_{i} I⃗[i]}{ϵ}⌋ on any input vector I⃗, where

d = 3 if the size of the participating set of I⃗ is 2, and d = 2 if the size of the participating set of I⃗ is 3 or more. Moreover, this protocol is optimal on each input vector.

Theorem 4.2 provides both the upper bound protocol and the matching lower bound. We hope to convince the reader that this is an excellent example of how topological modelling exposes subtle points which would otherwise be difficult to grasp.

The key intuition behind our ability to close the gap between the upper and lower bounds for Approximate Agreement is depicted in Figure 21, which shows the subdivisions induced by a three process protocol on the input vector [0, 1, 2]. Aspnes and Herlihy [1] derive their lower bound for any n + 1 process algorithm from a “bad” execution in which only the two processes with inputs farthest apart participate. Such an execution in our model corresponds to a sequence of chromatic subdivisions of the edge between ⟨0, 0⟩ and ⟨2, 2⟩.

In the end, the vertexes of each 1-simplex in the non-uniform chromatic subdivision of the edge connecting ⟨0, 0⟩ and ⟨2, 2⟩ must be mapped by a simplicial map to vertexes with output values that are less than ϵ apart, and hence connected by a simplex in the output complex. Since each subdivision introduces two new vertexes and splits the edge in three, in log_{3} 2 such steps one can cut the distance among these vertexes to ϵ. However, note that if one considers executions in which 3 processes participate, we run into a problem: No matter how we subdivide the

5Although their proofs are for the read/write register model, they carry over to the NIIS model

Fig. 21. Simplex Subdivided by an Approximate Agreement Protocol

2-simplex, there is always a path of 1-simplexes between ⟨0, 0⟩ and ⟨2, 2⟩ that includes the vertex ⟨1, (⟨0, 0⟩, ⟨1, 1⟩, ⟨2, 2⟩)⟩ (marked by a darker color). Hence, for 3 process executions, only a single new vertex will be introduced to this path between ⟨0, 0⟩ and ⟨2, 2⟩, and so the maximum distance between any two vertexes is cut by at most a half for each level of subdivision. Hence our tight log_{2} lower bound. Our upper bounds follow directly from Theorem 4.2 by specifying the proper subdivision and map. The key thing to note about the proof of Theorem 5.1 is that it does not involve any mention of the actual executions; All we need to do is argue about the topology of the inputs and outputs and then apply Theorem 4.2.

Proof. We first recast the description of the Approximate Agreement in terms of input and output complexes as follows:

—I is the closure under containment of the collection of all simplexes of the form (⟨0, x_{0}⟩, …, ⟨n, x_{n}⟩), where for all i, x_{i} ∈ V ∪ {⊥}.

—O is the closure under containment of the collection of all simplexes of the form

(⟨0, y_{0}⟩, …, ⟨n, y_{n}⟩), where for all i, j, y_{i} ∈ V ∪ {⊥} and |y_{i} − y_{j}| ≤ ϵ. —Γ = {(S, T) | vals(T) ⊆ [min vals(S), max vals(S)]}.

Note that the size of the participating set for the input vector corresponding to a simplex S in I equals dim(S) + 1. Theorem 5.1 then states that, given ϵ > 0, there is a protocol P_{(n,τ,δ)} solving Approximate Agreement with complexity

⌊log_{d} \frac{max vals(S)−min vals(S)}{ϵ}⌋ on any input simplexS, where d = 3 if dim(S) = 1, and d = 2 if dim(S) ≥ 1. Moreover, this protocol is optimal on each input simplex S.

We first establish the lower bound. Let P_{(n,τ,δ)} be a protocol that solves Approximate Agreement with worst case complexity k_{S} on S, where S is any input simplex of dimension n ≥ dim(S) > 0. Let D(S) = max_{v⃗,u⃗∈S} val(v⃗) − val(u⃗). Then Theorem 4.2 states that there is some mapable non-uniform chromatic subdivision X̃^{k}(I), with level k_{S} on S. We will show that k_{S} ≥ ⌊log_{d} \frac{D(S)}{ϵ}⌋. The proof uses the following lemma.

Lemma 5.2. Let l ≤ k. Label the vertexes of X̃^{l}(S) with real numbers in a way that agrees with the intial value labeling of S, and let l_{S} be the level of X̃^{l}(S). Then

D(X̃^{l}(S)) ≥ \frac{D(S)}{d^{l_{S}}}

Proof. Suppose without loss of generality that l = l_{S}. We first give the proof for the case of two participating processes and d = 3. By definition of D(S), there is a 1-simplex U = (u⃗_{0}, u⃗_{1}) in S such that D(U) = D(S). The complex X̃^{l}(U) contains at most 3^{l} 1-simplexes, denoted U_{1}, …, U_{M}, where M ≤ 3^{l}. These form a continuous path from u⃗_{0} to u⃗_{1}, the endpoints of which are labeled with val(u⃗_{0}) and val(u⃗_{1}), respectively. So the best we can do is cut D(U) in 3^{l} pieces. The triangle inequality tells us that D(U) ≤ ∑_{i=1}^{M} D(U_{i}) ≤ M max_{i} D(U_{i}) ≤ 3^{k} max_{i} D(U_{i}). Hence max_{i} D(U_{i}) ≥ D(U)/3^{l} = D(S)/3^{l}. The lemma follows, since max_{i} D(U_{i}) ≤ D(X̃^{l}(S)).

We now prove the case where the size of the participating set is greater than 2 (and hence dim(S) is greater than 1) and d = 2. We argue by induction on l. The case l = 0 is trivial. Now suppose the claim is true for l − 1. By definition of D(X̃^{l−1}(S)), there is a 1-simplex U = (u⃗_{0}, u⃗_{1}) in X̃^{l−1}(S) such that D(U) = D(X̃^{l−1}(S)). U is a face of some 2-simplex U′ = (u⃗_{0}, u⃗_{1}, u⃗_{2}). Suppose first that the next level of non-uniform chromatic subdivision does not subdivide U completely. Then there is some 1-simplex T in the level l non-uniform subdivision of U′ with D(T) ≥ D(U)/2. Since D(U) = D(X̃^{l−1}(S)) and D(T) ≤ D(X̃^{l}(S)), the lemma follows by induction. Suppose instead that the next level of subdivision does subdivide U′ completely. Then the level l subdivision has an internal vertex m⃗_{2}, colored with id(u⃗_{2}), and two neighboring 1-simplexes T_{0} = (u⃗_{0}, m⃗_{2}) and T_{1} = (m⃗_{2}, u⃗_{1}). The triangle inequality then tells us that D(U) ≤ D(T_{0}) + D(T_{1}) ≤ 2 max_{i} D(T_{i}), where i ∈ {0, 1}. It follows that D(X̃^{l}(S)) ≥ D(X̃^{l−1}(S))/2. The lemma follows by induction. □

Suppose now that there exists a chromatic simplicial map μ : X̃^{k}(I) → O such that, for all simplexes T in X̃^{k}(I), μ(T) ∈ Γ(carrier(T)). We can associate this map with a labeling of the vertexes in X̃^{k}(I) as follows. Label each vertex v⃗ in X̃^{k}(I) with val(μ(v⃗)). This labeling agrees with the input value labeling of I, since for any vertex v⃗, the task specification requires that for any simplex S_{0} that contains v⃗, it must be the case that μ(v⃗) ∈ D(S_{0}). Choose two neighboring simplexes S_{0} and S_{1} containing v⃗ such that D(S_{0}) ∩ D(S_{1}) = val(v⃗). It follows that μ(v⃗) = val(v⃗). Now let T be any simplex in X̃^{k}(I). By definition of μ, μ(T) is a simplex in O, and hence D(μ(T)) < ϵ. It follows that D(T) = D(μ(T)) < ϵ, and hence that D(X̃^{k}(I)) < ϵ, where D(X̃^{k}(I)) is equal to max_{T ∈_{X^{k}}(I)}D(T). Clearly, for any

input simplex S, it follows that the labels on the restriction of X̃^{k}(I) to S, X̃^{k}(S), have range less than ϵ. The previous lemma then states that ϵ > D(X̃^{k}(S)) ≥ \frac{D(S)}{d^{k_{S}}}. We conclude that

k_{S} ≥ ⌊log_{d} \frac{D(S)}{ϵ}⌋

To prove the upper bound, we construct a mapable non-uniform chromatic subdivision X̃^{k}(I) of the input complex with level k_{S} = ⌊log_{d} \frac{D(S)}{ϵ}⌋ on each input simplex S, according to Definition 3.29. As argued above, the requirement that the subdivision be mapable is equivalent to saying that there is a vertex labeling of X̃^{k}(I) that agrees with the initial value labeling of I with the additional property that D(X̃^{k}(I)) < ϵ.

For each level of subdivision l ≤ k, a vertex v⃗ is in A if there is another vertex u⃗ such that val(v⃗) − val(u⃗) > ϵ, otherwise it is in B. Before applying the next level of subdivision to X (A) (as specified by Definition 3.29), we relabel all new vertexes in X (A) (those not in skel^{0}(A)) as follows: If the dimension of A is 1, label the new vertexes in X (A) with (2 min val(A) + max val(A))/3 and (min val(A) + 2 max val(A))/3, respectively. This cuts the distance between the vertexes with values apart in 3. Otherwise, label the new vertexes with (min val(A)+max val(A))/2. This cuts the distance between the values furthest apart in 2.

It is clear from this construction that, at each level of recursion, for all simplexes S in I we have that, if D(X̃^{l}(S)) > ϵ, then either D(X̃^{l+1}(S)) = D(X̃^{l}(S))/d), or D(X̃^{l+1}(S)) < ϵ. It follows that the level k_{S} of X̃^{k}(I) on S is ⌊log_{d} \frac{D(S)}{ϵ}⌋, where d = 3 if dim(S) = 1, and d = 2 if dim(S) > 1. We conclude from Theorem 4.2 that there is a wait-free protocol that solves Approximate Agreement with worst case time complexity ⌊log_{d} \frac{D(S)}{ϵ}⌋ on input S, where d = 3 for two participating processes and d = 2 for three or more. □

6. RENAMING

In this section we use the asynchronous complexity theorem to analyze the complexity of the renaming task of Attiya et al. [3], in which at most N = n + 1 processes are given unique input names taken from a large name space, and must choose unique output names taken from a smaller name space.

A protocol is comparison-based if the only operations a process can perform on process ids is to test for equality and order; that is, given two process ids P and Q, a process can test for P = Q, P ≤ Q, and P ≥ Q, but cannot examine the structure of the identifiers in any more detail (e.g., it cannot test whether P is prime). We will only consider comparison-based protocols in this section.

Let A and B be complexes where each vertex is labeled with a process id,and possibly with a value. B is a recoloring of A if there exists a bijective simplicial map (not color-preserving)

ρ : A → B

that is (1) order-preserving on process ids: if id(u⃗) < id(v⃗) then id(ρ(u⃗)) < id(ρ(v⃗)), and (2) value-preserving: if val(v⃗) is defined then val(v⃗) = val(ρ(v⃗)).

Theorem Comparison-Based Time Complexity. A decision task D = ⟨I, O, Γ⟩ has a wait-free protocol in the IIS model with worst case time complexity k_{S^{m}} on input S^{m} iff there is a mapable non-uniform chromatic subdivision X̃^{k}(I^{n}) with level k_{S^{m}} on S^{m} such that any recoloring ρ : X̃^{k}(S_{0}^{m}) → X̃^{k}(S_{1}^{m}) induces a recoloring ρ′ : μ(X̃^{k}(S_{0}^{m})) → μ(X̃^{k}(S_{1}^{m})) such that for every face T of S_{0}^{m}, ρ′(μ(X̃^{k}(T))) = μ(ρ(X̃^{k}(T))).

The additional condition captures the notion that the behavior of comparisonbased protocols does not change if processes are renamed in an order-preserving way. The proof of this theorem is almost identical to the proof of Theorem ??, except that it is necessary to check at each step that the equivalence-under-recoloring property continues to hold.

Theorem 6.2. There exists a wait-free protocol for N process Renaming in the comparison-based NIIS model with time complexity time(N) and number of names names(N) if:

\frac{N(N + 1)}{2} − ∑_{i=2}N − i^{time(N)} ≤ names(N) < \frac{N(N + 1)}{2} − ∑_{i=2}N − i^{time(N)−1}

where

2N − 1 ≤ names(N) ≤ N(N + 1)/2

and

1 ≤ time(N) ≤ N − 1.

Similar bounds follow immediately for the AS and MRSW models since Borowsky and Gafni [6] show that one can implement IIS in the AS model in Θ(n) time and in time Θ(n^{2}) in the MRSW model.

We now sketch the main idea behind the proof. Our complexity theorem says that the complexity of any protocol solving the renaming problem in IIS is exactly the number of chromatic subdivisions necessary to allow a “symmetric” simplicial map from the subdivided input complex to the output complex. And indeed, for N = 2 processes a single subdivision suffices to allow such a map as depicted on the right hand side of Figure 1. Labeling this subdivision symmetrically requires 3 names and the resulting algorithm requires exactly one time step. For N = 3 processes, a single subdivision of a 2-simplex looks like the left hand side of Figure 2. Notice that with 6 possible output names we can label this complex so that all 2simplices have different labels, which implies that one can solve renaming in this case in a single time step. The various “stacked” subdivided 2-simplexes in the figure correspond to input simplexes with different orders among the processors. For the sake of our discussion it is enough to think about the “top” one.

If we only have 5 Names, We need to subdivide the 2-simplex so that all subsimplices can be labeled with different names. The right hand side of Figure 2 shows how this can be done, and is an example of a non-uniform subdivision – some simplices are subdivided more than others. Though one could also in this case provide a uniform/canonical subdivision, it would be significantly more complicated and the implied algorithm would have all processes take two steps. Figure 2 implies that with 5 names the time complexity of solving 3 process renaming is two. As with the two process case, the subdivision completely describes the solution algorithm, as shown in Figure 22. The two process algorithm we refer to appears in Figure 1. ^{6}

      Access first IS object
       if in view one other process has value ⊥
          run 2 process alg with non-⊥ object
       elseif in view 2 other processes have value ⊥
          return 1
       else
          if my_id is highest return 5
          else access second IS object
             run 2 process alg with other non-⊥ process,
             returning 4 in place of 1 if it was ⊥

Fig. 22. Algorithm for three process Renaming

For N = 4, one step induces a standard chromatic subdivision X (S^{3}) of the input 3-simplex such that each 2-face of S^{3} can be labeled with 6 names as in the case of N = 3, and the 3-simplex in the center of X (S^{3}) (the one corresponding to executions in which all processes see all others’ values) is labeled using 4 additional names, a total of 10 names. We refer to all the 3-simplexes of X (S^{3}) apart from the central one as the outer 3-simplexes.e Now, if we wish to remove one name from the labeling, we need to subdivide, say, the 2-faces of the input simplex so that

6We choose to make the unique process be the one with highest id, but it could just as well be the one with smallest id or any other such quantification based only on comparison of ids.

they use 5 names as in the case of N = 3, and then induce this subdivision nonuniformly onto the whole subdivided simplex X (S^{3}) (in other words, subdividing each 2-simplex on the face of S^{3} induces a non-uniform subdivision of the outer 3-simplex that contains it in the subdivision X (S^{3})). However, this additional time step allows us to introduce an additional subdivision in the center 3-simplex of X (S^{3}) by taking one of its 1-faces S^{1} and subdividing it as in the case of N = 2. Note that this does not require accessing a new (third) IS object, since in terms of the executions implied by the subdivision, after the first time step of the algorithm (in which the 1st IS object is accessed) the execution proceeds in one of the outer 3-simplexes or in the center one but not in both. As we will prove in the full paper, As we will show in the full proof, one can label the induced subdivided 3-simplexes of X̃^{2}(S^{3}) resulting from the subdivision of S^{1} by using the same names that appear on the internal vertexes of the subdivided 2-faces of S^{3}. Thus, if time(4) = 2 one can eliminate 2 names at the price of 1 time step, requiring a total of 8 names. Now, if time(4) = 2, we cannot remove any additional names from the 2-simplexes on the face of the subdivision. This is because 5 names is the lower bound (see [?]). We can however eliminate one additional name from the center 3-simplex, by, instead of subdividing a 1-simplex on its face, subdividing a 2-simplex and labeling all its original vertexes with the same name. This subdivision requires 5 names and is exactly as in the N = 3 case (and hence two time steps) using the same names of the 2-simplexes S^{2} on the boundary of S^{3}, with only the names of the original vertexes of s^{2} replaced by one of the names of the center simplex. The original vertexes of the center 3-simplex are thus labeled using only two names (the ones on its subdivided 2-face are all labeled the same), and the faces of S^{3} and the internal simplexes of the subdivision are labeled using 5 names, a total of 7 names. We derive the upper bound by extending this same reasoning inductively to higher values of N, where starting with the N(N + 1) subdivision, the 1st time step we add cuts N − 2 names, the second N − 3 and so on. We now proceed to the proof.

Proof. (Of Theorem 6.2)

Our complexity theorem says that the complexity of any protocol solving the renaming problem in the NIIS model is determined by the level of non-uniform chromatic subdivision necessary to allow a symmetry-preserving simplicial map from the subdivided input complex to the output complex. As argued above for the case of approximate agreement, such a simplicial map corresponds to a symmetric labeling of the vertices of the subdivided input complex that agrees with the task specification, that is, no two vertices on a simplex have the same label.

Given an input simplex S to the N-process renaming problem, where N > 1. Suppose without loss of generality that the process ids of the vertices in S are in the range 0, …, N − 1 and in increasing order, that is, id(v⃗_{i}) < id(v⃗_{j}) if and only if i < j. Suppose also that there are n = names(N) available names, taken from the set {1, …, n}, and that the available time is t = time(N). The proof proceeds by inductively building symmetrically labeled non-uniform subdivisions having maximal level t and labels taken from the n names given above, where n and t are in accordance with the formula given above. The current version of the proof as presented here is still in draft form and provides the construction of each such subdivisionis but is missing the proof that the subdivisions we use are in fact valid non-uniform chromatic subdivisions. This proof is rather straightforward, and for now is left to the reader.

For ease of argument, we express the formula more compactly as follows: Let

f(N, t) = \frac{N(N+1)}{2} − t ; ∑_{i=2}N − i, for all N > 1, 1 ≤ t ≤ N − 1. Then Theorem 6.2

says that there is a renaming protocol for N processes using n names and t time if f(N, t) ≤ n < f(N, t).

We will provide a general construction for the case where the number of names used is n = f(N, t). The in-between case, in which f(N, t) < n < f(N, t − 1), follows, since we can just run the algorithm for f(N, t) names whose output complex of this algorithm is a subcomplex of the output complex for n, thus providing a solution in this case too.

We first consider the case where N = 2. We show how to non-uniformly subdivide and symmetrically label (with output values) a typical input simplex, S = (v⃗_{0}, v⃗_{1}). As discussed above, the labeling will correspond to a simplicial map satisfying the task specification. Suppose without loss of generality that id(v⃗_{0}) < id(v⃗_{1}). The resulting subdivision and simplicial map correspond to one of the two 1-simplexes in Figure ??. The subdivision is simply a standard chromatic subdivision of the entire simplex, and the simplicial map μ is defined by the labelings on the vertices. The level of subdivision is 1, and the number of names used is 3, which is in accordance with the formula, since (2 · 3)/2 − (2 − 2) = 3. The symmetry requirement is clearly satisfied, since the choice of which vertex gets the bigger name depends only on the relative ordering of the original names. We denote this labeled subdivision for C_{1}(1, 2, 3)(S), and we will use it as an initial building block in the ensuing induction. The notation C_{1}(1, 2, 3) should be interpreted as follows; The subscript 1 indicates the dimension of the input simplex, which is one less than the number of processes that participate. The entries in the parentheses act as place holders for labels. In this simple case, the labels used are 1, 2 and 3. The relative ordering of the place holders matters, as it corresponds to the relative ordering of process ids.

Assume by induction that the result holds for 2, …, N − 1 processes. We will establish it for the case of N processes. Let S = (v⃗_{0}, …, v⃗_{N−1}) be an N − 1dimensional input simplex to the N process renaming problem.

We first show how to subdivide and label S in the extreme case where n = 2N −1 and t = N − 1. The right hand side of Figure 2 shows how this is done in the case of N = 3, n = 5 and t = 2, where each big triangle corresponds to a subdivided simplex S. We see that the entire simplex is subdivided once according to the standard chromatic subdivision, with the 1-simplices corresponding to the boundary of the original simplex labeled according to C_{1}(1, 2, 3). The internal 2-simplex is labeled using 4, 5, and one edge (the one labeled with only 4’s) is subdivided and labeled further using C_{1}(4, 2, 3). In general, we first subdivide the entire simplex once according to the standard chromatic subdivision. We say a vertex in this subdivision is external if its carrier is a proper face of S, and internal otherwise. By our induction hypothesis, we already know how to solve N−1 process renaming with 2N − 3 available names in time N − 2.. This solution corresponds to the labeled non-uniform subdivision C_{N−2}(1, 2, 3, …, 2N − 3) of level N − 2. We continue subdividing the subcomplex spanned by the external vertices so that eventually the subcomplex corresponding to each (N − 2)-face of S is subdivided and labeled according to C_{N−2}(1, 2, 3, …, 2N −3). These subdivisions are all induced onto the entire subdivided simplex in the obvious way, that is, by replacing the face with the appropriately subdivided face and starring this with all vertices in the complex that were connected to the face before the replacement. This is in accordance with the definition of the non-uniform chromatic subdivision.

We now label the N internal vertices of the complex as follows: the vertex whose process id is the largest, v⃗_{N−1}, gets the label 2N − 1. All the other vertices get the label 2N − 2. All that remains is to subdivide and label the face of the internal simplex spanned by the vertices with label 2N − 2. Call this simplex T. Using our induction hypothesis again, we subdivide and label T according to C_{N−2}(2N − 2, 2N −4, 2N −3, .., 2, 3), and induce this subdivision onto the rest of the subdivided simplex by replacing T with the labeled subdivision of T and starring this with all vertices in the complex that were connected to the T before the replacement. This concludes the construction of the labeled subdivided complex C_{N−1}(1, 2, 3 …, 2N− 1), which corresponds to a protocol that uses time N − 1 and 2N − 1 names, as required.

We now consider the general case, in which n = f(N, t) and 1 ≤ t < N − 1. , which can be applied to any (N −2)-dimensional input simplex to the N −1 process renaming problem.

We now describe how to subdivide and label S. The left hand side of Figure 2 shows how this is done in the case of N = 3, n = 6 and t = 1, where each big triangle corresponds to a subdivided simplex S. We see that the entire simplex is subdivided once according to the standard chromatic subdivision, with the 1simplices corresponding to the boundary of the original simplex labeled according to C_{1}(1, 2, 3). The internal 2-simplex is labeled using 4, 5, 6. In general, we first subdivide the entire simplex once according to the standard chromatic subdivision. By our induction hypothesis, we already know how to solve N − 1 process renaming with f(N − 1, t) available names in time t. This solution corresponds to the symmetrically labeled non-uniform subdivision C_{N−2}(1, 2, 3, …, f(N − 1, t)). We continue subdividing the subcomplex spanned by the external vertices so that eventually the subcomplex corresponding to each (N − 2)-face of S is subdivided and labeled according to C_{N−2}(1, …, f(N − 1, t)).

We now label the N internal vertices of the complex as follows. There are f(N, t)−f(N−1, t) = N+1−t > 2 unused names. We label the N−(N+1−t)+1 = t vertices with the lowest process ids f(N − 1, t) + 1, and we label the remaining vertices in increasing order using the names f(N − 1, t) + 2, …, f(N, t) such that the process with the largest id, v⃗_{N−1}, gets the label f(N, t). Denote the simplex spanned by the t vertices labeled with f(N − 1, t) + 1 as T. We subdivide and label T according to C_{t−1}(f(N − 1, t) + 1, f(N − 1, t) − 1, f(N − 1, t), .., f(N − 1, t) − (2t − 1), f(N − 1, t) − (2t − 2)), and induce this subdivision onto the rest of the subdivided complex by replacing T with the labeled subdivision of T and starring this with all vertices in the complex that were connected to the T before the replacement. This concludes the construction of the labeled subdivided complex C_{N−1}(1, 2, 3, …, f(N, t)), which corresponds to a protocol that uses time t and f(N, t) names, as required.

Note that, at each step, the labeling of internal vertices is based solely on comparing process ids. This guarantees that the labelings used in the proof are symmetric, as required. □

REFERENCES

[1] J. Aspnes and M.P. Herlihy. Fast randomized consensus using shared memory. Journal of Algorithms, 11, 1990.

[2] H. Attiya and S. Rajsbaum. A combinatorial topology framework for wait-free computability. Preprint, 1995.

[3] Hagit Attiya, Amotz Bar-Noy, Danny Dolev, David Peleg, and Rudiger Reischuk. Renaming in an asynchronous environment. Journal of the ACM, July 1990.

[4] O. Biran, S. Moran, and S. Zaks. A combinatorial characterization of the distributed tasks which are solvable in the presence of one faulty processor. In Proceedings of the 7th Annual ACM Symposium on Principles of Distributed Computing, pages 263–275, August 1988.

[5] E. Borowsky and E. Gafni. Generalized flp impossibility result for t-resilient asynchronous computations. In Proceedings of the 1993 ACM Symposium on Theory of Computing, May 1993.

[6] E. Borowsky and E. Gafni. Immediate atomic snapshots and fast renaming. In Proceedings of the 12th Annual ACM Symposium on Principles of Distributed Computing, August 1993.

[7] E. Borowsky and E. Gafni. A simple algorithmically reasoned chracterization of wait-free computationsi. In Proceedings of the 16th Annual ACM Symposium on Principles of Distributed Computing, August 1997.

[8] D. Dolev, N.A. Lynch, S.S. Pinter, E.W. Stark, and W.E. Weihl. Reaching approximate agreement in the presence of faults. Journal of the ACM, 33(3):499–516, July 1986.

[9] M. Fischer, N.A. Lynch, and M.S. Paterson. Impossibility of distributed commit with one faulty process. Journal of the ACM, 32(2), April 1985.

[10] E. Gafni and E. Koutsoupias. 3-processor tasks are undecidable. PODC 95, Brief announcement.

[11] M. Herlihy and S. Rajsbaum. Algebraic spans. In Proceedings of the 14th Annual ACM Symposium on Principles of Distributed Computing, pages 90–99. ACM, August 1995.

[12] M.P. Herlihy and S. Rajsbaum. On the decidability of distributed decision problems. In preparation.

[13] M.P. Herlihy and N. Shavit. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the 1993 ACM Symposium on Theory of Computing, May 1993.

[14] M.P. Herlihy and N. Shavit. A simple constructive computability theorem for wait-free computation. In Proceedings of the 1994 ACM Symposium on Theory of Computing, May 1994.

[15] N.A. Lynch and M.R. Tuttle. An introduction to input/output automata. Technical Report MIT/LCS/TM-373, MIT Laboratory For Computer Science, November 1988.

[16] J.R. Munkres. Elements Of Algebraic Topology. Addison Wesley, Reading MA, 1984. ISBN 0-201-04586-9.

[17] M. Saks and F. Zaharoglou. Wait-free k-set agreement is impossible: The topology of public knowledge. In Proceedings of the 1993 ACM Symposium on Theory of Computing, May