Open AccessArticle

A Topological Characterization to Arbitrary Resilient Asynchronous Complexity

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

School of Computer Science and Technology, University of Chinese Academy of Sciences, Beijing 100049, China

Yanqi Lake Beijing Institute of Mathematical Sciences and Applications, Beijing 101408, China

Authors to whom correspondence should be addressed.

Mathematics 2022, 10(15), 2720; https://doi.org/10.3390/math10152720

Submission received: 4 July 2022 / Revised: 23 July 2022 / Accepted: 26 July 2022 / Published: 1 August 2022

(This article belongs to the Section Mathematics and Computer Science)

Download

Browse Figures

Versions Notes

Abstract

In this work, we extend the topology-based framework and method for the quantification and classification of general resilient asynchronous complexity. We present the arbitrary resilient asynchronous complexity theorem, applied to decision tasks in an iterated delayed model which is based on a series of communicating objects, each of which mainly consists of the delayed algorithm. In order to do this, we first introduce two topological structures, delayed complex and reduced delayed complex, and build the topological computability model, and then investigate some properties of those structures and the computing power of that model. Our theorem states that the time complexity of any arbitrary resilient asynchronous algorithm is proportional to the level of a reduced delayed complex necessary to allow a simplicial map from a task’s input complex to its output complex. As an application, we use it to derive the bounds on time complexity to approximate agreement with

n + 1

processes.

Keywords:

distributed computation; asynchronous computation; combinatorial topology; computability; complexity; resilience; task-solvability

MSC:

68Q05; 68Q22; 68W15; 68M14

1. Introduction

Since the in-depth applications of computers to all aspects of modern life, computers are progressively and mainly being used as coordination devices in asynchronous distributed systems. However, the proof of the FLP theorem [1], which says that the consensus task cannot be solved in an asynchronous message passing system even though only one process may fail by halting, implies that distributed computing is different from the standard Turing computing.

A distributed computing system consists of finitely many sequential processes communicating via shared-memory, message-passing and other mechanisms [2]. The communicating mechanisms include communication channels, synchronizing primitives and general services [3]. The processes are asynchronous, which may make the message and communication delay leading to a great effect in Information Exchange, such as a hyper hexa-cell interconnection network [4]. In addition, they may also fail by stopping, so it is indistinguishable whether an irresponsive process has failed or is only running slowly in a distributed system.

Fortunately, as a revolutionary development, a new framework of modeling and analysis based on classical algebraic topology was introduced by Herlihy and Shavit [5] for understanding and reasoning of computability problems in an asynchronous distributed system in 1993. In that work, they presented a topological characterization of the asynchronous computability of general tasks with

t \geq 1

crash failures in a share-memory model which is equivalent to a message-passing model showed by Attiya et al. [6]. Furthermore, they then extended to a complete characterization of wait-free solvability of distributed tasks in shared-memory systems, namely, a task is solvable if and only if its specification is topologically compatible in some sense [7,8]. Later, that technique was further generalized in three directions. The first direction is generalization to systems with arbitrary communication objects [9,10,11,12,13], to arbitrary resilience (rather than one or n failures) [9,14], to arbitrary synchrony [9,15], or to Byzantine failures [16,17]. The second direction is to explore the way for the classification of distributed tasks in asynchronous shared-memory systems: two tasks are reducible to each other if and only if they are equivalent in a topological manner [18,19,20,21]. The last is to explore of the complexity of decision tasks in some communicating model, that is to say, one can give the upper bounds and/or lower bounds [22,23,24], or just give a theoretical estimation of the cost of time or space and so on [25,26,27,28,29,30,31,32]. We feel the time is ripe to extend these techniques to arbitrary resilient asynchronous complexity.

This paper studies asynchronous shared memory solutions to the decision tasks in a distributed asynchronous system with

n + 1

processes. We focus on the iterated delayed model which is based on a delayed snapshot algorithm introduced by Saraph et al. in [33]. The model can guarantee that the scan operations of each process return a view that contain more than

n - t

elements of sets of the participating processes’ inputs, where t means the number of crashing processes it tolerates by t (

1 \leq t \leq n

) or fewer for that system.

Our contribution lies in three aspects. Firstly, we introduce a topological structure, N-fold delayed complex, which is a sub-complex of the

2 N

-fold standard chromatic subdivision, where N is an arbitrary non-negative integer. Using it can give a precise description of the protocol complex of full-information protocol leading to the acquisition of computing power, which is a modification of the result showed by Saraph et al. [33]. Secondly, we introduce a novel computational model, the iterated delayed model, which has a particularly nice geometric representation and hence easily lends itself to topological analysis. Furthermore, by a new topological structure, the reduced complex is constructed from a delayed complex, and we will give a theoretical measure of computational complexity of an arbitrary resilient asynchronous model, which may lead some applications in practical applications. That is, the time (or round) complexity in that model is equal to the level of the chromatic subdivisions necessary to allow a simplicial map from a task’s input simplex corresponding to the worst case to its output complex. As an application, we derive the tight bound on the time to achieve an

n + 1

process approximate agreement in an iterated delayed model:

⌊ l o g_{m} \frac{m a x {i n p u t v a l u e} - m i n {i n p u t v a l u e}}{ϵ} ⌋

on any input n-simplex I, where

m = 9

n = 1

and

m = 4

n \geq 2

2. Preliminaries

In this subsection, we give an overview of the basic definitions and concepts of combinatorial topology that we will use to formulate our model. The complete definitions on algebraic topology can be taken from the classical textbooks [34,35].

2.1. Basic Concepts of Combinatorial Topology

An (abstract) simplicial complex

K

, or complex for short, is a finite set V together with a collection of subsets of V closed under containment, which means that, if

α \in K

, any subset of

α

is also in

K

. An element v of V is called a vertex and an element

α

K

is called a simplex, and

β (\in K)

is called a face of

α

β \subseteq α

. Subset

K

K

is called a sub-complex if itself is closed under containment. The dimension of simplex

α

is defined as

| | α | | - 1

(here

| | α | |

means the number of the vertices of

α

), denoted

d i m (α)

, and the dimension of

K

is defined as the highest dimension among its simplexes. Call simplex

α \in K

a facet of

K

d i m (α) = d i m (K)

. Usually, use n-simplex (complex) as shorthand for an n-dimensional simplex (complex). By default, any complex in this paper is pure in the sense that any simplex is a face of a facet in that complex. In addition, call

G (X)

the complex generated by X if it is a collection of X and all its faces, where X is a simplex in

K

To ease understanding, one can equivalently view simplicial complex

K

through a geometric lens. Bijectively map the set

V (α) = {v_{i}}_{i = 0}^{k}

of vertices of a k-simplex

α

K

to an arbitrary set

V^{'} (α) = {v_{i}^{'}}_{i = 0}^{k}

of affinely independent points in a Euclidean space with an appropriate dimension. Then, there is natural convex hull

{\bar{V}}^{'} (α) = {x \in \sum_{i = 0}^{k} λ_{i} v_{i}^{'} | \sum_{i = 0}^{k} λ_{i} = 1, λ_{i} \geq 0, λ_{i} \in R}

spanned by

V^{'} (α)

. Call

{\bar{V}}^{'} (α)

a geometric simplex or the geometric realization of

α

, and call

α

the vertex scheme of

{\bar{V}}^{'} (α)

. Put all geometric simplexes together such that the collection is closed under containment and every pair of distinct simplexes has disjoint interiors if they have intersections, by which we can obtain a geometric simplicial complex corresponding to

K

. For the details, one can follow Munkres [35]. Nevertheless, hereunder we still adopt the abstract simplex complex definition.

Let

α

and

β

be two simplexes of complex

K

with no intersection; then, the join of them is

α * β

with the vertex scheme being

α \cup β

. The star of

α

is the collection of simplexes

{β \in K | α \subseteq β}

K

, denoted

S t (α, K)

. See Figure 1; consider a complex

K

consisting of all vertices

{v_{i}}_{i = 0}^{3}

, and all segments

{v_{i}, v_{j}}_{0 \leq i \neq j \leq 3}

and all triangles

{v_{i}, v_{j}, v_{r}}_{0 \leq i \neq j \neq r \leq 3}

; the star of 0-simplex

v_{0}

S t (v_{0}, K)

consists of all simplexes of

K

except the red dotted segments and its faces.

Given two complexes

K

and

L

, a vertex map

f : V (K) ⟶ V (L)

is a simplicial map if f carries each simplex of

K

to a simplex of

L

, and f is called non-collapsed if, for every simplex

α \in K

, there is

d i m (f (α)) = d i m (α)

, and f is called equivalent if there is a simplicial map

g : L ⟶ K

such that

g \circ f : K ⟶ K

and

f \circ g : L ⟶ L

are all identity maps. A map

Φ : K ⟶ L

is called a carrier map if

Φ (α) \subseteq L

and

Φ (α \cap β) \subseteq Φ (α) \cap Φ (β)

for any

α, β \in K

. In addition, f is said to be carried by

Φ

f (α) \in Φ (α)

for any

α

K

is said to be a chromatic complex with colors C if there is a non-collapsed simplicial map

χ

from

K

C

; call

χ

the coloring of

K

. A map

ϕ : K ⟶ L

is said to be a color-preserving map if, for each vertex v of

K

, there is

χ_{K} (v) = χ_{L} (ϕ (v))

, where

χ_{K}

and

χ_{L}

are the colorings of complexes

K

and

L

. In addition, a map is called a color-preserving simplicial map if it is both a color-preserving map and a simplicial map.

Suppose

χ

is a coloring of n-simplex X with colors

C = {p_{i}}_{i = 0}^{n}

; call

C h (X)

once standard chromatic subdivision of simplex X if any m-simplex of

C h (X)

(m \leq n)

can be given by the form of

{(p_{i_{t}}, S_{r_{t}})}_{t = 0}^{m}

satisfying the following conditions:

there are $2^{n} (n + 1)$ vertices in total in $C h (X)$ ;
for all $t, s \in [m]$ , $p_{i_{t}} \neq p_{i_{s}}$ if $s \neq t$ , and either $S_{r_{t}} \subseteq S_{r_{s}}$ or $S_{r_{s}} \subseteq S_{r_{t}}$ ;
for all $t, s \in [m]$ , if $p_{i_{t}} \in χ (S_{r_{s}})$ , then $S_{r_{t}} \subseteq S_{r_{s}}$ ;

where

S_{r_{x}}

is a face of X, and

[m]

is equal to

{0, 1, 2, \dots, m}

As showed in Figure 2, on the left side of this figure is a chromatic 2-simplex

α = {v_{0}, v_{1}, v_{2}}

with colors

{0, 1, 2}

, and in the middle of it is a once standard chromatic subdivision

C h (α)

α

, and on the right is a general chromatic subdivision

D i v (α)

α

, since it is easy to check that it does not satisfy the second condition.

2.2. Distributed Computing Model

For the sake of the discussion, we first construct a series datatype for an arbitrary given datatype D. The datatype

V^{k} (D)

(k is a non-negative integer) can be defined inductively as follows:

$V^{0} (D) ≜ {(p_{i}, x_{i}) : x_{i} \in D \cup {⊥}, i \in [n]}$ ;
$V^{k} (D) ≜ {(p_{i}, s_{i}) : s_{i} \subset V^{k - 1} (D) \cup {⊥}, i \in [n]}$ , where $p_{i}$ can be regarded as the location for some data, ⊥ means nothing but a placeholder, and $(p_{i}, s_{i})$ is a pair.

Following the model by Moses and Rajsbaum [15], there are

n + 1

processes, up to t of which may fail by crashing. The processes execute a round-by-round protocol in an asynchronous manner. A decision task is a specification of eligible outputs with regard to the inputs, which intuitively models coordination problems. A protocol is a distributed program consisting of the processes. We say that a protocol solves a decision task if the outputs of any execution sequence (which consists of a series of round executions) conform with the specification of the task.

Our distributed computing model is based on the delayed object, denoted

D O_{n, t}

, a delayed algorithm proposed by Saraph et al. [33], and has been showed to be a useful building block for analysis of a t-resilient distributed asynchronous system; see Algorithm A1. Although Delporte et al. [36] showed that a t-resilient immediate snapshot is impossible, two snapshots each in delayed objects are wait-free immediate snapshots which can be implemented in a t-resilient asynchronous distributed system [37].

Intuitively,

D O_{n, t}

consists of three phases, the first and the third phases each are wait-free immediate snapshot (IS) operations, and the middle phase is a waiting operation. Before each process executes the second IS, it may need to wait until the view of some process contains at least

n - t + 1

pairs after the first IS. Formally, we can specify

D O_{n, t}

as an

I / O

automata for

(n + 1)

-processes with at most t processes crashing and datatype D, denoted by

D O_{n, t} {[0]}_{V^{0} (D)}

. Here, we only take

1 \leq t < n

, since

t = n

means the model is wait-free, and the complexity of that situation had been investigated by Hoest and shavit [30].

Our memory model is an iterated delayed model abbreviated as

IDM

, in which each process communicates with the other processes only by delayed object

D O_{n, t}

, and every process accesses that object at most once in every round. It assumes an unbounded sequence of delayed objects

D O_{n, t} {[0]}_{V^{0 \times 2} (D)}

D O_{n, t} {[1]}_{V^{1 \times 2} (D)}

D O_{n, t} {[2]}_{V^{2 \times 2} (D)}

⋯ with initial datatype D, abbreviated as

D O_{n, t} [0]

D O_{n, t} [1]

D O_{n, t} [2]

, ⋯, if the datatype is explicit in the context. This model has each participating process proceed in ascending order in the sequence.

Suppose

P_{(n, t, τ, δ)}

, as in Algorithm 1, is a protocol in

IDM

, and each process starts with a value coming from the datatype

V^{m} (D)

in that model, where m is a non-negative integer and D is some given datatype. Before communicating with other processes in round

r_{i}

by object

D O_{n, t} [r_{i}]

, process

p_{i}

needs to check whether or not its local state

l s_{i}

can be decidable by a evaluated function

τ : ⋃_{i = 0}^{\infty} V^{m + 2 i} (D) \to {f a l s e, t r u e}

, and a decision map

δ : ⋃_{i = 0}^{\infty} V^{m + 2 i} (D) \to V^{0} (D_{O})

, where

D_{O}

is called the output datatype. If

τ (l s_{i})

t r u e

, the process can decide and execute a decision operation; otherwise, do nothing. In addition,

S i g

is taken as the signal that records whether or not a process has output before the current round, and it admits only two possible values 0 and 1, where

S i g = 0

means the process does not have an output before the current round; otherwise, it means it already has an output. If

τ_{i} (l s_{i}) = t r u e

and

S i g_{i} = 0

, the process

p_{i}

can make a decision but has no output; then, it decides and outputs

δ_{i} (l s_{i})

; Otherwise, it needs to access the object

D O_{n, t} [r_{i}]

to accumulate information and then it accesses the next round with object

D O_{n, t} [r_{i} + 1]

Algorithm 1: An execution of a protocol

P_{(n, t, τ, δ)}

for process

p_{i}

IDM

(1)

l s_{i} \leftarrow

input value;
(2)

S i g_{i} \leftarrow 0

;
(3)

r_{i} \leftarrow 0

;
(4) forever do
(5)

r_{i} \leftarrow r_{i} + 1

;
(6) if

τ_{i} (l s_{i}) = t r u e

and

S i g_{i} = 0

(7) then output

δ_{i} (l s_{i})

and

S i g_{i} \leftarrow 1

;
(8)

l s_{i} \leftarrow D O_{n, t} [r_{i}] . c o m m u n i c a t e (i, l s_{i})

;
(9) od;

2.3. Topological Task Specification

In this subsection, we set some notions to make our statement straightforward. Let

D_{I}

be the set of input values and

D_{O}

the set of output values; then, any local state of the process

p_{i}

can be regarded as a pair

s_{i} = (p_{i}, v_{i})

such that

p_{i} = I d s (s_{i})

v_{i} = v a l (s_{i})

and

s_{i} \in V^{m} (D_{I})

, where m is a non-negative integer.

The input configurations for

n + 1

processes with input

D_{I}

are a chromatic n-complex, in which each k-simplex,

0 \leq k \leq n

, has form

{s_{i}}_{i = 0}^{k}

s_{i} \in V^{0} (D_{I})

—likewise for output configurations except

s_{i} \in V^{0} (D_{O})

. Formally, a topological specification of a decision task with

n + 1

processes is a triple

T = (I, O, Δ)

, where

I = V^{0} (D_{I})

and

O = V^{0} (D_{O})

are input n-complex and output n-complex, respectively, and

Δ : I ⟶ 2^{O}

is a name (color)-preserving carrier map [17,38].

3. The Topological Description of $IDM$

This section introduces a topological structure, k-fold delayed complex, which can be showed a sub-complex of

2 k

times standard chromatic subdivision, and investigate their properties. By this, we give a characterization of computing power of

IDM

, which is a modification of the results showed by Saraph et al. in [33].

3.1. Delayed Complexes

Suppose

I^{n}

is a chromatic n-simplex with the coloring map

χ

and the colors

C = {p_{i}}_{i = 0}^{n}

, and

I^{n} = G (I^{n})

is the chromatic n-complex generated by

I^{n}

| I^{n} |

and

| | I^{n} | |

mean the geometric realization and the number of vertices of

I^{n}

, respectively.

Definition 1.

P

-partition of a given finite set S is a partition

π_{0}, π_{1}, \dots, π_{m}

such that

S = \cup_{i = 0}^{m} π_{i}

π_{i} \cap π_{j} = \emptyset

for any

i \neq j \in [m]

, and

π_{i} ≻ π_{j}

0 \leq i < j \leq m

, where

" ≻ "

means some "priority" to the property

P

Lemma 1.

There is a one-to-one correspondence between the set of the facets of

C h (I^{n})

and the collection of all

P

-partitions of the set

C = χ (I^{n})

Proof of Lemma 1.

Suppose

Π = π_{0}, π_{1}, \dots, π_{m}

is a

P

-partition of C. Let

P

be the containment in the complex

I^{n}

, that is, if

α \subset β

for any simplexes

α, β \in I^{n}

χ (α) ≻ χ (β)

. Consider set

V = {(p_{i}, S_{i}) | p_{i} \in χ (S_{i}) \subseteq C, S_{i} \in I^{n}}

; there must be a subset

V_{Π}

of V with

| | V_{Π} | | = n + 1

, such that, for any two elements

(p_{i}, S_{i}), (p_{j}, S_{j}) \in V_{Π}

, there are

S_{i} = S_{j}

p_{i}, p_{j} \in π_{s}

for

s \in [m]

, and

S_{i} \subset S_{j}

p_{i} \in π_{s}, p_{j} \in π_{k}

for

0 \leq s < k \leq m

. In fact, it only needs to take the subset

{S_{i}}

I^{n}

, in which each simplex satisfies

χ (S_{i}) = \cup_{t = 0}^{i} π_{t}

. By Kozlov [39],

V_{π}

can span a facet of

C h (I^{n})

On the contrary, let

α = {(p_{i}, S_{i})}_{i = 0}^{n}

be a facet of

C h (I^{n})

, by the definition of standard chromatic subdivision of

I^{n}

. There is naturally a partition of the colorings set C under the containment in the set

{S_{i} \subseteq I^{n} | (p_{i}, S_{i}) \in α}

. □

By this lemma, any facet of a standard chromatic subdivision of a chromatic n-simplex can be represented by a

P

-partition of its colors, which provides a simple way to describe a sub-complex structure of the standard chromatic subdivision. Suppose X is any facet of standard chromatic subdivision

C h (I^{n})

corresponding to a

P

-partition

π_{0}, π_{1}, \dots, π_{s}

Definition 2.

A n-simplex is said to be a

C

-extended of the facet X in

C h (I)

, denoted by

F l i p_{i} (X)

, if it can be given as follows:

F l i p_{i} (X) = \{\begin{matrix} {p_{i}} \cup π_{1}, π_{2}, \dots, π_{s} & i f π_{0} = {p_{i}}, \\ {p_{i}}, π_{0} - {p_{i}}, π_{1}, π_{2} \dots, π_{s} & i f | | π_{0} | | > 1 a n d p_{i} \in π_{0} . \end{matrix}

(1)

Call the collection

{F l i p_{i} (X) | p_{i} \in π_{0}}

the

C

-extended of X, denoted by

F l i p (X)

. Furthermore, call

F l i p (X) \cup X

the

C

-neighborhood of X, denoted by

\hat{X}

It is not hard to see that the

C

-extended is symmetrical, that is, if X is a

C

-extended of Y, Y is also a

C

-extended of X. In addition, a

C

-extended of a facet is usually not unique unless the cardinal number of the first component in its

P

-partition is equal to one.

The

C

-neighborhood describes a combinatorial adjacent relation of two facets in

C h (I^{n})

, which is not a neighborhood in the usual sense in topology or geometry. In general, a neighborhood of a facet in the triangulation of an n-manifold is equal to the union of facets in itself and its collar, which is indeed not its

C

-neighborhood. Seeing Figure 3, let X be the black fields, the collection of all the facets of the star of

C h^{2} (s k e l^{0} (I^{2}))

C h^{2} (I^{2})

, the green areas are the

C

-extended of X, and the

C

-neighborhood is the collection of all the 2-simplexes colored black and green.

Lemma 2.

Suppose α is a facet of

C h (I^{2})

; then, a

C

-extended

F l i p_{i} (α)

is also a facet in

C h (I^{2})

Proof of Lemma 2.

This is a direct result of the Definition 2 and the Lemma 1. □

For general discussion, let

K

be any pure chromatic n-complex with the coloring map

χ

and colors

C = {p_{i}}_{i \in [n]}

, and let

S_{K}

be the collection of the facets of

S t (C h^{2} (s k e l^{n - t - 1} (K))

C h^{2} (K))

, where t is an integer and

0 \leq t < n

. The

C

-neighborhood

{\hat{S}}_{K}

S_{K}

is equal to

(⋃_{α \in S_{K}} F l i p (α)) ⋃ S_{K}

. Set

C_{S_{K}} = {α \in C h^{2} (K) | α \notin {\hat{S}}_{K}, d i m (α) = n}

Definition 3.

A subcomplex, denoted

{\hat{C h}}_{n, t} (K)

, of

C h^{2} (K)

is called the delayed complex about complex

K

{\hat{C h}}_{n, t} (K) = ⋃_{α \in C_{S_{K}}} G (α)

, where

G (α)

is the complex generated by simplex α. Inductively, the k-fold delayed complex about complex

K

can be defined as

{\hat{C h}}_{n, t}^{k} (K) = {\hat{C h}}_{n, t} ({\hat{C h}}_{n, t}^{k - 1} (K))

Example 1.

Consider an execution in delayed object

D O_{2, t}

with an input 2-simplex

I^{2}

{(p_{i}, v_{i})}_{i = 0}^{2}

, where the colors red, black and yellow are corresponding to

p_{0}, p_{1}

, and

p_{2}

, and

v_{i} (i \in [2])

is the input value of the process

p_{i}

, seeing the left side of Figure 4. Each 2-simplex colored black in the middle and the right of Figure 4 corresponds to a possible execution for

t = 1

and

t = 0

, respectively. Comparing Figure 3 and the middle of Figure 4, it can be seen that each black 2-simplex in the middle of Figure 4 is a 2-simplex of

{\hat{C h}}_{n, 1} (I^{2})

It is not hard to see that any two vertices can be linked by a path (a sequence of 1-simplexes) in

{\hat{C h}}_{2, 1} (I^{2})

, that is to say, it is 0-connected. In fact, by the similar arguments as Theorem 5 and Theorem 6 in [33], we can also show that

{\hat{C h}}_{n, t}^{k} (K)

(t - 1)

-connected, which means that any continuous map f from

(t - 1)

-sphere

S^{t - 1}

to the geometric realization

| {\hat{C h}}_{n, t}^{k} (K) |

{\hat{C h}}_{n, t}^{k} (K)

can be extended to a continuous map

\bar{f}

from t-disk

D^{t}

| {\hat{C h}}_{n, t}^{k} (K) |

. Here, we do not re-show those topology properties of delayed complexes any more, while we focus on the relation between executions in a delayed object and delayed complex. Saraph et al. introduced a sub-complex of

C h^{2} (I^{n})

, denoted by

C h_{t} (I^{n})

, which is in fact the complementary of the star of

C h^{2} (s k e l^{n - t - 1} (I^{n}))

C h^{2} (I^{n}))

. In addition, they implied that there is one-to-one correspondence between a simplex in

C h_{t} (I^{n})

and an execution of that object, which is actually inaccurate. There actually exists some simplex in

C h_{t} (I^{n})

that does not correspond to any execution of object

D O_{n, t}

. The next results present some properties of

C

-extended and

a C

-neighborhood of the complex

K

, by which will give an accurate geometric description of object

D O_{n, t}

Lemma 3.

Suppose

α = {(p_{i}, S_{i})}_{i \in [n]}

is any facet of

S_{k}

with the

P

-partition

Π_{α} = π_{0}, π_{1}, \dots, π_{t}

; then, there exists an integer m such that

| | S_{i} | | \leq n - t

and

| | S_{i}^{'} | | \leq n - t

for any

x \in [m]

, any

p_{i} \in π_{x}

and any

(p_{i}, S_{i}^{'}) \in S_{i}

, where

(p_{i}, S_{i}) \in V^{2} (v a l (V (K))), (p_{j}, S_{j}^{'}) \in S_{i} \subseteq V^{1} (v a l (V (K)))

and

m \leq t

Proof of Lemma 3.

Let

A_{α} = {β \in C h^{2} (K) | β \in C h^{2} (s k e l^{n - t - 1} (I^{n})), β \subseteq α \in S_{K}

I^{n} = c a r r i e r (α, K)}

; then, for any vertex

(p_{i}, S_{i}) \in V (α)

, there are

(p_{i}, S_{i}) \in V^{2} (v a l (V (I^{n})))

and

(p_{j}, S_{j}^{'}) \in S_{i} \subset V^{1} (v a l (V (I^{n})))

. Take a simplex, denoted

B (α)

, from

A_{α}

with the maximal dimension, and it is obvious that

B (α)

is unique. In addition, then there exists a

P

-partition

{\bar{π}}_{0}, {\bar{π}}_{i}, \dots, {\bar{π}}_{s}

B (α)

, denoted

Π_{B (α)}

We claim that

Π_{B (α)}

is the front of

s + 1

components of

Π_{α}

. If not,

Π_{B (α)}

must be a successive truncation in the interior of

Π_{α}

, for

B (α)

is a face of

α

. Hence, there exists at least one component

π_{x}

Π_{α}

but not in

Π_{B (α)}

, such that, for any element

p_{i}

π_{x}

with vertex

(p_{i}, S_{i}) \in V (α)

, there is

S_{i} \subset S_{j}

, where

p_{j}

is any element of an arbitrary component of

Π_{B (α)}

with vertex

(p_{j}, S_{j}) \in V (α)

. Therefore,

| | S_{i} | | < | | S_{j} | |

. Note that

d i m (s k e l^{n - t - 1} (I^{n})) = n - t - 1

; then,

d i m (B (α)) \leq n - t - 1

, and then

| | S_{j} | | \leq | | Π_{B} (α) | | = \sum_{i \in [s]} | | \bar{π_{i}} | | \leq n - t

. Since

(p_{i}, S_{i}) \in α

but

(p_{i}, S_{i}) \notin B (α)

, there is

| | S_{i} | | \geq n - t + 1

; then,

| | S_{i} | | > | | S_{j} | |

, which is an obvious contradiction. It follows that there is always

{\bar{π}}_{i} = π_{i}

for any

0 \leq i \leq s

. Next, it needs to show that

m = s

is a satisfied integer.

In fact, it has showed that

| | v a l ((p_{i}, S_{i})) | | = | | S_{i} | | \leq n - t

for any element

p_{i}

in any component

π_{x}

with

0 \leq x \leq s

. Hence, it only needs to show that

| | S_{j}^{'} | | \leq n - t

for any element

(p_{j}, S_{j}^{'}) \in S_{i}

. If it is not true, there is a vertex

(p_{i}, S_{i}) \in V (B (α))

such that there exists a vertex

(p_{j}, S_{j}^{'}) \in S_{i}

with

| | S_{j}^{'} | | \geq n - t + 1

. Since

B (α) \in C h^{2} (s k e l^{n - t - 1} (I^{n}))

, there must be a simplex

β \in C h (s k e l^{n - t - 1} (I^{n}))

with

B (α) \in C h (β)

. Note that

(p_{i}, S_{i}) \in V (B (α))

, and it follows that

(p_{j}, S_{j}^{'}) \in V (β)

; then,

p_{j} \in χ (β)

. By the construction of

B (α)

, there is

χ (β) = χ (B (α)) \subseteq \cup_{r \in [s]} {\bar{π}}_{r}

. Note that

d i m (s k e l^{n - t - 1} (I^{n})) = n - t - 1

and

S_{j}^{'} \in s k e l^{n - t - 1} (I^{n})

, hence

| | S_{j}^{'} | | \leq d i m (s k e l^{n - t - 1} (I^{n})) + 1 = n - t

, which is a contradiction. □

If we take

I^{n}

as an input n-simplex in an execution of

D O_{n, t}

, it is obvious that

α

corresponds to an impossible execution. Any process

p_{i} \in {\bar{π}}_{0}

executing the second IS does not need to wait after the first IS leading to

| | S_{i}^{'} | | \geq n - t + 1

, which contradicts with Lemma 3. The next lemma implies that, if a facet is in

C

-extended of the

S_{K}

, it corresponds to an impossible execution of object

D O_{n, t}

Lemma 4.

Suppose α is an arbitrary facet of

S_{K}

, and

α^{'}

is any facet in

F l i p (α)

with

P

-partition

Π^{'} = {\bar{π}}_{0}, {\bar{π}}_{1}, \dots, {\bar{π}}_{m}

. Then, there exists an integer q such that, for any integer

x \in [q]

and any element

p_{i} \in {\bar{π}}_{x}

, there is either

| | S_{i} | | \leq n - t

and

| | S_{j}^{'} | | \leq n - t

for any vertex

(p_{j}, S_{j}^{'}) \in S_{i}

, or

| | S_{i} | | \geq n - t + 1

, and there exists at least one vertex

(p_{j}, S_{j}^{'}) \in S_{i}

with

| | S_{j}^{'} | | \leq n - t

, where

(p_{i}, S_{i})

is a vertex of

α^{'}

Proof of Lemma 4.

Assume the

P

-partition of

α

Π = π_{0}, π_{0}, \dots, π_{p}

. If

| | π_{0} | | = 1

, there is only one element

p_{i}

π_{0}

, and then the

P

-partition of

α^{'}

can be represented as

Π^{'} = π_{0} \cup π_{1}, π_{2}, \dots, π_{p}

by Definition 2. Otherwise,

| | π_{0} | | > 1

, and the

P

-partition of

α^{'}

Π^{'} = {p_{i}}, π_{0} - {p_{i}}, π_{1}, \dots, π_{p}

, where

p_{i}

is an arbitrary element of

π_{0}

Set

A_{α} = {β \in C h^{2} (K) | β \in C h^{2} (s k e l^{n - t - 1} (I^{n})), β \subseteq α \in S_{K}, I^{n} = c a r r i e r (α, C h (K))}

. Let

B (α)

be a simplex of

A_{α}

with the maximal dimension; then,

P

-partition of

B (α)

is the previous

s + 1

components of

Π

by the same argument of the proof of Lemma 3, denoted

Π_{B (α)} =

π_{0}, π_{1}, \dots, π_{s}

0 \leq s < p

. Since

0 \leq d i m (B (α)) \leq n - t - 1

, there is

1 \leq | | \cup_{i \in [s]} π_{i} | | \leq n - t

| | \cup_{i = 0}^{s} π_{i} | | = 1

, then

s = 0

, and there is only one element in

π_{0}

. Suppose it is

p_{0}

; then,

P

-partition of

B (α)

π_{0} = p_{0}

. By Lemma 3, for any non-negative integer j, if

j = 0

, then

| | S_{0} | | = 1 \leq n - t

and

| | S_{0}^{'} | | \leq n - t

, where

(p_{0}, S_{0}^{'}) \in S_{0}

. Otherwise,

j \neq 0

, and there is

| | S_{j} | | \geq n - t + 1

for the choice of

α

, where

(p_{j}, S_{j})

is a vertex of

α

but not for

B (α)

, and

(p_{0}, S_{0}^{'}) \in S_{j}

. By Definition 2,

Π^{'} = {p_{0}} \cup π_{1}, π_{2}, \dots, π_{p}

, then

p = m + 1

{\bar{π}}_{i} = π_{i + 1}

with

0 \leq i \leq m

, which implies that it only changes

S_{0}

of the vertex

(p_{0}, S_{0})

α

into

{\bar{S}}_{0}

of the vertex

(p_{0}, {\bar{S}}_{0})

α^{'}

with

{\bar{S}}_{0} = S_{x}

, where

(p_{x}, S_{x})

is any vertex of

α

with

p_{x} \in π_{1}

. It follows that

| | S_{j} | | \geq n - t + 1

and at least one vertex

(p_{0}, S_{0}^{'}) \in S_{j}

with

| | S_{0}^{'} | | \leq n - t

for any

0 \leq q \leq m

, any component

{\bar{π}}_{x}

with

0 \leq x \leq q

, and any element

p_{j} \in {\bar{π}}_{x}

, where

(p_{j}, S_{j})

is a vertex of

α^{'}

| | \cup_{i = 0}^{s} π_{i} | | \geq 2

, then

s = 0

s \geq 1

For the former case, the

P

-partition of

B (α)

{p_{0}}

. By Lemma 3, for any

p_{i} \in π_{0}

, there are

| | S_{i} | | \leq n - t

and

| | S_{j}^{'} | | \leq n - t

, where

(p_{j}, S_{j}^{'})

is an arbitrary element of

S_{i}

and

(p_{i}, a n d S_{i})

is a vertex of

α

. Hence,

Π^{'} = {p_{i}}, π_{0} - {p_{i}}, π_{1}, \dots, π_{p}

, where

p_{i} \in π_{0}

; then,

{\bar{π}}_{0} = {p_{i}}

{\bar{π}}_{1} = π_{0} - {p_{i}}

{\bar{π}}_{2} = π_{1}

, ⋯,

{\bar{π}}_{m} = π_{p}

. Note that the transformation from

α

α^{'}

is only changing

S_{i}

into

{\bar{S}}_{i}

, which contains only one element, where

(p_{i}, {\bar{S}}_{i})

is a vertex of

α^{'}

. Let

q = 1

; then, for any

x \in [q]

and any

p_{r} \in {\bar{π}}_{x}

p_{r} = p_{i}

p_{r} \in π_{0} - {p_{i}}

. It follows that

| | {\bar{S}}_{r} | | = 1 \leq n - t

| | {\bar{S}}_{r} | | \leq n - t

, and

| | {\bar{S}}_{j}^{'} | | \leq n - t

, where

(p_{r}, {\bar{S}}_{r})

is a vertex of

α^{'}

and

(p_{j}, {\bar{S}}_{j}^{'})

is any element of

{\bar{S}}_{r}

For the latter case, the

P

-partition of

B (α)

π_{0}, π_{1}, \dots, π_{s}

; then, either

Π^{'} = {p_{i}}, π_{0} - {p_{i}}, π_{1}, \dots, π_{p}

for

p_{i} \in π_{0}

and

| | π_{0} | | \geq 2

, or

Π^{'} = π_{0} \cup π_{1}, π_{2}, \dots, π_{p}

for

| | π_{0} | | = 1

. For the former situation, let

q = s + 1

, and, for the latter situation, let

q = s - 1

. By the similar arguments as the situation

s = 0

, it can always obtain that, for any

0 \leq x \leq q

and any

p_{i} \in {\bar{π}}_{x}

, there are

| | S_{i} | | \leq n - t

and

| | S_{j}^{'} | | \leq n - t

, where

S_{i}

is the value of the corresponding vertex of

p_{i}

α^{'}

, and

(p_{j}, S_{j}^{'})

is an arbitrary element of

S_{i}

. □

Through the discussion above, we can obtain the following result directly.

Corollary 1.

Suppose α is an n-simplex of

{\hat{S}}_{K}

with the

P

-partition

Π = π_{0}, π_{1}, \dots, π_{m}

; then, there is a non-negative integer q such that, for any

x \in [q]

and any

p_{i} \in π_{x}

, there exists one vertex

(p_{j}, S_{j}^{'}) \in S_{i}

with

| | S_{j}^{'} | | \leq n - t

and

(p_{i}, S_{i}) \in V (α)

3.2. The Characterization of $IDM$

In the previous section, we have given the concepts of the k-fold delayed complex and

C

-neighborhood, and then discussed about their properties. In this section, we will characterize

IDM

from a topological point of view.

Suppose

ε

is an execution in a protocol

P

with a given input n-simplex

I^{n}

; we say a simplex X is reachable by execution

ε

if it can take

V (X)

as a possible return after executing

ε

Lemma 5.

Suppose

P

is the delayed algorithm in Algorithm A1 and

I^{n}

an input n-simplex, then the protocol complex

P (I^{n})

is equivalent to delayed complex

{\hat{C h}}_{n, t} (I^{n})

Proof of Lemma 5.

We only need to show that there is a one-to-one correspondence between the facets of

P (I^{n})

and the facets of

{\hat{C h}}_{n, t} (I^{n})

Suppose

α

is an arbitrary facet in

P (I^{n})

; then, there exists an execution

ε_{α}

P

such that

α

is reachable. Every process in

ε_{α}

just accesses object

D O_{n, t}

once. That is, the process runs the first IS (denoted by IS

_{1}

), waits or not, and then runs the second IS (denoted by IS

_{2}

). Hence, it can model

ε_{α}

as a composite of

ε_{α}^{1}

and

ε_{α}^{2}

, each of which having a wait-free IS. Following Kozlov [39], every IS can be modeled as an ordered partition

π_{0} ≻ π_{1} \dots ≻ π_{m}

along the processes’ running, such that processes in the same component run concurrently, and processes in

π_{i}

run after the processes in

π_{j}

for

j < i

. It follows that there are ordered partitions for

ε_{α}^{1}

and

ε_{α}^{2}

, denoted

π_{0}^{1} ≻ π_{1}^{1} \dots ≻ π_{m_{1}}^{1}

and

π_{0}^{2} ≻ π_{1}^{2} \dots ≻ π_{m_{2}}^{2}

, respectively. Assuming

{(p_{i}, l s_{i}^{1})}_{i \in [n]}

is a return after executing IS

_{1}

, then

l s_{i}^{1}

is a face of

I^{n}

for any

i \in [n]

, and

l s_{i}^{1} \subset l s_{j}^{1}

for

p_{i} \in π_{s}^{1}, p_{j} \in π_{t}^{1}

and

s < t

, and

l s_{i}^{1} = l s_{j}^{1}

for

p_{i}, p_{j} \in π_{x}^{1}

, where

s, t, x \in [m_{1}]

. Likewise, for a return

α = {(p_{i}, l s_{i})}_{i \in [n]}

except after executing IS

_{2}

. Let

S_{i} = l s_{i}

and

\bar{α} = {(p_{i}, S_{i})}_{i \in [n]}

; then,

\bar{α}

is a facet in

C h^{2} (I^{2})

. In the next, it only needs to show that

\bar{α}

is not a facet in a

C

-neighborhood of an arbitrary facet of

S t (C h^{2} (s k e l^{n - t - 1} (I^{n})), C h^{2} (I^{n}))

By steps 5 and step 6 in a delayed algorithm in Algorithm A1, we know that, if the number of elements of the view of a process is at most

n - t

after finishing

ε_{α}^{1}

, it needs to wait until

d o n e

t r u e

. Assume

- 1 \leq s < m_{1}

is the largest integer such that all processes need to wait in

π_{x}^{1}

x \leq s

(here,

s = - 1

means that all processes are wait-free). Then, any process in

π_{x}^{1}

should wait until at least one process in

π_{s + 1}^{1}

has finished

ε_{α}

. Meanwhile, processes in

π_{y}^{1}

do not need to wait and immediately run IS

_{2}

after IS

_{1}

, where

x \leq s

y \geq s + 1

. It follows that, for any process

p_{i}

π_{0}^{2}

, it must appear in

π_{x}^{1}

with

s + 1 \leq x \leq m_{1}

. Assume

l s_{i}^{1}

is the view of

p_{i}

after executing IS

_{1}

; then,

| | l s_{i}^{1} | | \geq n - t + 1

. Let

S_{i}^{'} = l s_{i}^{1}

; then,

α^{'} = {(p_{i}, S_{i}^{'})}_{i \in [n]}

is an n-simplex in

C h (I^{n})

with

| | S_{i}^{'} | | \geq n - t + 1

for

p_{i} \in π_{y}^{1}, y \geq s + 1

. Since

π_{0}^{2}, π_{1}^{2}, \dots, π_{m_{2}}^{2}

is actual, the

P

-partition of

α

and

α \in C h (α^{'}) \subset C h^{2} (I^{n})

, it follows that

\bar{α} \notin (C h^{2} (I^{n}) - {\hat{C h}}_{n, t} (I^{n}))

by Corollary 1. As a result,

\bar{α} \in {\hat{C h}}_{n, t} (I^{n})

. Since

α

is arbitrary,

P (I^{n}) \subseteq {\hat{C h}}_{n, t} (I^{n})

up to equivalence.

On the other hand, assume

β = {(p_{i}, S_{i})}_{i \in [n]}

is an arbitrary facet of

{\hat{C h}}_{n, t} (I^{n})

. We will construct an execution

ε

in object

D O_{n, t}

, such that

β

is a reachable n-simplex for

ε

Since

{\hat{C h}}_{n, t} (I^{n}) \subset C h^{2} (I^{n})

, there exists only one facet

β^{'} \in C h (I^{n})

admitting form

{(p_{i}, S_{i}^{'})}_{i \in [n]}

such that

β

is a facet in

C h (β^{'})

, where

S_{i}^{'}

is a face of

I^{n}

for any

i \in [n]

. By Lemma 1,

β^{'}

has a

P

-partition under containment of the values of its vertices, denoted

Π^{'} = π_{0}^{'}, π_{1}^{'}, \dots, π_{m}^{'}

, such that, for any vertex

(p_{i}, S_{i}^{'})

(p_{j}, S_{j}^{'})

S_{i}^{'} \subset S_{j}^{'}

p_{i} \in π_{s}^{'}

p_{j} \in π_{q}^{'}

and

s < q

, and

S_{i} = S_{j}

p_{i}, p_{j} \in π_{x}^{'}

x \in [m]

. Note that this partition corresponds to an execution IS, hence we can divide the first IS into a sequence of executions, denoted

ε^{'} = ε_{0}^{'} \circ ε_{1}^{'} \dots ε_{m^{'}}^{'}

, such that processes run

ε_{i}^{'}

concurrently if they are in the same component

π_{i}^{'}

, and processes in

π_{i}^{'}

execute

ε_{i}^{'}

after processes in

π_{j}^{'}

running

ε_{j}^{'}

for

i > j

. It not hard to see that

β^{'}

is a reachable n-simplex after executing

ε^{'}

. Likewise, the argument for the

P

-partition of

β

except a series of executions

ε = ε_{0} \circ ε_{1} \dots ε_{q}

and

β

is a reachable n-simplex after executing

ε

. Let

ε_{β} = ε^{'} \circ ε

. It only needs to show that

ε_{β}

is possible executing in object

D O_{n, t}

with input

I^{n}

. Equivalently, it only needs to show that, for any vertex

(p_{i}, S_{i}^{'}) \in β^{'}

, if

| S_{i}^{'} | \leq n - t

p_{i}

does not appear in

π_{0}

. That is, process

p_{i}

does not execute

ε

immediately after running

ε^{'}

, and it needs to wait until “done” is

t r u e

Assume there exists a vertex

(p_{i}, S_{i}^{'})

β^{'}

such that

p_{i} \in π_{0}^{'}

when

| | S_{i}^{'} | | \leq n - t

. By Corollary 1,

β

is an n-simplex of the

C

-neighborhood of an facet in

S t (C h^{2} (s k e l^{n - t - 1} (I^{n})

C h^{2} (I^{n}))

, which is an obvious contradiction for

β \in {\hat{C h}}_{n, t} (I^{n})

. As a result,

ϵ_{β}

is indeed an execution in

D O_{n, t}

with input

I^{n}

Let

l s_{i}

be the view of process

p_{i}

after executing

ε_{β}

, then

l s_{i} = S_{i}

. It follows that

β

is indeed a reachable n-simplex after executing

ε_{β}

. Since

β

is arbitrary in

{\hat{C h}}_{n, t} (I^{n})

{\hat{C h}}_{n, t} (I^{n}) \subseteq P (I^{n})

up to equivalence. By the upper arguments,

P (I^{n})

is equivalent to

{\hat{C h}}_{n, t} (I^{n})

. □

Corollary 2.

Suppose

I^{n}

is an input n-simplex and

P

a protocol with k rounds in which each executes a delayed algorithm in Algorithm A1; then, the protocol complex

P (I^{n})

is equivalent to k-fold delayed complex

{\hat{C h}}_{n, t} (I^{n})

Proof of Corollary 2.

Execution

ε

in P can be modeled as a sequence of executions, denoted by

ε_{1} \circ ε_{2} \circ \dots \circ ε_{k}

, in which each execution

ε_{i}

is an one round execution in delayed object

D O_{(n, t)} [i]

, and each return of a process after executing

ε_{i}

is as an input in execution

ε_{i + 1}

for

0 \leq i < k

. By Lemma 5 and Definition 3, we know that

P (I^{n})

is equivalent to

{\hat{C h}}_{n, t}^{k} (I^{n})

. □

4. Measure Complexity

In this section, we introduce some concepts about the measure of complexity of arbitrary resilient

IDM

, and then we give a topological characterization of the complexity for that model.

4.1. Complexity of the Delayed Model

Suppose

T = (I, O, Δ)

is a decision task and

P_{(n, t, τ, δ)}

is a general algorithm solving T in

IDM

. Let

ε

be an arbitrary execution of

P_{(n, t, τ, δ)}

with a legal input simplex I (i.e.,

d i m (I) \geq n - t

), and

t_{ε}

the maximum number among the effective access to object

D O_{n, t}

for all participating processes in the execution

ε

with input I. Here, “effective” means the number of outputs is less than or equal to

n - t

in an execution in a distributed system. In addition, from now on, once we refer to a protocol

P_{(n, t, τ, δ)}

, it means that the protocol can aways solve some implied decision task.

Definition 4.

The time complexity of a protocol

P_{(n, t, τ, δ)}

on a given input simplex I is the supremum of the set

{t_{ε} | ε

is any execution of the

P_{(n, t, τ, δ)}

with input

I}

, denoted

t_{I}

Remark 1.

Set

t_{I} = - 1

if an input simplex is illegal, since the dimension of that input simplex is less than

n - t

and this time any participating process could not make a decision or output.

Definition 5.

The time complexity of a protocol

P_{(n, t, τ, δ)}

on a given input complex

I

, denoted

t_{P_{(n, t, τ, δ)}}

, is the supremum of the set

{t_{I} | I \in I^{n}}

Before we explore the complexity of a protocol in a delayed model, we introduce some properties of any execution in

D O_{n, t}

, which may be useful for the next discussing.

Lemma 6.

Any execution

ε^{'}

in object

D O_{n, t}

is finite.

Proof of Lemma 6.

Since any execution in

D O_{n, t}

can be modeled as an execution of two-round executions of wait-free IS, even though there is a barrier layer between the two-round IS, it does not contain other actions except for waiting. Note that any execution of IS is finite by Hoest [30], then any execution of two-round IS is also finite. Hence,

ε^{'}

is finite. □

Lemma 7.

Let ε be any execution of protocol

P_{(n, t, τ, δ)}

for a task T in

IDM

, then ε is finite.

Proof of Lemma 7.

Suppose there is no process stopping by crashing; then,

ε

contains at most

n + 1

starting actions and

n + 1

decision actions for there are at most

n + 1

processes and each of them has at most one initial state and one final state. Consider an integer

{\bar{t}}_{ε}

which is the time complexity of

ε

; then,

ε

can be modeled as an ordered executing sequence with at most

{\bar{t}}_{ε}

one-round execution of delayed object

D O_{n, t}

, denoted

ε_{1}

ε_{2}

, ⋯,

ε_{{\bar{t}}_{ε}}

. Despite the fact that some processes may make a decision and output a value among those executions, there is no essential effect on the finiteness. By Lemma 6, each

ε_{i}

is finite. Note that

{\bar{t}}_{ε}

is finite, hence

ε

is finite. □

4.2. Reduced Delayed Complex

Suppose

I

is a pure chromatic n-complex with coloring map

χ

and colors

C = {p_{i}}_{i \in [n]}

. Let X be an m-simplex in

I

and

G (X)

the complex generated by X; then, there is a facet

\bar{X}

I

such that

X \subseteq \bar{X}

χ (X) \subseteq χ (\bar{X})

and

G (X) \subseteq G (\bar{X})

. Let

(S_{X}, A_{X})

be any partition of the set of vertices

V (X)

of X with

A_{X} \neq \emptyset

, such that

V (X) = S_{X} \cup A_{X}

χ (S_{X}) \cap χ (A_{X}) = \emptyset

Definition 6.

Call

R (X)

a reduced delayed complex of X about

χ (X)

(a)

each simplex has form

C * T

, where

C \in G (S_{X}) ⋃ \emptyset

T \in {\hat{C h}}_{n, t} (\bar{X}) ⋃ \emptyset

and

χ (T) \subseteq χ (A_{X})}

;

(b)

there exists one simplex

c a r r i e r (T, \bar{X})

\bar{X}

such that

C * c a r r i e r (T, \bar{X})

is a face of X.

Furthermore, call

R (I)

a reduced delayed complex of

I

about C if

R (I) = ⋃_{X \in I} R (X)

Remark 2.

C and T can not be empty-set at the same time.
If $S_{X} = \emptyset$ , then $R (X)$ is a sub-complex of ${\hat{C h}}_{n, t} (\bar{X})$ .
$R (X)$ is also a pure chromatic m-complex with the same set of colors as X.
Suppose $(S_{\bar{X}}, A_{\bar{X}})$ is a partition of $\bar{X}$ ; then, there must be $S_{X} \subseteq S_{\bar{X}}$ and $A_{X} \subseteq A_{\bar{X}}$ .
Suppose Y is another simplex in $I$ with a partition $(S_{Y}, A_{Y})$ , and assume $X \cap Y = H \neq \emptyset$ . If $v \in H$ and $v \in S_{X}$ , then $v \in S_{Y}$ , and vice versa; if $v \in H$ and $v \in A_{X}$ , then $v \in A_{Y}$ , and vice versa.
In fact, it needs only to consider all the facets of complex $I$ to construct the reduced delayed complex $R (I)$ ; that is, $⋃_{X \in I} R (X) = ⋃_{X \in I, d i m (X) = n} R (X)$ .

Example 2.

Let

I^{2} = {v_{0}, v_{1}, v_{2}}

be a chromatic 2-simplex with coloring map χ, where

χ (v_{0}) = r e d

χ (v_{1}) = b l a c k

and

χ (v_{2}) = y e l l o w

, seeing the left in Figure 5. Suppose

S_{I^{2}} = {v_{0}}

and

A_{I^{2}} = {v_{1}, v_{2}}

; then,

V (R (I^{2}))

is a collection of

v_{0}

and all the vertices coloring black and yellow in the black area of the middle figure in Figure 5. Reduced delayed complex

R (I^{2})

can be obtained by pulling all vertices coloring red in the black area of the middle figure in Figure 5 over the flat and then pasting them together as just one vertex, seeing the right in Figure 5.

Inductively, we can define a k-fold reduced delayed complex for n-complex

I

, denoted

R^{k} (I)

. For

k = 0

, it is equal to

I

. For

k \geq 1

, it can be given by the following procedure: the vertices of

I

can be divided into two disjoint parts, denoted

S_{0}

and

A_{0}

with

A_{0} \neq \emptyset

, respectively. Let

\bar{I} = {X \in I | d i m (X) = n}

; then, for any element

X \in \bar{I}

, there exists a partition

(S_{0, X}, A_{0, X})

of X such that

S_{0, X} \subseteq S_{0}

A_{0, X} \subseteq A_{0}

and

χ (A_{0, X}) \subseteq χ (X) = C

. Hence,

S_{0} = ⋃_{X \in \bar{I}} S_{0, X}, A_{0} = ⋃_{X \in \bar{I}} A_{0, X} .

Let

S_{0} = ⋃_{X \in \bar{I}} G (S_{0, X})

be a sub-complex of complex

I

, and

C_{A_{0}} = χ (A_{0})

C_{A_{0, X}} = χ (A_{0, X})

. Any simplex in

R^{k} (I)

has form

C^{'} * T^{'}

, where

C^{'} \in S_{0}

T^{'} \in R^{k - 1} ({\hat{C h}}_{n, t} {(I)}_{C_{A_{0}}})

C^{'} * c a r r i e r (T^{'}, I)

is an n-simplex of

I

, and

{\hat{C h}}_{n, t} {(I)}_{C_{A_{0}}} = ⋃_{X \in \bar{I}} {\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}

. Here,

{\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}

represents a complex, in which each simplex

α

is a face of a simplex

β \in {\hat{C h}}_{n, t} (X)

with

χ (α) \subseteq C_{A_{0, X}}

. It is not hard to show that

{\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}

is a pure sub-complex of the complex

{\hat{C h}}_{n, t} (X)

with dimension

| | C_{A_{0, X}} | | - 1

. By Definition 6, we can construct

R^{k - 1} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}})

inductively.

Intuitively, each vertex of the reduced delayed complex

R (X)

with input simplex X records a local state, in which the process can decide and has no output. Without loss of generality, assume

X \in I

is a facet. For each process

p_{x}

, it needs to check whether its initial state can decide by the predicted function before accessing

D O_{n, t} [1]

. If it can decide and there is no output, then it will make a decision and give an output, and then the process

p_{x}

may continue executing in the following round or just stop for crashing; anyway, it has nothing to do with output of the process

p_{x}

. If it can not, it needs to accumulate more information by object

D O_{n, t} [1]

, which does have an effect on its output. Putting all initial states in which each process can decide together as a set

S_{X}

; it not hard to see that

S_{X}

can span a face of X. Since, for a process that is not in

χ (S_{X})

, it needs to access object

D O_{n, t}

to obtain more information to decide, each local state of a process

p_{j}

with on output after executing object

D O_{n, t} [1]

corresponds to a vertex in

V ({\hat{C h}}_{n, t} {(X)}_{C_{A_{X}}})

, where

A_{X} = V (X) - S_{X}

. By the Definition 6,

R (X)

indeed describes the one-round execution of

P_{(n, t, τ, δ)}

. The next two lemmas show the general execution (i.e., there are many rounds in it) of

P_{(n, t, τ, δ)}

Lemma 8.

Suppose

P_{(n, t, τ, δ)}

is a protocol in

IDM

with input n-complex

I

. If the time complexity of

P_{(n, t, τ, δ)}

about

I

is k, then protocol complex

P_{(n, t, τ, δ)} (I)

is equivalent to a k-fold reduced delayed complex

R^{k} (I)

I

, where k is non-negative integer.

Proof of Lemma 8.

Use induction to the complexity. Assume

t_{P_{(n, t, τ, δ)}} = 0

, it is obvious that

P_{(n, t, τ, δ)} (I)

≅

I

. Note that

R^{0} (I) = I

, hence

P_{(n, t, τ, δ)} (I) ≅ R^{0} (I)

. Suppose the conclusion is established for any non-negative integer

t_{P_{(n, t, τ, δ)}}

, which is less than k. Consider

t_{P_{(n, t, τ, δ)}} = k

Let

v_{i} = (p_{i}, x_{i})

be any vertex in

I

, and

χ

and

v a l

the coloring map and assignment function for

I

such that

χ (v_{i}) = p_{i}

and

v a l (v_{i}) = x_{i}

. Note that whether the process

p_{i}

can make a decision and output a value in its initial state before accessing object

D O_{n, t} [1]

or not depends on the value of predicted function

τ

v_{i}

. If

τ (v_{i})

t r u e

and

p_{i}

does not output,

p_{i}

is decidable and outputs

δ (v_{i})

before proceeding. Otherwise, process

p_{i}

can not make a decision, and it needs to accumulate information by accessing object

D O_{n, t} [1]

. It follows that

τ

divides

V (I)

into two disjoint parts, denoted

S_{0}

and

A_{0}

, respectively, such that

τ (S_{0}) = t r u e

and

τ (A_{0}) = f a l s e

. Since

k = t_{P_{(n, t, τ, δ)}} \geq 1

, there is at least one vertex

v_{x}

V (I)

such that

τ (v_{x}) = f a l s e

, and then

A_{0} \neq \emptyset

Consider an arbitrary facet

X \in I

, such that the time complexity of the protocol

P_{(n, t, τ, δ)}

about X is k. By the former argument, there must exist a partition of

V (X)

, denoted by

(S_{0, X}, A_{0, X})

, such that

S_{0, X} \subseteq S_{0}, A_{0, X} \subseteq A_{0}

and

X = S_{0, X} * A_{0, X}

. Any execution of

P_{(n, t, τ, δ)}

can be modeled as a composite of an ordered sequence of one-round executions, in which each participating process accesses object

D O_{n, t} [r]

at most once in round r, and the returns of concurrent round can be as the inputs to the next round. By Lemma 5, each return after executing round 1 is a simplex in

{\hat{C h}}_{n, t} (X)

; then, the time complexity of

P_{(n, t, τ, δ)}

on each simplex in

{\hat{C h}}_{n, t} (X)

is at most

k - 1

. By hypothesis,

P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} (X)) ≅ R^{k - 1} ({\hat{C h}}_{n, t} (X)) .

χ (\bar{v}) \in χ (S_{0, X})

for a vertex

\bar{v} \in V ({\hat{C h}}_{n, t} (X))

, the process

χ (\bar{v})

has obtained an output before accessing object

D O_{n, t} [1]

. Hence, it only needs to focus on the sub-complex

{\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}

of complex

{\hat{C h}}_{n, t} (X)

, and there is

P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}) ≅ R^{k - 1} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}) .

Let

G (S_{X}) * P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} (X))

be the collection of all simplexes with form

α * β

, where

α \in G (S_{0, X}) \cup \emptyset

β \in {\hat{C h}}_{n, t} (X_{C_{A_{0, X}}}) \cup \emptyset

, and

α

and

β

can not be empty sets at the same time. Since

G (S_{0, X})

and

{\hat{C h}}_{n, t} (X_{C_{A_{0, X}}})

all are chromatic complexes and

χ (P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}})) \cap χ (S_{0, X}) = \emptyset

G (S_{X}) * P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} (X))

is a chromatic complex. Likewise,

G (S_{0, X}) * R^{k - 1} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}})

is also a chromatic complex.

It follows that

G (S_{X}) * P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} (X)) ≅ G (S_{0, X}) * R^{k - 1} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}) .

Note that

P_{(n, t, τ, δ)} (X) = G (S_{0, X}) * P_{(n, t, τ, δ)} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}})

and

R^{k} (X) = G (S_{0, X}) * R^{k - 1} ({\hat{C h}}_{n, t} {(X)}_{C_{A_{0, X}}}) .

Hence,

P_{(n, t, τ, δ)} (X) ≅ R^{k} (X)

. Since X is arbitrary facet in

I

, there is

P_{(n, t, τ, δ)} (I) = ⋃_{X \in I, d i m (X) = n} P_{(n, t, τ, δ)} (X) .

Therefore,

P_{(n, t, τ, δ)} (I) ≅ ⋃_{X \in I, d i m (X) = n} R^{k} (X) .

By Definition 6, there is

⋃_{X \in I, d i m (X) = n} R^{k} (X) = R^{k} (I) .

It follows that

P_{(n, t, τ, δ)} (I) ≅ R^{k} (I)

. □

Lemma 9.

Suppose

I

is a pure chromatic n-complex with coloring map χ, and

R^{k} (I)

is a k-fold reduced delayed complex about

I

, where k is a non-negative integer. Then, there exists a protocol

P_{(n, t, τ, δ)}

IDM

with time complexity k about complex

I

, such that its protocol complex is equivalent to

R^{k} (I)

Proof of Lemma 9.

Assume we have obtained the predicted function

τ

and the decision map

δ

in the delayed system with

n + 1

processes, then we can construct a protocol

P_{(n, t, τ, δ)}

in that model in the way shown as in Algorithm A1. By Lemma 8, the protocol complex

P_{(n, t, τ, δ)} (I)

is indeed equivalent to complex

R^{k} (I)

. Next, we mainly focus on constructing the predicted function

τ

and the decision map

δ

Consider an arbitrary facet X in n-complex

I

. By Definition 6 and the fundamental configuration process of k-fold reduced delayed complex

R^{k} (X)

, there is a sequence of complexes, denoted

X, R (X), R^{2} (X), \dots, R^{k} (X)

, respectively, and two corresponding complex sequences, denoted

S_{0, X}, S_{1, X}, S_{2, X}, \dots, S_{k - 1, X}

and

A_{0, X}, A_{1, X}, A_{2, X}, \dots, A_{k - 1, X}

, respectively. Such that, for any

i, j \in [k - 1]

, if

i \neq j

, there are

χ (S_{i, X}) \cap χ (S_{j, X}) = \emptyset

and

χ (S_{i, X}) \cap χ (A_{i, X}) = \emptyset

, and, for any

r \in [k - 2]

, there is

χ (A_{r, X}) = χ (S_{r + 1, X}) \cup χ (S_{r + 1, X})

Note that, for any

i \in [k - 1]

V (S_{i, X})

and

V (A_{i, X})

are the subsets of

V^{2 i} (D_{v a l (X)})

. Define function

τ_{X} : ⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (X)}) ⟶ {t r u e, f a l s e},

satisfying if

v \in V (S_{i, X}), i \in [k - 1]

, then

τ_{X} (v) = t r u e

, otherwise

τ_{X} (v) = f a l s e

. Since

V (S_{i, X}) \cap V (S_{j, X}) = \emptyset

for any

i \neq j \in [k - 1]

τ_{X}

is well-defined. By the similar way, we can define a color-preserving simplicial map

δ_{X} : ⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (X)}) ⟶ V^{0} (D_{v a l (O)}),

such that, for any

v \in ⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (X)})

, if

τ_{X} (v) = t r u e

, then

δ_{X} (v) = (χ (v), x)

, otherwise

δ_{X} (v) = (χ (v), ⊥)

, where x is a value in

v a l (O)

and ⊥ is just a placeholder. It is obvious that

δ_{X}

is also well-defined.

Note that

I

is pure and X is arbitrary in complex

I

, and let

τ = \sum_{X \in I, d i m (X) = n} τ_{X}, δ = \sum_{X \in I, d i m (X) = n} δ_{X} .

Next, we only need to check that

τ

and

δ

are well-defined. Assume Y is another facet in complex

I

and

X \cap Y = C \neq \emptyset

. By Definition 6 and the construction of

τ_{X}

and

τ_{Y}

, there is

τ_{X} (⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (C)})) = τ_{Y} (⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (C)})),

which implies that

τ

is well-defined. Therefore,

τ

is exactly a satisfied predicted function from

⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (I)})

{t r u e, f a l s e}

. In a similar way, it can also show that

δ

is well-defined and a satisfied decision map from

⋃_{i \in [k - 1]} V^{2 i} (D_{v a l (I)})

V^{0} (D_{O})

. □

4.3. Arbitrary Resilient Asynchronous Complexity Theorem

The strength and usefulness of

IDM

of computation comes from the fact that each of its associated protocol complexes has a slightly nice, recursive structure. In fact, it turns out that any protocol complex of

IDM

is equivalent to a reduced delayed complex which can be constructed by 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 output complex of a decision task that agrees with the task specification can be interpreted as a topological measure of the task’s time complexity.

Let

T = (I, O, Δ)

be a decision task and k a non-negative integer. We say

R^{k} (I)

is a mappable reduced subdivision of the input complex and k is a mappable level of reduced subdivision if there exists a color-preserving simplicial map

μ

from

R^{k} (I)

O

such that, for all

X \in R^{k} (I)

μ (X) \in Δ (c a r r i e r (T, I))

Theorem 1.

A decision task

T = (I, O, Δ)

has a t-resilient solvable protocol in

IDM

with worst case time complexity

k_{X}

on legal inputs

X \in I

if and only if there is a mappable reduced subdivision

R^{k} (I)

with level

k_{X}

on X.

Proof of Theorem 1.

Herlihy and Shavit in [40] imply that decision task T has a t-resilient solvable protocol

P_{(n, t, τ, δ)}

IDM

if and only if the following triangle is commutative, where

μ

is a color and carrier preserving simplicial map from

P_{(n, t, τ, δ)}

O

By Lemma 8, any protocol complex

P_{(n, t, τ, δ)} (I)

is equivalent to a k-fold reduced delayed complex

R^{k} (I)

. The protocol

P_{(n, t, τ, δ)}

solves task T in

IDM

with worst case time complexity

k_{X}

on X. It follows that

k \geq k_{X}

. Let k be equal to

k_{X}

and

μ^{'}

a color-preserving isomorphism from

R^{k} (I)

P_{(n, t, τ, δ)} (I)

, and let

μ = δ \circ μ^{'}

. Then,

μ

is a color and carrier preserving simplicial map from

R^{k} (I)

O

. It follows that

R^{k} (I)

is mappable.

On the other hand, any mappable reduced subdivision

R^{k} (I)

with level

k_{X}

on X is equivalent to the protocol complex

P_{(n, t, τ, δ)} (I)

of a protocol in the delayed model with worst case complexity

k_{X}

on legal input X by Lemma 9. Assume

γ

is a color-preserving simplicial map from

P_{(n, t, τ, δ)} (I)

R^{k} (I)

. If there is a color and carrier preserving simplicial map

μ

from

R^{k} (I)

O

, by setting

δ = μ \circ γ

, then protocol

P_{(n, t, τ, δ)}

can solve T in a delayed model with worst case time complexity

k_{X}

on legal inputs

X \in I

. □

Remark 3.

When

t = n

IDM

is actually a wait-free non-standard iterated immediate snapshot model(NIIS) proposed by Hoest and Shavit [30]. As a corollary of Theorem 1, it can easily obtain the wait-free asynchronous complexity theorem.

5. Application

In this section, we will analyze the time complexity of the well-known Approximate Agreement task as an application of Theorem 1. An approximate agreement

T = (I, O, Δ)

in a distributed system with

n + 1

processes can be specified as follows: each n-simplex

I \in I

has form

{(p_{i}, v_{i})}_{i \in [n]}

, where each

v_{i}

is in a finite set S of real numbers, and

p_{i}

is the ID of the process. In addition, each n-simplex

O \in O

has the form

{(p_{i}, w_{i})}_{i \in [n]}

, such that, for any

i \in [n]

w_{i}

is also in S; and, for any

i, j \in [n]

, there is

| w_{i} - w_{j} | < ϵ

, where

ϵ

is the same predetermined number that is more than 0, and

(I, O) \in Δ

v a l (O) \subseteq v a l (I) \cup {⊥}

For a wait-free model, Hoest et al. [30] have showed that the time complexity of approximate agreement is

⌊ l o g_{d} \frac{m a x {v a l (I)} - m i n {v a l (I)}}{ϵ} ⌋

for

d = 3

n = 1

and

d = 2

n \geq 2

with any input simplex I. Here, we investigate the time complexity of approximate agreement in

IDM

. Since any legal input simplex

α_{I}

, there is always a facet

α \in I

such that

α_{I}

is a face of

α

, and they admit the same time complexity. Therefore, it only needs to consider all the facets in the input complex

I

In order to make the next discussion brief, let

D (α) = m a x {v a l (α)} - m i n {v a l (α)}

for any chromatic simplex

α

, and

D (K) = m a x_{α \in K} D (α)

for a chromatic complex

K

. In addition, let

χ

be the coloring map with the collection of all the IDs of the processes.

Theorem 2.

Suppose

ϵ > 0

is a predetermined number and

T = (I, O, Δ)

is an approximate agreement, then there is a protocol

P

solving T in

IDM

with time complexity

⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋

on any input n-simplex I, where

m = 9

n = 1

and

m = 4

n \geq 2

Proof of Theorem 2.

Assume task T has protocol

P

with the time complexity

k_{I}

on input n-simplex

I \in I

. By Theorem 1, there is a color-preserving simplicial map

ψ : R^{k} (I) ⟶ O,

carried by

Δ

, such that

k = k_{I}

ψ

acts on the sub-complex

R^{k} (I)

of the complex

R^{k} (I)

Relabel all of the vertices of

R^{k} (I)

by associating map

ψ

in the following way. For each vertex

v \in R^{k} (I)

, label v with

v a l (ψ (v))

while retaining its coloring. It is obvious that this labeling satisfies the task specification, since, for any n-simplex

α \in I

that contains v, the labeling

v a l (ψ (v))

must be in

v a l (α)

. Note that

ψ

is a simplicial map from

R^{k} (I)

O

; then,

D (ψ (α)) < ϵ

for any

α \in R^{k} (I)

. Since

D (α) = D (ψ (α))

and

α

is chosen arbitrary, then

D (R^{k} (I)) < ϵ .

Consider an arbitrary n-simplex

I \in I

. By the Definition 6,

(l + 1)

-fold reduced delayed complex

R^{l + 1} (I)

can be obtained from an l-fold reduced delayed complex

R^{l} (I)

. That is,

V (R^{l + 1} (I))

can be divided into two disjoint sets of vertices

S_{l, I}

and

A_{l, I}

, such that

S_{l, I} \subseteq V (R^{l} (I)) \subseteq V (R^{k} (I))

and

A_{l, I} \subseteq V ({\hat{C h}}_{n, t}^{2 l} (I))

and each simplex of

R^{l} (I)

can be spanned by a subset of

S_{l, I}

and a subset of

A_{l, I}

. Hence,

D (R^{l} (I)) = D (G^{'} (A_{l, I}))

, where

G^{'} (A_{l, I})

is the complex generated by

A_{l, I}

in which each simplex in

{\hat{C h}}_{n, t}^{2 l} (I)

. By the similar argument of the proof of Theorem 6.1 [30], there is

D (R^{k} (I)) \geq \frac{D (I)}{d^{2 k_{I}}},

where

k_{I}

is the complexity on I, and

d = 3

n = 1

and

d = 2

n \geq 2

. Then,

\frac{D (I)}{d^{2 k_{I}}} < ϵ .

Let

m = d^{2}

, then

⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋ \leq k_{I},

where

n = 1

m = 9

and

m = 4

n \geq 2

. Therefore,

⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋

is a lower bound of the time complexity on simplex I.

On the other hand, suppose there is a color and carrier preserving simplicial map

ψ

from k-fold reduced delayed complex

R^{k} (I)

O

, such that

k = ⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋

ψ

acts on the sub-complex

R^{k} (I)

of the complex

R^{k} (I)

for any input facet

I \in I

, where

m = 9

n = 1

and

m = 4

n \geq 2

. By Theorem 1, there is a protocol that solves approximate agreement T with the worst case time complexity

⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋

on input n-simplex I, which implies that

⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋

is also an upper bound of the time complexity on input I.

In fact, the existence of that map

ψ

is equivalent to that there exists a labeling of the vertices of

R^{k} (I)

which agrees with the initial values of input complex

I

with

D (R^{k} (I)) < ϵ

. By definition 6, we know that k-fold reduced delayed complex

R^{k} (I)

is recursive, hence we can label each vertex of

R^{k} (I)

at each fold as follows. Consider any facet I of

I

; for each fold

1 \leq l \leq k

, a vertex v is in

A_{l - 1, I}

if there exists a facet

α

{\hat{C h}}_{n, t}^{l} (I)

taking v as one of its vertices, such that

| v a l (v) - v a l (w) | > ϵ

; otherwise, v is in

S_{l - 1, I}

, where w is a vertex in

α

. Assume it has relabelled all vertices of

{\hat{C h}}_{n, t}^{l} (I)

but with colors in

χ (A_{l - 1, I})

. Before entering the next fold, it needs to relabel all vertices of

{\hat{C h}}_{n, t}^{l} {(I)}_{C_{A_{l - 1, I}}}

but in

S_{l, I}

. Consider any facet

α

{\hat{C h}}_{n, t}^{l - 1} (I)

. At first, relabel all vertices of

C h^{2} (α)

as follows: If

d i m (α) = 1

, label the new vertices with values

\frac{M_{l} + 8 \cdot m_{l}}{9}, \frac{2 \cdot M_{l} + 7 \cdot m_{l}}{9}, \dots, \frac{8 \cdot M_{l} + m_{l}}{9}

, such that

D (C h^{2} (α)) = \frac{M_{l} - m_{l}}{9}

; otherwise, label new vertices with

\frac{M_{l} + 3 \cdot m_{l}}{4}, \frac{2 \cdot M_{l} + 2 \cdot m_{l}}{4}, \frac{3 \cdot M_{l} + m_{l}}{4}

, such that

D (C h^{2} (α)) = \frac{M_{l} - m_{l}}{4}

, where

M_{l} = m a x {v a l (α)}, m_{l} = m i n {v a l (α)}

. It follows that

D ({\hat{C h}}_{n, t} (α)) \leq D (C h^{2} (α)

for the su-bcomplex

{\hat{C h}}_{n, t} (α)

C h^{2} (α)

. By this construction, we can see that, if

D (R^{l} (I)) > ϵ

, either

D (R^{l + 1} (I)) < ϵ

D (R^{l + 1} (I)) = \frac{D (R^{l} (I))}{m}

, where

m = 9 o r 4

, which implies that, for any facet

I \in I

R^{k} (I)

is as a

⌊ l o g_{m} \frac{D (I)}{ϵ} ⌋

-fold reduced sub-complex of

R^{k} (I)

for

m = 9

d i m (I) = 1

and

m = 4

d i m (I) \geq 2

. □

Remark 4.

We only consider the input simplex which is a facet, since, for any legal input simplex α, there always exists a facet

α_{0} (\supseteq α)

such that they have the same time complexity for it only needs to assign the processes that are in

χ (α_{0})

but not in

χ (α)

with the same value as any value in

v a l (α)

6. Conclusions and Future Work

This paper modifies the description of a protocol complex of a delayed algorithm proposed by Saraph, Herlihy, and Gafni in [33], in which they thought the protocol complex was equivalent to

C h_{t} (I^{n})

. However, we give a precisely topological characterization of that algorithm and show that the protocol complex is equivalent to

{\hat{C h}}_{n, t} (I^{n})

, which is a proper subset of complex

C h_{t} (I^{n})

, which implies there exists a simplex in complex

C h_{t} (I^{n})

corresponding to an impossible execution in

D O_{n, t}

Take

D O_{n, t}

as a black-box and then construct an iterated delayed model (

IDM

), which turns out to be an arbitrary resilient algorithm in an asynchronous distributed system. Even though Delporte et al. [36] have showed that a t-resilient immediate snapshot is impossible in a t-resilient asynchronous distributed system by showing the equivalence of consensus (

2 t - n + 1

-set agreement) and a t-resilient immediate snapshot for

t < (n + 1) / 2

(

t \geq (n + 1) / 2

), there exist some tasks that admit weaker computing power than consensus and set agreement. In addition, each immediate snapshot in

IDM

is actually a wait-free immediate snapshot from a local point of view, which turns out to be implemented in a t-resilient asynchronous distributed system [37] but not for a t-immediate snapshot. Hence, it makes sense for the construction of

IDM

This paper gives a topological characterization of the time complexity of an arbitrary resilient distributed asynchronous model theoretically by the number of subdivisions of the worst input case. Although the topological structures are very complex and difficult to construct, it turns the dynamic analysis of that system into a static geometric structure analysis, which may lead to a great significance in practical applications. Using that characterization gives a time complexity of approximate agreement in t-resilient

IDM

, in which it can obtain the time complexity of approximate agreement in a wait-free asynchronous model by taking

t = n

, showed by Hoest et al. [30].

Unfortunately, any model involved in this paper refers to only a crashing failure model, which is an ideal failure model. Meanwhile, the most common failure model is the Byzantine failure model, in which the behavior of a byzantine process is out of control, leading to difficulty in analyzing its complexity in a distributed asynchronous system. In addition, in order to obtain the characterization of the complexity of the Byzantine failure model, it may be necessary to obtain more information during an execution, not just the initial states and terminal states. However, the main technique of our work is based on the method and framework proposed by Herlihy et al. [8,18,40,41], in which it is not necessary to care about the intermediate process during an execution but the initial states and terminal states.

In the future, we will construct a new geometric structure, the directed topological model, which is proposed mainly to be used to study concurrent computation [42], and from which it may catch up not only the initial states and terminal states but also almost all information during an execution. Investigating the topological characterization, such as the invariant of directed homotopy or directed homology, and then exploring the relationship between the computational complexity and those topological characterizations, may give us a feasible way to study Byzantine complexity.

Author Contributions

Conceptualization, Y.Y. and X.L.; Formal analysis, Y.Y., X.L., and F.L.; Methodology, Y.Y. and J.W.; Writing—original draft, Y.Y.; Writing—review and editing, X.L. and F.L. All authors have read and agreed to the published version of the manuscript.

Funding

The work is partially supported by the National Natural Science Foundation of China (Grant No. 12071051, 62072433), partially supported by National Natural Science Foundation of China 647 (Grant No. 11971144), and partially supported the Fundamental Research Funds for the Central Universities (Grant No. DUT21RC(3)102) and partially supported High-level Scientific Research Foundation of Hebei Province and the start-up research fund from BIMSA.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

Not applicable.

Conflicts of Interest

The authors declare no conflict of interest. The funders had no role in the design of the study; in the collection, analyses, or interpretation of data; in the writing of the manuscript, or in the decision to publish the results.

Abbreviations

The following abbreviations are used in this manuscript:

Symbol	Corresponding Meaning
$K$ , $I$	(abstract) simplicial complexes
$X, α, β, γ$	(abstract) simplexes
$V (X) / V (K)$	the set of vertices of simplex X/simplicial complexes $K$
$\| \| X \| \|$	the number of vertices (or elements) of simplex (or set) X
$\| X \|$	the geometric realization of simplex X
$G (X)$	the complex generated by simplex X
$D O_{n, t}$	delayed object consists of $n + 1$ processes with t-resilience
$D O_{n, t} [r]$	invoking delayed object $D O_{n, t}$ in r-th round execution
$V^{k} (D)$	the datatype generated by k-fold iterations with data D
$F l i p (X)$	$C$ -extended of simplex X
$\hat{X}$	$C$ -neighborhood of simplex X
${\hat{C h}}_{n, t}^{k} (I)$	k-fold delayed complex about n-simplicial complex $I$
$R^{k} (K)$	k-fold reduced delayed complex about n-simplicial complex $I$
$IDM$	iterated delayed model

Appendix A. Delayed Algorithm

Algorithm A1: Delayed algorithm [33]

(1) shared

m e m 0 [n + 1]

m e m 1 [n + 1]

, done;

(2) done ← false;

(3) immediate

(4)

m e m 0 [i d] \leftarrow i n p u t_{i d}

;

(5)

s n a p 0 [i d] \leftarrow s n a p s h o t (m e m 0)

;

(6) if

| s n a p 0 [i d] | \leq n - t

then

(7) while

n o t d o n e

(8) skip

(9) immediate

(10)

m e n 1 [i d] \leftarrow s n a p 0 [i d]

;

(11)

s n a p 1 \leftarrow s n a p s h o t (m e m 1)

;

(12)

d o n e \leftarrow t u r e

;

(13) return

s n a p 1

;

References

Fischer, M.J.; Lynch, N.A.; Paterson, M.S. Impossibility of distributed consensus with one faulty process. In Proceedings of the Second ACM SIGACT-SIGMOD Symposium on Principles of Database Systems, Atlanta, GA, USA, 21–23 March 1983; pp. 1–7. [Google Scholar]
Lynch, N. Distributed Algorithms; Morgan Kaufmann: San Francisco, CA, USA, 1996. [Google Scholar]
Herlihy, M. Wait-free synchronization. ACM Trans. Program. Lang. Syst. 1991, 13, 124–149. [Google Scholar] [CrossRef]
Mahafzah, B.A.; Al-Zoubi, I. Broadcast communication operations for hyper hexa-cell interconnection network. Telecommun. Syst. 2018, 67, 73–93. [Google Scholar] [CrossRef]
Herlihy, M.; Shavit, N. The asynchronous computability theorem for t-resilient tasks. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, San Diego, CA, USA, 16–18 May 1993; pp. 111–120. [Google Scholar]
Attiya, H.; Amotz, B.N.; Dolev, D. Sharing memory robustly in message-passing systems. J. ACM 1995, 42, 124–142. [Google Scholar] [CrossRef]
Herlihy, M.; Rajsbaum, S. Set consensus using arbitrary objects (preliminary version). In Proceedings of the Thirteenth Annual ACM Symposium on Principles of Distributed Computing, Los Angeles, CA, USA, 14–17 August 1994; pp. 324–333. [Google Scholar]
Herlihy, M.; Rajsbaum, S. Algebraic spans (preliminary version). In Proceedings of the Fourteenth Annual ACM Symposium on Principles of Distributed Computing, Ottawa, ON, Canada, 20–23 August 1995; pp. 90–99. [Google Scholar]
Herlihy, M.; Rajsbaum, S. The topology of distributed adversaries. Distrib. Comput. 2013, 26, 173–192. [Google Scholar] [CrossRef]
Herlihy, M.; Rajsbaum, S.; Raynal, M.; Stainer, J. From wait-free to arbitrary concurrent solo executions in colorless distributed computing. Theor. Comput. Sci. 2017, 683, 1–21. [Google Scholar] [CrossRef]
Herlihy, M.; Rajsbaum, S.; Tuttle, M.R. Unifying synchronous and asynchronous message-passing models. In Proceedings of the Seventeenth Annual ACM Symposium on Principles of Distributed Computing, PODC '98, Puerto Vallarta, Mexico, 28 June–2 July 1998; ACM: New York, NY, USA, 1998; pp. 133–142. [Google Scholar]
Kuznetsov, P.; Rieutord, T.; He, Y. An asynchronous computability theorem for fair adversaries. CoRR 2020, abs/2004.08348. [Google Scholar]
Yue, Y.G.; Lei, F.C.; Liu, X.W.; Wu, J. Asynchronous computability theorem in arbitrary solo models. Mathematics 2020, 5, 757. [Google Scholar] [CrossRef]
Gafni, E.; Kuznetsov, P.; Manolescu, C. A generalized asynchronous computability theorem. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC’14, Paris, France, 15–18 July 2014; pp. 222–231. [Google Scholar]
Moses, Y.; Rajsbaum, S. Toward a topological characterization of asynchronous complexity. SIAM J. Comput. 2002, 31, 989–1021. [Google Scholar] [CrossRef] [Green Version]
Nicolas, B.S.; Guerraoui, R.; Florian, H. Fast byzantine agreement. In Proceedings of the ACM Symposium on Principles of Distributed Computing, PODC’13, Montreal, QC, Canada, 22–24 July 2013; pp. 57–64. [Google Scholar]
Mendes, H.; Tasson, C.; Herlihy, M. Distributed computability in byzantine asynchronous systems. CoRR 2013, abs/1302.6224. [Google Scholar]
Herlihy, M.; Rajsbaum, S. The decidability of distributed decision tasks (extended abstract). In Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, TX, USA, 4–6 May 1997; pp. 589–598. [Google Scholar]
Herlihy, M.; Rajsbaum, S. A classification of wait-free loop agreement tasks. Theor. Comput. Sci. 2003, 291, 55–77. [Google Scholar] [CrossRef] [Green Version]
Liu, Y.W.; Xu, Z.W.; Pan, J.Z. Classifying rendezvous tasks of arbitrary dimension. Theor. Comput. Sci. 2009, 410, 2162–2173. [Google Scholar] [CrossRef] [Green Version]
Yue, Y.G.; Lei, F.C.; Wu, J. The evolution of non-degenerate and degenerate rendezvous tasks. Topol. Its Appl. 2019, 264, 187–200. [Google Scholar] [CrossRef]
Biran., O.; Moran, S.; Zaks, S. Tight bounds on the round complexity of distributed 1-solvable tasks. Theor. Comput. Sci. 1995, 145, 271–290. [Google Scholar] [CrossRef] [Green Version]
Castañeda, A.; Rajsbaum, S. New combinatorial topology bounds for renaming: The lower bound. Distributed Comput. 2010, 22, 287–301. [Google Scholar] [CrossRef]
Castañeda, A.; Rajsbaum, S. New combinatorial topology bounds for renaming: The upper bound. J. ACM 2012, 59, 3. [Google Scholar] [CrossRef]
Abraham, I.; Dolev, D. Byzantine agreement with optimal early stopping, optimal resilience and polynomial complexity. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, Portland, OR, USA, 14–17 June 2015; pp. 605–614. [Google Scholar]
Attiya, H.; Guerraoui, R.; Hendler, D.; Kuznetsov, P. The complexity of obstruction-free implementations. J. ACM 2009, 56, 24:1–24:33. [Google Scholar] [CrossRef]
Galil, Z.; Mayer, A.J.; Yung, M. Resolving message complexity of byzantine agreement and beyond. In Proceedings of the 36th Annual Symposium on Foundations of Computer Science, Milwaukee, WN, USA, 23–25 October 1995; pp. 724–733. [Google Scholar]
Georgiou, C.; Russell, A.; Shvartsman, A.A. The complexity of synchronous iterative do-all with crashes. Distributed Comput. 2004, 17, 47–63. [Google Scholar] [CrossRef] [Green Version]
Helmi, M.; Higham, L.; Pacheco, E.; Woelfel, P. The space complexity of long-lived and one-shot timestamp implementations. J. ACM 2014, 61, 7. [Google Scholar] [CrossRef]
Hoest, G.; Shavit, N. Toward a topological characterization of asynchronous complexity. SIAM J. Comput. 2006, 36, 457–497. [Google Scholar] [CrossRef]
Chordia, S.; Rajamani, S.K.; Rajan, K.; Ramalingam, G.; Vaswani, K. Asynchronous Resilient Linearizability. In Distributed Computing, Proceedings of the 27th International Symposium, DISC 2013, Jerusalem, Israel, 14–18 October 2013; Lecture Notes in Computer Science; Afek, Y., Ed.; Springer: Berlin/Heidelberg, Germany, 2013; Volume 8205, pp. 164–178. [Google Scholar]
Choudhury, A.; Patra, A. Optimally Resilient Asynchronous MPC with Linear Communication Complexit. In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN 2015, Goa, India, 4–7 January 2015; Das, S.K., Krishnaswamy, D., Karkar, S., Korman, A., Kumar, M.J., Portmann, M., Sastry, S., Eds.; ACM: New York, NY, USA, 2015; p. 5. [Google Scholar]
Vikram, S.; Herlihy, M.; Gafni, E. Asynchronous Computability Theorems for t-Resilient Systems. In Distributed Computing, Proceedings of the 30th International Symposium, DISC 2016, Paris, France, 27–29 September 2016; Lecture Notes in Computer Science; Cyril, G., David, I., Eds.; Springer: Berlin/Heidelberg, Germany; Volume 9888, pp. 428–441.
Kozlov, D.N. Combinatorial Algebraic Topology; Algorithms and Computation in Mathematics; Springer: Berlin/Heidelberg, Germany, 2008; Volume 21. [Google Scholar]
Munkres, J.R. Elements of Algebraic Topology; Addision-Wesley: Reading, MA, USA, 1984. [Google Scholar]
Delporte, C.; Fauconnier, H.; Rajsbaum, S.; Raynal, M. t-resilient immediate snapshot is impossible. In Structural Information and Communication Complexity, Proceedings of the 23rd International Colloquium, SIROCCO 2016, Helsinki, Finland, 19–21 July 2016; Revised Selected Papers; Lecture Notes in Computer Science; Jukka, S., Ed.; Springer: Berlin/Heidelberg, Germany, 2016; pp. 177–191. [Google Scholar]
Borowsky, E.; Gafni, E. A simple algorithmically reasoned characterization of wait-free computations (extended abstract). In Proceedings of the Sixteenth Annual ACM Symposium on Principles of Distributed Computing, Santa Barbara, CA, USA, 21–24 August 1997; pp. 189–198. [Google Scholar]
Herlihy, M.; Rajsbaum, S. Concurrent computing and shellable complexes. In Proceedings of the Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, 13–15 September 2010; pp. 109–123. [Google Scholar]
Kozlov, D.N.; Shavit, N. Combinatorial topology of the standard chromatic subdivision and weak symmetry breaking for 6 processes. CoRR 2015, abs/1506.03944. [Google Scholar]
Herlihy, M.; Shavit, N. The topological structure of asynchronous computability. J. ACM 1999, 46, 858–923. [Google Scholar] [CrossRef]
Herlihy, M.; Kozlov, D.N.; Rajsbaum, S. Distributed Computing through Combinatorial Topology, 1st ed.; Morgan Kaufmann: San Francisco, CA, USA, 2013. [Google Scholar]
Fajstrup, L.; Raußen, M.; Goubault, E. Algebraic topology and concurrency. Theor. Comput. Sci. 2006, 357, 241–278. [Google Scholar] [CrossRef] [Green Version]

Figure 1. The star of

v_{0}

in complex

K

Figure 1. The star of

v_{0}

in complex

K

Figure 2. Once standard chromatic and general chromatic subdivision of 2-simplex

α

Figure 2. Once standard chromatic and general chromatic subdivision of 2-simplex

α

Figure 3.

C

-extended and

C

-neighborhood.

Figure 3.

C

-extended and

C

-neighborhood.

Figure 4. Execution for three processes with input simplex

I^{2}

Figure 4. Execution for three processes with input simplex

I^{2}

Figure 5. An intuitive procedure of 2-simplex

I^{2}

to some reduced delayed complex.

Figure 5. An intuitive procedure of 2-simplex

I^{2}

to some reduced delayed complex.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

© 2022 by the authors. Licensee MDPI, Basel, Switzerland. This article is an open access article distributed under the terms and conditions of the Creative Commons Attribution (CC BY) license (https://creativecommons.org/licenses/by/4.0/).

Share and Cite

MDPI and ACS Style

Yue, Y.; Liu, X.; Lei, F.; Wu, J. A Topological Characterization to Arbitrary Resilient Asynchronous Complexity. Mathematics 2022, 10, 2720. https://doi.org/10.3390/math10152720

AMA Style

Yue Y, Liu X, Lei F, Wu J. A Topological Characterization to Arbitrary Resilient Asynchronous Complexity. Mathematics. 2022; 10(15):2720. https://doi.org/10.3390/math10152720

Chicago/Turabian Style

Yue, Yunguang, Xingwu Liu, Fengchun Lei, and Jie Wu. 2022. "A Topological Characterization to Arbitrary Resilient Asynchronous Complexity" Mathematics 10, no. 15: 2720. https://doi.org/10.3390/math10152720

APA Style

Yue, Y., Liu, X., Lei, F., & Wu, J. (2022). A Topological Characterization to Arbitrary Resilient Asynchronous Complexity. Mathematics, 10(15), 2720. https://doi.org/10.3390/math10152720

Note that from the first issue of 2016, this journal uses article numbers instead of page numbers. See further details here.

Article Menu

A Topological Characterization to Arbitrary Resilient Asynchronous Complexity

Abstract

1. Introduction

2. Preliminaries

2.1. Basic Concepts of Combinatorial Topology

2.2. Distributed Computing Model

2.3. Topological Task Specification

3. The Topological Description of $IDM$

3.1. Delayed Complexes

3.2. The Characterization of $IDM$

4. Measure Complexity

4.1. Complexity of the Delayed Model

4.2. Reduced Delayed Complex

4.3. Arbitrary Resilient Asynchronous Complexity Theorem

5. Application

6. Conclusions and Future Work

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

Abbreviations

Appendix A. Delayed Algorithm

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

Article Menu

A Topological Characterization to Arbitrary Resilient Asynchronous Complexity

Abstract

1. Introduction

2. Preliminaries

2.1. Basic Concepts of Combinatorial Topology

2.2. Distributed Computing Model

2.3. Topological Task Specification

3. The Topological Description of IDM

3.1. Delayed Complexes

3.2. The Characterization of IDM

4. Measure Complexity

4.1. Complexity of the Delayed Model

4.2. Reduced Delayed Complex

4.3. Arbitrary Resilient Asynchronous Complexity Theorem

5. Application

6. Conclusions and Future Work

Author Contributions

Funding

Institutional Review Board Statement

Informed Consent Statement

Data Availability Statement

Conflicts of Interest

Abbreviations

Appendix A. Delayed Algorithm

References

Share and Cite

Article Metrics

Article Access Statistics

Further Information

Guidelines

MDPI Initiatives

Follow MDPI

3. The Topological Description of $IDM$

3.2. The Characterization of $IDM$