Dynamic asynchronous iterations

Matthew L. Daggitt Timothy G. Griffin Department of Computer Science and Technology, University of Cambridge, UK

Abstract

Many problems can be solved by iteration by multiple participants (processors, servers, routers etc.). Previous mathematical models for such asynchronous iterations assume a single function being iterated by a fixed set of participants. We will call such iterations static since the system’s configuration does not change. However in several real-world examples, such as inter-domain routing, both the function being iterated and the set of participants change frequently while the system continues to function. In this paper we extend Üresin & Dubois’s work on static iterations to develop a model for this class of dynamic or always on asynchronous iterations. We explore what it means for such an iteration to be implemented correctly, and then prove two different conditions on the set of iterated functions that guarantee the full asynchronous iteration satisfies this new definition of correctness. These results have been formalised in Agda and the resulting library is publicly available.

keywords:

Asynchronous computation, Iteration, Fixed points, Formal verification, Agda

1 Introduction

Let $S$ be a set. Iterative algorithms aim to find a fixed point $x^{*}$ for some function ${F:S\rightarrow S}$ by starting from an initial state $x\in S$ and calculating the sequence:

x,\ F(x),\ F^{2}(x),F^{3}(x),\ ...

If a number of iterations $k^{*}$ is found such that $F^{k^{*}}(x)=F^{k^{*}+1}(x)$ then $F^{k^{*}}(x)$ is a fixed point $x^{*}$ . Whether or not there exists such a $k^{*}$ depends on both the properties of the iterated function $F$ and the initial state chosen $x$ . It should be noted that this paper is only interested in functions $F$ which converge to a unique fixed point, i.e. the same $x^{*}$ is reached no matter which initial state $x$ the iteration starts from.

In a distributed version of the iteration, both the set $S$ and the function $F$ are assumed to be decomposable into $n$ parts:

	$\displaystyle S$	$\displaystyle=S_{1}\times S_{2}\times...\times S_{n}$
	$\displaystyle F$	$\displaystyle=(F_{1},F_{2},...,F_{n})$

where $F_{i}:S\rightarrow S_{i}$ computes the $i^{th}$ component of the new state. Each node $i$ repeatedly iterates $F_{i}$ on its local view of the current state of the iteration, and propagates its stream of updated values to other nodes so that they may incorporate them in their own iteration. In an asynchronous distributed iteration, the timings between nodes are not actively synchronised. A formal model, $\delta$ , for such an asynchronous iteration is described in Section 2.

Frommer & Syzld [1] provide a survey of the literature describing when such asynchronous iterations are guaranteed to converge to a unique fixed point. One of the unifying features of these results is that they only require conditions on the function $F$ and hence users may prove an asynchronous iteration converges without ever directly reasoning about unreliable communication or asynchronous event orderings. Applications of these results include routing [2, 3, 4], programming language design [5], peer-to-peer protocols [6], and numerical simulations [7]. Other recent applications of asynchronous iterations include [8, 9, 10], while [11] and [12] provide useful surveys of asynchronous iterations in general.

However there are two main drawbacks to the models used in the current literature. Firstly, they assume the set of participating nodes remains constant over time. While this may be reasonable when modelling an iterative process run on a multi-core computer, it is unrealistic when reasoning about truly distributed “always on” protocols such as routing and consensus algorithms. For example the global Border Gateway Protocol that coordinates routing in the internet has been “on” since the early 1990’s and has grown from a few dozen routers to millions. During that time the set of participating routers has been completely replaced many times over. The second problem is that the models assume that the function $F$ being iterated remains constant over time. This may not be the case if it depends on some process external to the iteration (e.g. link latencies in routing) or on the set of participants (e.g. resource allocation/consensus/routing algorithms).

This paper will therefore use the term static to refer to the asynchronous iterations previously described in the literature and dynamic to refer to this new class of asynchronous iterations in which the set of participating nodes and function being iterated may change over time.

When applying the results in the literature to always-on algorithms, it is common for prior work to either informally argue or implicitly assume that the correctness of a dynamic iteration is an immediate consequence of the correctness of a infinite sequence of suitable static iterations. This line of reasoning is:

•

implicitly argued in Section 4.2 of [2].
•

explicitly argued in Section 3.2 of [3].
•

implicitly argued in Section 2.4 of [4].
•

discussed and implicitly argued in point (b) of Section 5 in [13].

The reasoning runs that a dynamic iteration is really a sequence of static iterations, where each new static iteration starts from the final state of the previous static iteration. However this argument is incorrect, as it does not take into account that messages may be shared between the different static iterations in the sequence. For example if node 1 fails, it may still have messages in flight that node 2 will receive in the next static iteration. Not only may this message prevent convergence in the next iteration, the model in the existing literature has no way of even representing messages arriving from nodes that are not participating during the current static iteration.

This paper therefore proposes a new, more general model that can be used to reason about dynamic iterations over both continuous and discrete data. Section 2 of the paper describes one of the most commonly used static models, and discusses some of the surrounding literature. Section 3 then presents our new generalised model for dynamic iterations, and discusses what it means for a dynamic iteration to be “correct”. Next, Section 4 proves two different conditions for a dynamic asynchronous iteration to satisfy this definition of correctness. Importantly, and as with the previous static results of Üresin & Dubois, these conditions only constrain the synchronous behaviour of the dynamic system. This means that users of our theorems can prove the correctness of their asynchronous algorithms by purely synchronous reasoning. Section 5 then briefly describes the formalisation of the results in Agda and their application to inter-domain routing protocols. Finally, Section 6 discusses our concluding thoughts and possible directions for future work.

2 Static asynchronous iterations

2.1 Model

A mathematical model for static asynchronous iterations was standardised by work in the 1970s and 80s [13, 14, 15]. The notation and terminology used here is taken from the recent paper [16] which in turn is based on that used by Üresin & Dubois [17].

Assume that the set of times $T$ is a discrete linear order. Each point in time marks the occurrence of events of interest: for example a node computing an update or a message arriving at a node. The set of times can be represented by $\mathbb{N}$ but for notational clarity $T$ will be used. Additionally let $V=\{1,2,...,n\}$ be the set of nodes that are participating in the computation.

Definition 1 (Static schedule).

A static schedule consists of a pair of functions:

•

$\alpha:T\rightarrow 2^{V}$ , the activation function, where $\alpha(t)$ is the set of nodes which activate at time $t$ .
•

$\beta:T\times V\times V\rightarrow T$ , the data flow function, where $\beta(t,i,j)$ is the time at which the latest message node $i$ has received from node $j$ at time $t$ was sent by node $j$ .

such that:

(SS1)

$\forall i,j,t:\>\beta(t+1,i,j)\leq t$

The function $\alpha$ describes when nodes update their values, and the function $\beta$ tracks how the resulting information moves between nodes. Assumption (SS1) enforces causality by stating that information may only flow forward in time. Note that this definition does not forbid the data flow function $\beta$ from delaying, losing, reordering or even duplicating messages (see Figure 1). Prior to recent work [16], static schedules were assumed to have two additional assumptions that guaranteed every node continued to activate indefinitely and that every pair of nodes continued to communicate indefinitely.

Figure 1: Behaviour of the data flow function

\beta

. Messages from node

j

to node

i

may be reordered, lost or even duplicated. The only constraint is that every message must arrive after it was sent. Reproduced from [16]

Definition 2 (Static asynchronous state function).

Given a static schedule $(\alpha,\beta)$ the static asynchronous state function, $\delta:T\rightarrow S\rightarrow S$ , is defined as follows:

\displaystyle\delta^{t}_{i}(x)

\displaystyle=\begin{cases}x_{i}&\text{if $t=0$}\\ \delta^{t-1}_{i}(x)&\text{else if $i\notin\alpha(t)$}\\ F_{i}(\delta^{\beta(t,i,1)}_{1}(x),\delta^{\beta(t,i,2)}_{2}(x),...,\delta^{\beta(t,i,n)}_{n}(x))&\text{otherwise}\end{cases}

where $\delta^{t}_{i}(x)$ is the state of node $i$ at time $t$ when starting from state $x$ .

At time $0$ the iteration is in the initial state $x$ . At subsequent times $t$ if node $i$ is not in the set of active nodes then its state remains unchanged. Otherwise if node $i$ is in the active set of nodes it applies its update function $F_{i}$ to its current view of the global state. For example $\delta^{\beta(t,i,1)}_{1}(x)$ is the state of node $1$ at the time of departure of the most recent message node $i$ has received from node $1$ at time $t$ .

2.2 Correctness

In order to precisely define when an asynchronous iteration is expected to converge, it is first necessary to discuss what sort of schedules allow an asynchronous iteration to make progress. As mentioned earlier, previous models made the simplifying assumption that every node activates an infinite number of times and every pair of nodes continue to communicate indefinitely. This essentially says that the schedule is well-behaved forever. In contrast [16] built upon the work of Üresin & Dubois and their concept of pseudocycles and relaxed this condition to only require that schedules must be well-behaved for a finite period of time. This distinction will be important in the dynamic model described later in Section 3, as a dynamic iteration will only have a finite period of time to converge before either the participants or the function being iterated changes.

Definition 3 (Static activation period).

A period of time $[t_{1},t_{2}]$ is an activation period for node $i$ if there exists a time $t\in[t_{1},t_{2}]$ such that $i\in\alpha(t)$ .

Definition 4 (Static expiry period).

A period of time $[t_{1},t_{2}]$ is an expiry period for node $i$ if for all nodes $j$ and times $t\geq t_{2}$ then $t_{1}\leq\beta(t,i,j)$ .

Therefore after an activation period node $i$ is guaranteed to activate at least once. In contrast after an expiry period the node is guaranteed to use only data generated after the start of the expiry period. In other words, all messages in flight to node $i$ at time $t_{1}$ have either arrived or been lost by time $t_{2}$ .

Definition 5 (Static pseudocycle).

A period of time $[t_{1},t_{2}]$ is a pseudocycle if for all nodes $i$ there exists a time $t\in[t_{1},t_{2}]$ such that $[t_{1},t]$ is an expiry period for node $i$ and $[t,t_{2}]$ is an activation period for node $i$ .

The term “pseudocycle” refers to the fact that during such a period of time the asynchronous iteration will make at least as much progress as that of a single step of the synchronous iteration. This statement will be made formal later on by Lemma 8 in Section 4.1. When we informally say that a period of time contains $k$ pseudocycles, we implicitly mean $k$ disjoint pseudocycles.

Using the definition of a pseudocycle, it is now possible to define what it means for an asynchronous iteration to converge for schedules that are only well-behaved for a finite amount of time.

Definition 6 (Static convergence).

The static asynchronous iteration converges over a set of initial states ${X=X_{1}\times X_{2}\times\ldots\times X_{n}}\subseteq S$ if:

1.

there exists a fixed point $x^{*}$ for $F$ and a number of iterations $k^{*}$ .
2.

for every starting state $x\in X$ and schedule containing at least $k^{*}$ pseudocycles then there exists a time $t_{1}$ such that for all $t_{2}\geq t_{1}$ then $\delta^{t_{2}}(x)=x^{*}$ .

2.3 Results

The survey paper by Frommer & Syzld [1] provides an overview of the convergence results in the literature for this and other related models. Much of the work has been motivated by iterative algorithms in numerical analysis and consequently many of the proofs of convergence assume that the set $S$ is equipped with a dense ordering. Unfortunately in fields such as routing, consensus algorithms and others, the set $S$ is discrete, and so many of the more common results are inapplicable. However in the late 1980s Üresin & Dubois [17] came up with one of the first conditions for the convergence of discrete asynchronous iterations. Here we use the relaxed version of the conditions as proposed in [16].

Definition 7 (Static ACO).

A function $F$ is an asynchronously contracting operator (ACO) if there exists a sequence of sets $B(k)=B(k)_{1}\times B(k)_{2}\times...\times B(k)_{n}$ for $k\in\mathbb{N}$ such that:

(SA1)

$\forall x\in S:x\in B(0)\Rightarrow F(x)\in B(0)$ .
(SA2)

$\forall k\in\mathbb{N},x\in S:x\in B(k)\Rightarrow F(x)\in B(k+1)$ .
(SA3)

$\exists k^{*}\in\mathbb{N},x^{*}\in S:\forall k\in\mathbb{N}:k^{*}\leq k\Rightarrow B(k)=\{x^{*}\}$ .

Theorem 1.

If function $F$ is an ACO then $\delta$ converges deterministically over the set $B(0)$ .

Proof.

See [17] & [16]. ∎

The advantage of the ACO conditions is that they are independent of both $\delta$ and the schedule, and so proving that $\delta$ converges only requires reasoning about the function $F$ .

The conditions require that the state space $S$ can be divided into a series of nested boxes $B(k)$ where every application of $F$ moves the state into the next box, and eventually a box $B(k^{*})$ is reached that only contains a single element. See Figure 2 for a visualisation.

Figure 2: If

F

is an ACO then the space

S

can be divided up into a series of boxes

B

. Note that this figure is a simplification, as each set

B(k)

is decomposable into

B(k)_{1}\times...\times B(k)_{n}

and so in reality the diagram should be

n

dimensional.

The reason why these conditions guarantee asynchronous convergence, rather than merely synchronous convergence, is that each box must be decomposable over each of the $n$ nodes. Therefore the operator is always contracting even if every node hasn’t performed the same number of updates locally. Note that Theorem 1 only guarantees $\delta$ will converge from states in the initial set $B(0)$ . Hence $B(0)$ can be thought of as a basin of attraction [18].

In practice the set of boxes $B$ can be difficult and non-intuitive to construct, as they must be explicitly centered around the fixed point whose existence may not even be immediately obvious. Üresin & Dubois recognised this and provided several other stronger conditions that are sufficient to construct an ACO. An alternative set of equivalent conditions was originally described by Gurney [19]. As with the ACO conditions, these conditions were relaxed by [16] and the latter version is now presented.

Definition 8 (Static AMCO).

A function $F$ is an asynchronously metrically contracting operator (AMCO) if for every node $i$ there exists a distance function $d_{i}$ such that if $D(x,y)\triangleq\max_{i}d_{i}(x_{i},y_{i})$ then:

(SU1)

$\forall i\in V,x,y\in S:d_{i}(x,y)=0\Leftrightarrow x=y$
(SU2)

$\forall i\in V:\exists n\in\mathbb{N}:\forall x,y\in S:d_{i}(x,y)\leq n$
(SU3)

$\forall x\in S:x\neq F(x)\Rightarrow D(x,F(x))>D(F(x),F^{2}(x))$
(SU4)

$\forall x,x^{*}\in S:F(x^{*})=x^{*}\wedge x\neq x^{*}\Rightarrow D(x^{*},x)>D(x^{*},F(x))$
(SU5)

$S$ is non-empty

The AMCO conditions require the construction of a notion of distance between states such that there exists a maximum distance (SU2) and that successive iterations become both closer together (SU3) and closer to any fixed point (SU4). Note, unlike Gurney’s original formulation, the AMCO conditions as defined above do not require $d_{i}$ to obey the typical metric axioms of symmetry and the ultrametric triangle inequality.

Gurney [19] proves that the AMCO conditions are equivalent to the ACO conditions by constructing reductions in both directions. Consequently the following convergence theorem holds.

Theorem 2.

If $F$ is an AMCO then $\delta$ converges deterministically over the set $S$ .

Proof.

See [19] & [16]. ∎

2.4 Motivations for a dynamic model

As discussed in the introduction, prior work applying Üresin & Dubois’s results to “always-on” algorithms often assumes that dynamic iterations can be viewed as a sequence of static iterations. By inspecting the definition of $\delta$ , the flaw in this argument can now be formalised. Consider a dynamic iteration with nodes $V$ in which node $i\in V$ has sent out an update message to $j\in V$ and then $i$ ceases participating. The new static iteration would begin immediately with participants $V-\{i\}$ and therefore when $j$ next activates, the static model is incapable of receiving the message from node $i$ .

Another feature lacking in the static model is the ability to reboot nodes. It is possible to represent temporary node failure in the static model by excluding it from the set of active nodes, however this still provides an unsatisfactory model as many types of failure will result in a node’s state being erased (e.g. replacing a faulty server in a data centre). In reality after such an event the node is forced to revert back to the initial state. This “rebooting” of a node after a temporary failure cannot be described by the existing static model.

3 Dynamic asynchronous iterations

To overcome these shortcomings we now propose a new, more general model that can describe both dynamic and static iterations.

3.1 Model

Let $V$ be the set of all the nodes that participate at some point during the dynamic iteration. $V$ is still assumed to be finite with $n=|V|$ , as the only cases in which $|V|$ could be infinite is if either an infinite number of nodes participated at the same time or an infinite amount of time has passed since the iteration began. Neither case is useful in reality. As before, we assume there exists a product state space $S=S_{1}\times S_{2}\times..\times S_{n}$ .

In order to capture the new dynamic nature of the iteration we introduce the concept of an epoch. An epoch is a contiguous period of time in which both the function being iterated and the set of participating nodes remain constant. The set of epochs is denoted as $E$ but as with time can be assumed to be an alias for $\mathbb{N}$ .

Instead of a single function $F$ , we now assume that $F$ is a family of indexed functions where $F^{ep}$ is the function being computed in epoch $e\in E$ by participants $p\subseteq V$ . Furthermore we assume there exists a special non-participating state $\bot\in S$ .

A schedule must therefore not only track the activation of nodes and the flow of data between them but also the current epoch and the participating nodes. Given these requirements it is natural to redefine a schedule as follows:

Definition 9 (Dynamic schedule).

A dynamic schedule is a tuple of functions $(\alpha,\beta,\eta,\pi)$ where:

•

$\alpha:T\rightarrow 2^{V}$ is the activation function, where $\alpha(t)$ is the set of nodes which activate at time $t$ .
•

$\beta:T\times V\times V\rightarrow T$ is the data flow function, where $\beta(t,i,j)$ is the time at which the information used by node $i$ at time $t$ was sent by node $j$ .
•

$\eta:T\rightarrow E$ is the epoch function, where $\eta(t)$ is the epoch at time $t$ .
•

$\pi:E\rightarrow 2^{V}$ is the participants function, where $\pi(e)$ is the set of nodes participating in the computation during epoch $e$ .

such that:

(DS1)

$\forall i,j,t:\>\beta(t+1,i,j)\leq t$ – information only travels forward in time.
(DS2)

$\forall t_{1},t_{2}:\>t_{1}\leq t_{2}\Rightarrow\eta(t_{1})\leq\eta(t_{2})$ – the epoch number only increases.

The additional assumption (DS2) states that epochs are monotonically increasing. Although not technically required, the assumption is convenient as it ensures that for any two points in time in the same epoch then every point between them is also in the same epoch. This assumption does not reduce the expressive power of the model, as for any non-monotonic $\eta$ it is possible to find a suitable relabelling of epochs that recovers monotonicity. Another possible assumption that might be made is that a node can only activate if it is currently participating in the iteration (i.e. $\forall t:\alpha(t)\subseteq\pi(\eta(t))$ ). Although the assumption is reasonable, the dynamic asynchronous state function $\delta$ will be defined in such a way that it will not be required (see Definition 10).

Given a schedule, we define some additional notation for $\rho(t)$ , the set of nodes participating at time $t$ , and $F^{t}$ , the function being used at time $t$ :

	$\displaystyle\rho(t)$	$\displaystyle\triangleq\pi(\eta(t))$
	$\displaystyle F^{t}$	$\displaystyle\triangleq F^{\eta(t)\rho(t)}$

It is now possible to define the dynamic asynchronous state function as follows:

Definition 10 (Dynamic asynchronous state function).

Given an initial state $x$ and a schedule $(\alpha,\beta,\eta,\pi)$ the dynamic state function is defined as:

\delta^{t}_{i}(x)=\begin{cases}\bot_{i}&\text{if $i\notin\rho(t)$}\\ x_{i}&\text{else if $t=0$ or $i\notin\rho(t-1)$}\\ \delta^{t-1}_{i}(x)&\text{else if $i\notin\alpha(t)$}\\ F^{t}_{i}(\delta^{\beta(t,i,1)}_{1}(x),\ldots,\delta^{\beta(t,i,n)}_{n}(x))&\text{otherwise}\end{cases}

where $\delta^{t}_{i}(x)$ is the state of node $i$ at time $t$ starting from state $x$ .

If a node is not currently participating then it adopts its non-participating state. If it is participating at time $t$ but was not participating at the time $t-1$ then it must have just (re)joined the computation and it therefore adopts its initial state. If the node is a continuing participant and is inactive at time $t$ then its state remains unchanged. Otherwise, if it is active at time $t$ , it updates its state in accordance with the data received from the other nodes in the computation.

Note that in the latter case at time $t$ nodes can use data from any node in $V$ rather than just the current set of participants $\rho(t)$ . Hence nodes that are currently participating may end up processing messages from nodes that are no longer participating in the current epoch. Also note that this new model is a strict generalisation of the static model as the static definition of $\delta$ is immediately recovered by a schedule with the constant epoch and participants functions $\eta(t)=0$ and $\pi(0)=V$ .

3.2 Correctness

In order to define a notion of correctness for dynamic iterations, we first need to update the definition of a pseudocycle. It turns out that only two alterations are needed. The first is that the start and end of activation and expiry periods and consequently pseudocycles must belong to the same epoch. The second is that during a pseudocycle, only the participating nodes need to experience an activation and expiry period. An updated version of the definitions is given below with the changes underlined.

Definition 11 (Dynamic activation period).

A period of time $[t_{1},t_{2}]$ is a dynamic activation period for node $i$ if $\eta(t_{1})=\eta(t_{2})$ and there exists a time $t\in[t_{1},t_{2}]$ such that $i\in\alpha(t)$ .

Definition 12 (Dynamic expiry period).

A period of time $[t_{1},t_{2}]$ is(SU1) a dynamic expiry period for node $i$ if $\eta(t_{1})=\eta(t_{2})$ and for all nodes $j$ and times $t\geq t_{2}$ then $t_{1}\leq\beta(t,i,j)$ .

Definition 13 (Dynamic pseudocycle).

A period of time $[t_{1},t_{2}]$ is a dynamic pseudocycle if $\eta(t_{1})=\eta(t_{2})$ and for all nodes $i$ $\in\rho(t_{1})$ there exists a time $t\in[t_{1},t_{2}]$ such that $[t_{1},t]$ is an expiry period for node $i$ and $[t,t_{2}]$ is an activation period for node $i$ .

We can now start to think what it means for a dynamic iteration to be implemented correctly. Guaranteeing that a dynamic iteration will always converge to one particular fixed point is impossible as both the underlying computation and the participants may continue to change indefinitely. Furthermore the epoch durations may be short enough that no fixed point is ever reached, even temporarily. The natural and intuitive notion in such circumstances is to say that an iteration is convergent if whenever an epoch contains a sufficient number of pseudocycles then $\delta$ will converge to a fixed point for the remainder of that epoch. Furthermore within an epoch the fixed point reached should be unique, but different epochs may have different unique fixed points.

However, we would also like to be able to reason about for which epochs and sets of participants a dynamic iteration does not converge. For example in the case of inter-domain routing, it is known that path-vector protocols only converge if and only if the network topology is free [20]. Therefore, in the same way that we constrain convergence to some set of initial states, we also constrain convergence to some set of pairs of epochs and set of participants. We will refer to such pairs as configurations.

Definition 14 (Convergent iteration).

A dynamic asynchronous iteration is convergent over an initial set of states ${X=X_{1}\times X_{2}\times\ldots\times X_{n}}$ and a set of configurations $C\subseteq E\times 2^{V}$ iff:

1.

for every epoch and configuration $(e,p)\in C$ there exists a fixed point $x^{*}_{ep}$ for $F^{ep}$ and a number of iterations $k^{*}_{ep}$ .
2.

for every initial state $x\in X$ , schedule and time $t_{1}$ then if ${(\eta(t_{1}),\rho(t_{1}))\in C}$ and the time period $[t_{1},t_{2}]$ contains $k^{*}_{\eta(t_{1})\rho(t_{1})}$ pseudocycles then for every time $t_{3}$ such that $t_{3}\geq t_{2}$ and $\eta(t_{2})=\eta(t_{3})$ then $\delta^{t_{3}}(x)=x^{*}_{\eta(t_{1})\rho(t_{1})}$ .

Having now defined what we mean for a dynamic iteration to be correct, in the next section we generalise the static ACO and AMCO conditions described in Section 2.3 and prove analogous correctness theorems for them.

4 Results

Before we generalise the ACO and AMCO conditions, some additional definitions are needed. As would be expected, information from non-participating nodes that is still “in-flight” from a previous epoch may interfere with the convergence of $\delta$ in the current epoch. Therefore a notion is needed of a state only containing information for the current set of participants.

Definition 15 (Accordant states).

A state $x$ is accordant with respect to a set of participants $p$ if every inactive node is assigned the inactive state, i.e. $\forall i\notin p:x_{i}=\bot_{i}$ . The set of states that are accordant with $p$ is denoted as $A^{p}$ .

When in the dynamic world we also need to take more care about the properties of $X$ , the set of initial states which the iteration can converge from. The static ACO conditions in Definition 7 implicitly take the first box to be the set of initial states, i.e. $X=B(0)$ , whilst the static AMCO conditions implicitly assume any state is valid, i.e. $X=S$ . However, the former approach no longer works in the dynamic world as we are forced to have different sets of boxes for each epoch and set of participants, and the latter is unnecessarily restrictive, as some iterative algorithms may only converge when started from certain states.

In order to solve these problems, we now define the properties that the initial set must satisfy regardless of whether we’re using the ACO or AMCO conditions.

Definition 16 (Valid set of initial states).

An initial set $X=X_{1}\times X_{2}\times\ldots\times X_{n}$ is valid if:

(IS1)

$\bot\in X$
(IS2)

$\forall e,p,x:x\in X\Rightarrow F^{ep}(x)\in X$

Assumption (IS1) states that the non-participating state is in the initial set and (IS2) states that $X$ is closed over every operator. The latter is the counterpart of assumption (SA1) in the definition of a static ACO. Together these ensure that an asynchronous iteration never leaves the initial set (see Lemma 1 for details). Also note that the entire state space $S$ is trivially a valid initial set.

4.1 Dynamic ACO implies convergent

We can now define the dynamic counterpart of the static ACO conditions. While it might be tempting to simply require that every $F^{ep}$ be a static ACO, there are a couple of additional constraints necessary.

Definition 17 (Dynamic ACO).

The set of functions $F$ are a dynamic ACO over a set of initial states $X=X_{1}\times X_{2}\times\ldots\times X_{n}$ and set of configurations $C\subseteq E\times 2^{V}$ if for every epoch $e$ and set of participants $p$ such that $(e,p)\in C$ there exists a sequence of sets $B^{ep}(k)=B^{ep}_{1}(k)\times B^{ep}_{2}(k)\times...\times B^{ep}_{n}(k)$ for $k\in\mathbb{N}$ such that:

(DA1)

$X\subseteq B^{ep}(0)$
(DA2)

$\forall k\in\mathbb{N},i\notin p:\bot_{i}\in B^{ep}_{i}(k)$
(DA3)

$\forall k\in\mathbb{N},x\in X\cap A^{p}:x\in B^{ep}(k)\Rightarrow F^{ep}(x)\in B^{ep}(k+1)$
(DA4)

$\exists k^{*}_{ep}\in\mathbb{N},x^{*}_{ep}\in X:\forall k\in\mathbb{N}:k^{*}_{ep}\leq k\Rightarrow B^{ep}(k)=\{x^{*}_{ep}\}$

Assumption (DA1) is a new assumption that links the initial boxes of each epoch together by assuming that the initial set of states is a subset of the initial box. Assumption (DA2) is also new and ensures that the box for any non-participating node contains its non-participating state. Assumptions (DA3) & (DA4) are generalised versions of (SA2) & (SA3) respectively. The only difference is that (DA3) has been weakened so that applying $F^{ep}$ only advances a box when the state is accordant with the current set of participants. This means that progress need not be made in the case when stale messages are still being received from nodes that are no longer participating.

We now prove that if $F$ is a dynamic ACO over a valid set of initial states $X$ and configurations $C$ then $\delta$ is convergent over $X$ and $C$ . Going forwards the existence of some arbitrary schedule $(\alpha,\beta,\eta,\pi)$ and starting state $x\in X$ is assumed. As with $F^{t}\triangleq F^{\eta(t)\rho(t)}$ , we use the shorthand $B^{t}\triangleq B^{\eta(t)\rho(t)}$ and $c(t)\triangleq(\eta(t),\rho(t))$ so that the current boxes and configuration may be indexed by time rather than by epoch and participants. Initially some auxiliary definitions are introduced in order to improve the readability of the proof.

Definition 18.

The state of node $i$ is in box $k$ at time $t$ if:

c(t)\in C\Rightarrow\delta^{t}_{i}(x)\in B^{t}_{i}(k)

i.e. if the current configuration is in the set of valid configurations then the current state of node $i$ is in box $k$ .

Definition 19.

The messages to node $i$ are in box $k$ at time $t$ if:

c(t)\in C\Rightarrow\forall s:(s>t)\wedge(\eta(s)=\eta(t))\Rightarrow\forall j:\delta^{\beta(s,i,j)}_{j}(x)\in B^{t}_{j}(k)

i.e. if the current configuration is in the set of valid configurations then any message arriving at node $i$ after time $t$ and before the end of the current epoch is guaranteed to be in box $k$ . A different way of viewing this condition is that node $i$ ’s local view of the global state of the iteration will be in box $k$ for the remainder of the epoch.

Definition 20.

The messages to node $i$ are accordant at time $t$ if:

\forall s:(s>t)\wedge(\eta(s)=\eta(t))\Rightarrow\forall j:j\notin\rho(s)\Rightarrow\delta^{\beta(s,i,j)}_{j}=\bot_{j}

i.e. any message arriving at node $i$ after time $t$ during the current epoch from a non-participating node $j$ will always contain the non-participating state $\bot_{j}$ . This is equivalent to stating that node $i$ ’s local view of the state is accordant.

Definition 21.

The computation at node $i$ is in box $k$ at time $t$ if:

1.

the state of node $i$ is in box $k$ at time $t$ .
2.

if $k>0$ the messages to node $i$ are in box $k-1$ at time $t$ .
3.

if $k>0$ then the messages to node $i$ are accordant at time $t$ .

This definition collects together the pre-conditions required to prove that the state of node $i$ will always be in box $k$ for the remainder of the epoch, as shown in Lemma 4. Finally we lift this definition from an individual node to the whole computation as follows:

Definition 22.

The computation is in box $k$ at time $t$ if for all nodes $i\in\rho(t)$ then the computation at node $i$ is in box $k$ at time $t$ .

It is interesting to note that Definition 22 does not place any requirements on non-participating nodes. This is because, by the definition of $\delta$ , any non-participating node $i$ is always in the non-participating state $\bot_{i}$ , which, by assumption (DA2), is in every one of the boxes, including the final one. Also note that all of the above definitions contain some linguistic slight of hand, as being in box $k$ at time $t$ and being in box $k$ at time $t+1$ , does not necessarily refer to the same box if $\eta(t)\neq\eta(t+1)$ .

The proof can now be split into four parts. The first set of closure lemmas prove that the computation is always in box 0 even after changes in the epoch. The second set of stability lemmas describe under what conditions after the computation reaches box $k$ it remains in that box for the remainder of the epoch. The third set of progress lemmas demonstrate how during a pseudocycle the entire computation advances at least one box. Finally these results are combined to prove convergence.

4.1.1 Closure lemmas

In order to later apply the other ACO assumptions, we first establish that the initial set $X$ is closed over $\delta$ , i.e. that the iteration never escapes the initial set. As a consequence of this and assumption (DA1), we then prove that both the state and the computation are always in the box 0 of the current epoch.

Lemma 1.

For any $x\in X$ and time $t$ then $\delta^{t}(x)\in X$ .

Proof.

Consider an arbitrary node $i$ . The proof that $\delta^{t}_{i}(x)\in X_{i}$ proceeds by induction over the definition of $\delta$ .

Case 1: $i\notin\rho(t)$
Then $\delta^{t}_{i}(x)=\bot_{i}$ and $\bot_{i}\in X_{i}$ by assumption (IS1).

Case 2: $i\in\rho(t)$ and ( $t=0$ or $i\notin\rho(t-1)$ )
Then $\delta^{t}_{i}(x)=x_{i}$ and $x_{i}\in X_{i}$ by the initial assumption.

Case 3: $i\in\rho(t)$ and $i\in\rho(t-1)$ and $i\notin\alpha(t_{2})$
Then $\delta^{t}_{i}(x)=\delta^{t-1}_{i}(x)$ , and $\delta^{t-1}_{i}(x)\in X_{i}$ by the inductive hypothesis applied to time $t-1$ .

Case 4: $i\in\rho(t)$ and $i\in\rho(t-1)$ and $i\in\alpha(t)$
Then $\delta^{t}_{i}(x)=F^{t}_{i}(\delta^{\beta(t,i,1)}_{1}(x),\ldots,\delta^{\beta(t,i,n)}_{n}(x))$ . For each $j$ then $\delta^{\beta(t,i,j)}_{j}(x)\in X_{j}$ by the inductive hypothesis applied to time $\beta(t,i,j)$ . Hence $F^{t}_{i}(...)\in X_{i}$ as $X$ is closed under $F^{t}$ by assumption (IS2) . ∎

Lemma 2.

For every time $t$ and node $i$ the state of node $i$ is in box $0$ at time $t$ .

Proof.

Consider an arbitrary time $t$ and node $i$ such that $c(t)\in C$ . Then $\delta^{t}_{i}(x)\in X_{i}$ by Lemma 1 and $X_{i}\subseteq B^{t}_{i}(0)$ by assumption (DA1). ∎

Lemma 3.

For every time $t$ and node $i$ the computation at node $i$ is in box $0$ at time $t$ .

Proof.

The state of node $i$ is in box $0$ at time $t$ by Lemma 2. As we are only considering box 0, Definition 21 does not require us to prove that the messages to node $i$ are in box 0 and are accordant at time $t$ ¹¹1Note that the latter isn’t even true as out-of-date messages may still be arriving from nodes that were participating in a previous epoch but are no longer participating in the current epoch.. ∎

4.1.2 Stability lemmas

Guaranteeing that the dynamic iteration makes progress towards the fixed point of the current epoch is complicated by the fact that out-of-date messages may arrive from earlier in the iteration and undo recent progress. The next lemmas establish what conditions are necessary to guarantee that once the state and messages are in box $k$ then they will remain in box $k$ for the remainder of the epoch.

Lemma 4.

If the computation at node $i$ is in box $k$ at time $t$ then the state of node $i$ is in box $k$ for every time $s\geq t$ such that $\eta(s)=\eta(t)$ .

Proof.

Assume that the computation at node $i$ is box $k$ at time $t$ for an arbitrary node $i$ and time $t$ . We must show that $\delta^{s}_{i}(x)\in B^{s}_{i}(k)$ for any $s\geq t$ such that $c(s)\in C$ . If $k=0$ then the result follows immediately by Lemma 2. Otherwise if $k>0$ the proof proceeds by induction over time $s$ and the definition of $\delta$ . If $s=t$ then the state of node $i$ is in box $k$ at time $t$ by Definition 21. Otherwise $s>t$ and as $s-1\in[t,s]$ and $\eta(t)=\eta(s)$ then $\eta(t)=\eta(s-1)=\eta(s)$ and hence $B^{t}=B^{s-1}=B^{s}$ and $c(t),c(s-1)\in C$ . Consider the following cases:

Case 1: $i\notin\rho(s)$
Then $\delta^{s}_{i}(x)=\bot_{i}$ and $\bot_{i}\in B^{s}_{i}(k)$ by assumption (DA2).

Case 2: $i\in\rho(s)$ and $i\notin\rho(s-1)$
As $\eta(s-1)=\eta(s)$ then $\rho(s-1)=\rho(s)$ , contradicting the case assumptions.

Case 3: $i\in\rho(s)$ and $i\in\rho(s-1)$ and $i\notin\alpha(s)$
Then $\delta^{s}_{i}(x)=\delta^{s-1}_{i}(x)$ . As $c(s-1)\in C$ then we have $\delta^{s-1}_{i}(x)\in B^{s-1}_{i}(k)$ by the inductive hypothesis applied to time $s-1$ . As $B^{s-1}_{i}(k)=B^{s}_{i}(k)$ , we therefore have $\delta^{s}_{i}(x)\in B^{s}_{i}(k)$ .

Case 4: $i\in\rho(s)$ and $i\in\rho(s-1)$ and $i\in\alpha(s)$
Then $\delta^{s}_{i}(x)=F^{s}_{i}(\delta^{\beta(s,i,1)}_{1}(x),\ldots,\delta^{\beta(s,i,n)}_{n}(x))$ . As $c(t)\in C$ and all messages to node $i$ are in box $k-1$ at time $t$ and are accordant, then $\delta^{\beta(s,i,j)}_{j}(x)$ is accordant and in box $B^{t}_{j}(k-1)=B^{s}_{j}(k-1)$ for every node $j$ . Hence $F^{s}_{i}(...)\in B^{s}_{i}(k)$ by assumption (DA3). ∎

Lemma 5.

If messages to node $i$ are in box $k$ at time $t$ then the messages to node $i$ are in box $k$ for all times $s\geq t$ such that $\eta(s)=\eta(t)$ .

Proof.

Consider a time $r>s$ such that $\eta(r)=\eta(s)$ . We must show that $\delta^{\beta(r,i,j)}_{j}(x)\in B^{s}_{j}(k)$ for every node $j$ . Then $r>t$ and $\eta(r)=\eta(t)$ and so by Definition 19 we have that $\delta^{\beta}(r,i,j)(x)_{j}\in B^{t}_{j}(k)$ . As $\eta(s)=\eta(t)$ then $B^{s}=B^{t}$ and hence we have the required result. ∎

4.1.3 Progress lemmas

Having established that i) the computation is always in box 0 no matter the epoch and ii) once the computation at node $i$ has reached box $k$ , it remains in box $k$ , it is next necessary to establish when the computation advances a box during an epoch. These conditions are intimately tied to the notion of a pseudocycle.

Lemma 6.

If the messages to node $i$ are accordant and are in box $k$ at time $t$ and $[t,s]$ is an activation period then the state of node $i$ is in box $k+1$ at time $s$ .

Proof.

Assume $c(s)\in C$ . The proof that $\delta^{s}_{i}(x)\in B^{s}_{i}(k+1)$ proceeds by induction over the definition of $\delta$ and time $s$ . As activation periods are of non-zero length then $s>t$ and as $s-1\in[t,s]$ and $\eta(t)=\eta(s)$ then $B^{t}=B^{s-1}=B^{s}$ and $c(t),c(s-1)\in C$ . Consider the following cases:

Case 1: $i\notin\rho(s)$
Then $\delta^{s}_{i}(x)=\bot_{i}$ and $\bot_{i}\in B^{s}_{i}(k+1)$ by assumption (DA2).

Case 2: $i\in\rho(s)$ and $i\notin\rho(s-1)$
As $\eta(s-1)=\eta(s)$ then $\rho(s-1)=\rho(s)$ , contradicting the case assumptions.

Case 3: $i\in\rho(s)$ and $i\in\rho(s-1)$ and $i\notin\alpha(s)$
Then $\delta^{s}_{i}(x)=\delta^{s-1}_{i}(x)$ . If $s-1=t$ then the initial assumptions are contradicted as $i$ has not activated during the period $[t,s]$ . Otherwise if $s-1>t$ then $\delta^{s-1}_{i}(x)\in B^{s-1}_{i}(k+1)$ by applying the inductive hypothesis to time $s-1$ . As $B^{s-1}_{i}(k+1)=B^{s}_{i}(k+1)$ we have the required result.

Case 4: $i\in\rho(s)$ and $i\in\rho(s-1)$ and $i\in\alpha(s)$
Then $\delta^{s}_{i}(x)=F_{i}(\delta^{\beta(s,i,1)}_{1}(x),\ldots,\delta^{\beta(s,i,n)}_{n}(x))$ . As $c(t)\in C$ and all messages to node $i$ are in box $k$ at time $t$ and are accordant, then $\delta^{\beta(s,i,j)}_{j}(x)$ is accordant and in box $B^{t}_{j}(k)=B^{s}_{j}(k)$ for every node $j$ . Hence $F_{i}(...)\in B^{s}_{i}(k+1)$ by assumption (DA3). ∎

Lemma 7.

If the computation is in box $k$ at time $t$ and $[t,s]$ is an expiry period for node $i$ then the messages to node $i$ are in box $k$ at time $s$ .

Proof.

Assume that the computation is in box $k$ at time $t$ and consider two arbitrary nodes $i$ and $j$ and time $s$ such that $[t,s]$ is an expiry period and $c(s)\in C$ . We must show that for all times $r>s$ such that $\eta(s)=\eta(r)$ then $\delta^{\beta(r,i,j)}_{j}(x)\in B^{s}_{j}(k)$ . As $[t,s]$ is an expiry period then $t\leq\beta(r,i,j)<r$ and therefore $\eta(t)=\eta(\beta(r,i,j))=\eta(r)=\eta(s)$ . If $j\notin\rho(s)$ then $\delta^{\beta(r,i,j)}_{j}(x)=\bot_{j}$ and $\bot_{j}\in B^{s}_{j}(k)$ by assumption (DA2). Otherwise if $j\in\rho(s)$ then $\delta^{\beta(r,i,j)}_{j}(x)\in B^{\beta(r,i,j)}_{j}(k)$ by Lemma 4 applied to time period $[t,\beta(r,i,j)]$ and the fact that the computation at node $j$ is in box $k$ at time $t$ . The required result then follows as $B^{\beta(r,i,j)}=B^{s}$ by $\eta(\beta(r,i,j))=\eta(s)$ . ∎

Lemmas 6 & 7 prove that during activation and expiry periods the state and the messages are both guaranteed to advance at least one box. The next lemma combines them to prove that during a pseudocycle the whole computation advances at least one box, i.e. during a pseudocycle the asynchronous iteration makes at least as much progress as a single step of the synchronous iteration.

Lemma 8.

If the computation is in box $k$ at time $t$ and the period $[t,s]$ is a pseudocycle then the computation is in box $k+1$ at time $s$ .

Proof.

Consider an arbitrary node $i\in\rho(t)$ . As $[t,s]$ is a pseudocycle then as $i\in\rho(t)$ there exists a time $r$ such that $[t,r]$ is an expiry period for node $i$ and $[r,s]$ is an activation period for node $i$ .

•

As the messages to node $i$ are accordant at time $t$ then they are also accordant at times $r$ and $s$ .
•

As $[t,r]$ is an expiry period and the computation is in box $k$ at time $t$ , then the messages to node $i$ are in box $k$ at time $r$ by Lemma 7, and also therefore at time $s$ by Lemma 5.
•

As $[r,s]$ is an activation period and the messages to node $i$ are accordant and in box $k$ at time $r$ (by the previous two points) then the state of node $i$ in box $k+1$ at time $s$ by Lemma 6.

Consequently all three requirements for the computation at node $i$ being in box $k+1$ at time $s$ are fulfilled. ∎

4.1.4 Convergence

Now that Lemma 8 has established that during a pseudocycle the whole computation advances one box, the main theorem may be proved.

Theorem 3.

If $F$ is a dynamic ACO over a valid initial set $X$ and configurations $C$ then $\delta$ is convergent over $X$ and $C$ .

Proof.

To prove that $\delta$ is convergent it is first necessary to construct a fixed point $x^{*}_{ep}$ and iteration number $k^{*}_{ep}$ for every epoch $e$ and set of participants $p$ such that $(e,p)\in C$ . Let these be the $x^{*}_{ep}$ and $k^{*}_{ep}$ respectively as specified by assumption (DA4).

Next consider an arbitrary schedule, starting state $x\in X$ and starting time $t_{1}$ in epoch $e=\eta(t_{1})$ with participants $p=\rho(t_{1})$ such that $(e,p)\in C$ . We must show that for all times $t_{2}$ if $[t_{1},t_{2}]$ contains $k^{*}_{ep}$ pseudocycles then for all times $t_{3}$ such that $t_{3}\geq t_{2}$ and $\eta(t_{3})=\eta(t_{2})$ then $\delta^{t}_{3}(x)=x^{*}_{ep}$ .

The computation is always in box 0 by Lemma 3. Consequently after $k^{*}_{ep}$ pseudocycles, the computation is in box $k^{*}_{ep}$ at time $t_{2}$ by repeated application of Lemma 8. Hence for any subsequent time $t_{3}$ in epoch $e$ , then $\delta^{t_{3}}(x)\in B^{ep}(k^{*}_{ep})$ by Lemma 4 and, as $x^{*}_{ep}$ is the only state in $B^{ep}(k^{*}_{ep})$ by assumption (DA4), then $\delta^{t_{3}}(x)=x^{*}_{ep}$ . ∎

4.2 Dynamic AMCO implies convergent

Although the dynamic ACO conditions are sufficient to guarantee convergence, they can be a tricky to construct in practice. As discussed previously in Section 2.3, the AMCO conditions are often easier to work with. This section defines the dynamic AMCO conditions and shows that they also guarantee the iteration is convergent by constructing a reduction from the dynamic AMCO conditions to the dynamic ACO conditions.

Definition 23 (Dynamic AMCO).

The set of functions $F$ are a dynamic AMCO over a set of initial states $X=X_{1}\times X_{2}\times...\times X_{n}$ and a set of configurations $C\subseteq E\times 2^{V}$ if for every epoch $e$ and set of participants $p$ such that $(e,p)\in C$ and for every node $i\in V$ there exists a distance function $d^{ep}_{i}$ such that if $D^{ep}(x,y)\triangleq\max_{i\in p}\>d^{ep}_{i}(x,y)$ then:

(DU4)

$\forall i\in V:\forall x,y\in S:d^{ep}_{i}(x,y)=0\Leftrightarrow x=y$
(DU5)

$\forall i\in V:\exists n:\forall x,y\in S:d^{ep}(x,y)_{i}\leq n$
(DU6)

$\forall x{\in}X{\cap}A^{p}:F^{ep}(x)\neq x\Rightarrow D^{ep}(F^{ep}(x),(F^{ep})^{2}(x)){<}D^{ep}(x,F^{ep}(x))$
(DU7)

$\forall x{\in}X{\cap}A^{p},x^{*}{\in}S{:}F^{ep}(x^{*}){=}x^{*}\wedge x{\neq}x^{*}{\Rightarrow}D^{ep}(x^{*},F^{ep}(x)){<}D^{ep}(x^{*},x)$
(DU8)

$\forall x{\in}X{\cap}A^{p}:F^{ep}(x)\in A^{p}$ .

Again assumptions $(DU1)$ – $(DU4)$ are generalisations of $(SU1)$ – $(SU4)$ . The crucial difference is that everything is restricted to the set of participants: $F^{ep}$ need only be strictly contracting over accordant states $A^{p}$ , and the distance functions $D^{ep}$ are defined as the maximum over all participating states. Note that the static assumption (SU5) that $S$ is non-empty is not needed as the dynamic model assumes the existence of the non-participating state $\bot\in S$ . Instead the new assumption (DU8) ensures that the operator $F$ preserves accordant enforces that non-participating nodes adopt the non-participating state. This assumption was not stated explicitly in the dynamic ACO conditions but can be derived from assumptions (DA2) and (DA3).

The proof that these conditions imply that the iteration is convergent is a generalisation of the proof in [16] which in turn was based off the work in [19]. The main thrust of the reduction to the dynamic ACO conditions is relatively simple. As $F^{ep}$ is strictly contracting on orbits & its fixed points, it possesses a fixed point $x^{*}$ . As all distances are bounded above by some value, which we will call $k^{*}$ , the box $B^{ep}_{i}(k)$ can then be defined as the set of the states which are at a distance of no more than $k^{*}-k$ from $x^{*}_{i}$ . This is now fleshed out in more detail.

Theorem 4.

If $F$ is a dynamic AMCO then $F$ is a dynamic ACO.

Proof.

Consider an epoch $e$ and set of participants $p$ such that ${(e,p)\in C}$ . First we prove that $F^{ep}$ has a fixed point. We start by constructing the chain:

\bot,\ F^{ep}(\bot),\ (F^{ep})^{2}(\bot),\ (F^{ep})^{3}(\bot),\ ...

By assumption (DU8) and the fact $\bot$ is trivially accordant, then we have that every element in the chain is in $A^{p}$ . Similarly by assumptions (IS1) & (IS2) we have every element in the chain is in $X$ . Therefore while $(F^{ep})^{k}(\bot)\neq(F^{ep})^{k+1}(\bot)$ then by assumption (DU6) the distance between consecutive elements must strictly decrease:

D(\bot,F^{ep}(\bot))>D(F^{ep}(\bot),(F^{ep})^{2}(\bot))>D((F^{ep})^{2}(\bot),(F^{ep})^{3}(\bot))>...

As this is a decreasing chain in $\mathbb{N}$ it must eventually reach a $k$ such that $D(F^{k}(\bot),F^{k+1}(\bot))=0$ . Therefore $F^{k}(\bot)\neq F^{k+1}(\bot)$ by (DU4) and hence $x^{*}=F^{k}(\bot)$ is a fixed point and furthermore $x^{*}\in X$ and $x^{*}\in A^{p}$ .

By assumption (DU5) there exists an upper bound on the distance function $d_{i}^{ep}$ for all nodes $i$ , which we will denote as $k^{*}$ . Having established the existence of the fixed point $x^{*}$ and maximum distance $k^{*}$ , we can now define $i^{th}$ component for the $k^{th}$ box as follows:

B^{ep}_{i}(k)\triangleq\begin{cases}S_{i}&\text{if $k=0$}\\ \{\bot_{i}\}&\text{if $k\neq 0\wedge i\notin p$}\\ \{x_{i}\mid d_{i}(x_{i},x^{*}_{i})\leq\max(0,k^{*}-k)\}&\text{if $k\neq 0\wedge i\in p$}\end{cases}

We must now verify that the boxes $B^{ep}$ fulfil the conditions in Definition 17:

1.

(DA1) – $X\subseteq B^{ep}(0)$

Immediate from the first case of the definition of $B^{ep}$ .
2.

(DA2) – $\forall k\in\mathbb{N},i\notin p:\bot_{i}\in B^{ep}_{i}(k)$

Immediate from the first and second cases of the definition of $B^{ep}$ .

(DA3) – $\forall k\in\mathbb{N},x\in X\cap A^{p}:x\in B^{ep}(k)\Rightarrow F^{ep}(x)\in B^{ep}(k+1)$

Consider some state $x\in X\cap A^{p}$ and also assume that $x\in B^{ep}(k)$ . We must show that for all nodes $i$ then $F^{ep}_{i}(x)\in B^{ep}_{i}(k+1)$ .

If $i\notin p$ then $x_{i}=\bot_{i}$ by $x_{i}\in B^{ep}_{i}(k)$ , and hence $F^{ep}_{i}(x_{i})=\bot_{i}$ by assumption (DU8), and so $F^{ep}_{i}(x_{i})\in B_{i}(k+1)$ . Otherwise if $i\in p$ it remains to show that $d^{ep}_{i}(x^{*}_{i},F^{ep}_{i}(x))\leq\max(0,k^{*}-(k+1))$ .

If $x=x^{*}$ then:

$\displaystyle d^{ep}_{i}(x^{*}_{i},F^{ep}_{i}(x))$	$\displaystyle=d^{ep}_{i}(x^{}_{i},F^{ep}_{i}(x^{}))$	(as $x=x^{*}$ )
	$\displaystyle=d^{ep}_{i}(x^{}_{i},x^{}_{i})$	(as $F^{ep}(x^{})=x^{}$ )
	$\displaystyle=0$	(by (DU4))
	$\displaystyle\leq\max(0,k^{*}-(k+1))$

Otherwise if $x\neq x^{*}$ then $d^{ep}_{i}(x^{*}_{i},F^{ep}_{i}(x))<\max(0,k^{*}-k)$ as:

$\displaystyle d^{ep}_{i}(x^{*}_{i},F^{ep}_{i}(x))$	$\displaystyle\leq D^{ep}(x^{*},F^{ep}(x))$	(by definition of $D$ )
	$\displaystyle<D^{ep}(x^{*},x)$	(by (DU7) & (DU8))
	$\displaystyle\leq\max(0,k^{*}-k)$	(by $x\in B(k)$ )

which implies that $d^{ep}_{i}(x^{*}_{i},F^{ep}_{i}(x))\leq\max(0,k^{*}-(k+1))$ .

(DA4) – $\exists k^{*},x^{*}:\forall k:k^{*}\leq k\Rightarrow B(k)=\{x^{*}\}$

We have already established the existence of $k^{*}$ and $x^{*}$ . Consider a $k\geq k^{*}$ . If $k=0$ then $k^{*}=0$ and so the result holds trivially as $x^{*}\in S$ and all points are 0 distance away from and hence equal to $x^{*}$ by (DU4) & (DU5). Otherwise if $k\neq 0$ then as $k\geq k^{*}$ the definition of $B^{ep}(k)$ simplifies to:

B^{ep}_{i}(k)\triangleq\begin{cases}\{\bot_{i}\}&\text{if $i\notin p$}\\ \{x_{i}\mid d^{ep}_{i}(x_{i},x^{*}_{i})=0\}&\text{if $i\in p$}\end{cases}

To prove that $x^{*}\in B^{ep}(k)$ we must show that for every node $i$ we have $x^{*}_{i}\in B^{ep}_{i}(k)$ . This follows as if $i\notin p$ then as $x^{*}_{i}=\bot_{i}$ as $x^{*}\in A^{p}$ . Otherwise if $i\in p$ then $d^{ep}(x^{*}_{i},x^{*}_{i})=0$ by (DU4).

Suppose there exists another state $x\in B^{ep}(k)$ . We must show that for every node $i$ we have that $x_{i}=x^{*}_{i}$ . If $i\notin p$ then $x_{i}\in B^{ep}_{i}(k)$ implies $x_{i}=\bot_{i}$ and $\bot_{i}=x^{*}_{i}$ as $x^{*}\in A^{p}$ . Otherwise if $i\in p$ then $x_{i}\in B^{ep}_{i}(k)$ implies $d^{ep}(x_{i},x^{*}_{i})=0$ . Hence $x_{i}=x^{*}_{i}$ by (DU4).

Hence the conditions are satisfied and $F$ is a dynamic ACO. ∎

Theorem 5.

If $F$ satisfies the dynamic AMCO conditions then $\delta$ is convergent.

Proof.

As $F$ is a dynamic AMCO then $F$ is a dynamic ACO by Theorem 3. Hence $\delta$ is convergent by Theorem 4. ∎

5 Formalisation in Agda

Every result presented in this paper have been formalised in Agda [21], a dependently typed language that is expressive enough that both programs and proofs may be written in it. The results cover not only the dynamic model but also include the previous static model as well. The proofs are available online [22] as an Agda library and the library’s documentation contains a guide to definitions and proofs to the corresponding Agda code.

It is hoped that the library may be of use to others in constructing formal proofs of correctness for a variety of asynchronous algorithms. The library is designed in a modular fashion so that users need not be aware of the underlying details. The library has already been used to generalise and formally verify the correctness conditions for inter-domain routing protocols with complex conditional policy languages found in [3].

6 Conclusion

This paper has successfully constructed a more general model for dynamic asynchronous iterations in which both the computation and the set of participants may change over time. It has generalised the ACO and AMCO conditions for the existing static model and shown that the generalisations are sufficient to guarantee the correctness of the dynamic model.

Although we have not directly explored any uses of these results in this paper, we refer interested readers to [23] which contains an in-depth case study of how they may be applied to prove new theoretical results about the Bellman-Ford family of routing protocols.

There are still several open questions in regards to the theory of asynchronous iterations. For example, even in the static model questions remain about what are necessary conditions for $\delta$ to converge. Üresin & Dubois [17] showed that when $S$ is finite then the ACO conditions are both necessary and sufficient for convergence. As far as the authors are aware there exist no such corresponding conditions for the case when $S$ is infinite.

Another obvious question is whether the dynamic ACO conditions are also necessary for the convergence of the dynamic model when $S$ is finite. Üresin & Dubois’s static proof is essentially combinatorial in nature, building the ACO boxes $B$ such that they contain all possible states that can result from static schedules. The challenges to adapting this to the dynamic model are twofold: firstly the additional combinatorial explosion of possible states introduced by the epochs, and secondly the absence in the definition of a dynamic schedule of Üresin & Dubois’s assumption that the schedules must contain an infinite number of pseudoperiods.

Acknowledgements

Matthew L. Daggitt was supported by an EPSRC Doctoral Training grant.

References

[1] A. Frommer, D. B. Szyld, On asynchronous iterations, Journal of computational and applied mathematics 123 (1) (2000) 201–216 (2000).
[2] C.-k. Chau, Policy-based routing with non-strict preferences, SIGCOMM Computer Communication Review 36 (4) (2006) 387–398 (Aug. 2006). doi:10.1145/1151659.1159957.
[3] M. L. Daggitt, A. J. T. Gurney, T. G. Griffin, Asynchronous convergence of policy-rich distributed Bellman-Ford routing protocols, in: SIGCOMM proceedings, ACM, 2018 (2018).
[4] B. Ducourthial, S. Tixeuil, Self-stabilization with path algebra, Theoretical Computer Science 293 (1) (2003) 219 – 236 (2003). doi:https://doi.org/10.1016/S0304-3975(02)00238-4.
[5] S. A. Edwards, E. A. Lee, The semantics and execution of a synchronous block-diagram language, Science of Computer Programming 48 (1) (2003) 21 – 42 (2003). doi:https://doi.org/10.1016/S0167-6423(02)00096-5.
[6] S. Y. Ko, I. Gupta, Y. Jo, A new class of nature-inspired algorithms for self-adaptive peer-to-peer computing, ACM Transactions on Autonomous and Adaptive Systems 3 (3) (2008) 11:1–11:34 (Aug. 2008). doi:10.1145/1380422.1380426.
[7] M. Chau, Algorithmes parallèles asynchrones pour la simulation numérique, Ph.D. thesis, Institut National Polytechnique de Toulouse (2005).
[8] J. Wolfson-Pou, E. Chow, Modeling the asynchronous Jacobi method without communication delays, Journal of Parallel and Distributed Computing 128 (2019) 84–98 (2019).
[9] F. Magoulès, Q. Zou, Asynchronous time-parallel method based on Laplace transform, International Journal of Computer Mathematics 98 (1) (2021) 179–194 (2021).
[10] F. Magoulès, G. Gbikpi-Benissan, Q. Zou, Asynchronous iterations of parareal algorithm for option pricing models, Mathematics 6 (4) (2018) 45 (2018).
[11] P. Spiteri, Parallel asynchronous algorithms: A survey, Advances in Engineering Software 149 (2020) 102896 (2020).
[12] J. M. Bahi, S. Contassot-Vivier, R. Couturier, Parallel iterative algorithms: from sequential to grid computing, CRC Press, 2007 (2007).
[13] D. P. Bertsekas, J. N. Tsitsiklis, et al., A survey of some aspects of parallel and distributed iterative algorithms, Tech. rep. (1989).
[14] G. M. Baudet, Asynchronous iterative methods for multiprocessors, Tech. rep., Department of Computer Science, Carnegie-Mellon University, Pittsburgh (1976).
[15] A. Uresin, M. Dubois, Generalized asynchronous iterations, in: International Conference on Parallel Processing, Springer, 1986, pp. 272–278 (1986).
[16] M. L. Daggitt, R. Zmigrod, T. G. Griffin, A relaxation of Üresin & Dubois’ asynchronous fixed-point theory in Agda, Journal of Automated Reasoning (2019).
[17] A. Üresin, M. Dubois, Parallel asynchronous algorithms for discrete data, Journal of the ACM (JACM) 37 (3) (1990) 588–606 (1990).
[18] J. Milnor, On the concept of attractor, in: The theory of chaotic attractors, Springer, 1985, pp. 243–264 (1985).
[19] A. J. T. Gurney, Asynchronous iterations in ultrametric spaces, Tech. rep. (2017).
URL https://arxiv.org/abs/1701.07434
[20] J. L. Sobrinho, Correctness of routing vector protocols as a property of network cycles, IEEE/ACM Transactions on Networking 25 (1) (2017) 150–163 (2017).
[21] U. Norell, Dependently typed programming in Agda, in: Proceedings of the 4th International Workshop on Types in Language Design and Implementation, 2009 (2009).
[22] M. L. Daggitt, R. Zmigrod, T. G. Griffin, Routing library (2020).
URL https://github.com/MatthewDaggitt/agda-routing/tree/jpdc2020
[23] M. L. Daggitt, T. G. Griffin, Formally verified convergence of policy-rich dbf routing protocols (2021). arXiv:2106.01184.