Stabilizing Consensus Is Impossible in Lossy Iterated Immediate Snapshot Models

Agreement tasks, and in particular consensus, have always been a focal point of distributed computing research, not only because of their practical applicability, but also because consensus tasks characterize very precisely the limits of a distributed computing model. Understanding such limitations not only facilitates the quick assessment of problem solvability in a given model, but also sheds light on the impact that certain properties, such as synchrony, impose on the system. For instance, the celebrated FLP impossibility result [15] reveals the devastating effect of both asynchrony and process crashes on deterministic consensus solvability. In a similar vein, it has been shown that process crashes impair general task solvability [21] even in asynchronous shared memory systems, and that byzantine faults [22] and/or message loss [25, 26, 11, 29, 30] impair consensus solvability even in the context of synchronous message passing systems.

Although distributed systems research has focused extensively on terminating tasks, there exist interesting applications and problems that are inherently non-terminating. Apart from the specific class of self-stabilizing distributed algorithms [12, 14], which can even tolerate massive transient faults, asymptotic consensus [4, 5], stabilizing consensus [2, 9, 27], and approximate consensus [8, 13] are examples of non-terminating distributed tasks: processes are not required to terminate after having computed some final value, but rather eventually converge to some stable configuration. Such tasks are not only of theoretical interest, but are also essential for implementing practical distributed problems such as clock synchronization [23, 28] and sensor fusion [3].

In this paper, we focus on stabilizing consensus, which can be viewed as the non-terminating variant of consensus. As in the case of consensus, all processes start with their own input values and must eventually agree on a common value. The fundamental difference to terminating consensus is that every process may start arbitrarily late, and does not need to decide on a value irrevocably and exactly once, but can change its decision value finitely often. Nevertheless, all processes must eventually stabilize on the same decision value.

It should be noted that stabilizing consensus is also loosely related to asymptotic consensus  [16], in the sense that, in neither problem, processes are required to terminate. A fundamental difference, however, is that asymptotic consensus allows processes to decide from a real-valued range, in contrast to the validity condition for stabilizing consensus, which only allows decisions from the pool of input values. Stabilizing consensus is a stronger problem, since any protocol that solves stabilizing consensus also solves asymptotic consensus. Indeed, we provide a simple novel model introduced below (the DLL), where stabilizing consensus is impossible (see Theorem 3.10), yet asymptotic consensus can be solved. In this light, asymptotic consensus is more closely related to approximate consensus [8], while stabilizing consensus is more closely related to consensus.

We consider a finite set of process $\mathrm{\Pi }=\{p_1,\mathrm{\dots },p_n\}$ that communicate through message passing via directional point-to-point links in lock-step synchronous rounds. We assume that rounds are communication-closed, i.e., messages sent at a round $r$ will also arrive at round $r$ or will not be delivered. Note that in contrast to [9] we assume synchronous process starts (i.e., starting round $s_p=1$ for all $p$) as this special case already facilitates our impossibility result. Obviously, our result then carries over to the more general model presented in the original paper.

Each process $p_i$ is given an initial input value ${\text{x}}_i$ from a finite set of inputs $I$. We say that an initial global configuration is an $n$-tuple ${(p_i,{\text{x}}_i)}_{i=1}^n$ of process-input pairs. We denote the set of possible input configurations as $ℐ$. Similarly, an output configuration is an $n$-tuple ${(p_i,{\text{y}}_i)}_{i=1}^n$. We denote the set of possible output configurations by $𝒪$.

We model distributed problems as input/output relations called tasks that map a set of input configurations $ℐ$ to a set of valid output configurations. Formally, a task is a triple $T=⟨ℐ,𝒪,\mathrm{\Delta }⟩$ where $\mathrm{\Delta }:ℐ\to 2^{𝒪}$ is a validity map that determines a subset of valid output configurations from a single input configuration. Tasks are widely used in the literature to capture problems in distributed setting, see for example [24, 17, 18].

The communication is governed by a message adversary that determines which processes are able to communicate at a given round. We use a directed graph $G_r$ on $\mathrm{\Pi }$, which we call the communication graph, to represent the message exchange at round $r$. We denote by $I{n}_G(p_i)$ the in-neighborhood of $p_i$ in graph $G$, which always includes $p_i$. Note that $I{n}_{G_r}(p_i)$ represents the set of processes from which $p_i$ receives a message at round $r$. We represent the communication in an execution by a communication graph sequence $\sigma ={(G_i)}_{i=1}^{\mathrm{\infty }}$, called a communication pattern, where $\sigma (k)=G_k$. We denote by $G\cdot \sigma$ the concatenation of $G$ with $\sigma$ and by $G^k$ the sequence of $G$ repeated $k$ times. If $\sigma ={(G_i)}_{i=1}^{\mathrm{\infty }}$ is a communication pattern, we say that ${(G_i)}_{i=1}^k$ is the $k$-prefix of $\sigma$, denoted by ${\sigma |}_1^k$. Conversely, ${\sigma |}_k^{\mathrm{\infty }}={(G_i)}_{i=k}^{\mathrm{\infty }}$ denotes the suffix starting from round $k$. We define $\mu ={(H_i)}_{i=1}^{\mathrm{\infty }}$ to be a sub-sequence of $\sigma ={(G_i)}_{i=1}^{\mathrm{\infty }}$, denoted by $\mu ⊑\sigma$, iff there is a strictly increasing sequence $s:\mathbb{N}\to \mathbb{N}$ such that $H_i=G_{s(i)}$. Note that the sub-sequence relation $⊑$ is a partial order on sequences with the same domain and co-domain. A message adversary is just a set of communication patterns $ℳ$.

Since our focus is on solvability, we assume for convenience that the processes execute a full-information flooding protocol. That is, at any given round $r$, each process will send a copy of its local state, also called view to all possible recipients. For terminating protocols and terminating tasks, we consider strong termination, i.e., a process stops its execution whenever a decision is made by the protocol. Thus, processes will stop sending messages and updating their views once the protocol has output a decision value. In contrast, for stabilizing tasks and protocols, we consider that the protocol never terminates and processes keep communicating and updating their views forever.

We define the view of a process $p_i$ at the end of a round $r$ under $\sigma ={(G_i)}_{i=1}^{\mathrm{\infty }}$ and initial configuration ${𝒞}^0$ as: $vie{w}_{{𝒞}^0:\sigma }(p_i,r):=⟨V({𝒞}^0:\sigma ,p_i,r),p_i,r⟩$, where $V({𝒞}^0:\sigma ,p_i,r)=\{vie{w}_{{𝒞}^0:\sigma }(p_j,r-1)|p_j\in I{n}_{{\sigma }_{r-1}}(p_i)\}$. We define $vie{w}_{{𝒞}^0:\sigma }(p_i,0):=⟨\{{\text{x}}_i\},p_i,0⟩$, where ${\text{x}}_i$ is the input value of process $p_i$ in ${𝒞}^0$.

We also employ a subview relation, denoted by $vie{w}_{{𝒞}^0:\sigma }(p_i,r)\prec vie{w}_{{𝒞}^0:\sigma }(p_j,s)$, which can be defined inductively: $vie{w}_{{𝒞}^0:\sigma }(p_j,s)\prec vie{w}_{{𝒞}^0\sigma }(p_i,r)$ iff $s=r-1$ and $vie{w}_{{𝒞}^0:\sigma }(p_j,s)\in V({𝒞}^0:\sigma ,p_i,r)$; or $vie{w}_{{𝒞}_{\sigma }^0}(p_j,s)\prec vie{w}_{{𝒞}^0:\sigma }(p_k,r-1)$ for some
$vie{w}_{{𝒞}^0:\sigma }(p_k,r-1)\in V({𝒞}^0:\sigma ,p_i,r)$. Intuitively, this subview relation captures all the previous local states that a given process $p_i$ is aware of at a given round $r$.

We denote by $\text{inputs}(vie{w}_{{𝒞}^0:\sigma }(p_i,r)):=\{{\text{x}}_j|⟨\{{\text{x}}_j\},p_j,0⟩\prec vie{w}_{{𝒞}^0:\sigma }(p_i,r)\}$ the set of inputs $p_i$ has heard of by round $r$. Whenever ${𝒞}^0$ is clear from the context or not relevant, we will omit it in favor of notational simplicity.

We define the kernel $Ker(\sigma )$ of a sequence $\sigma$ as the set of processes that reach all other processes infinitely often, i.e., processes in $Ker(\sigma )$ are able to disseminate their local state at any point in the run. Formally, $p\in Ker(\sigma )$ if and only if $\forall r>0:\exists r^{\prime }>r:\forall q\in \mathrm{\Pi }:vie{w}_{\sigma }(p,r)\prec vie{w}_{\sigma }(q,r^{\prime })$.

We define the global configuration at the end of round $r$ under a communication pattern $\sigma$ as an $n$-tuple ${𝒞}_{\sigma }^r:={(vie{w}_{\sigma }(p_i,r))}_{i=1}^n$.

As we only consider deterministic protocols, global configurations are fully determined by the input configuration, and the communication pattern $\sigma$. Therefore, in the context of this paper, we will consider that a run consists of the input configuration and communication pattern. Furthermore, whenever it is clear from the context, or the input configuration is not relevant, we will use communication pattern and run interchangeably.

We use views to determine indistinguishability between global configurations. More precisely, a global configuration ${𝒞}_{\alpha :\sigma }^r$ is indistinguishable from a global configuration ${𝒞}_{\beta :\mu }^r$ for a process $p_i\in \mathrm{\Pi }$ iff $vie{w}_{\alpha :\sigma }(p_i,r)=vie{w}_{\beta :\mu }(p_i,r)$, where $\alpha ,\beta \in ℐ$ are input configurations, and $\sigma ,\mu \in ℳ$ are communication patterns.

Note that any protocol can be split into a full-information flooding part that generates views and sends messages, and a decision map that produces an output value. If the output values form a valid configuration, then we say that the protocol solves a problem.

Formally, we define a decision map of a protocol $𝒫$ as a function that maps process views generated by the full information flooding protocol to output values. We will denote a decision map as ${\delta }_{𝒫}:Views(ℳ)\to O$, where $Views(ℳ)$ is the set of possible views induced by the message adversary $ℳ$ under the protocol $𝒫$, and $O$ is the set of possible output values. Note that for terminating protocols, an additional undecided value $\perp$ may be used for representing that the protocol is not yet ready to decide. However, since we are focusing only on stabilizing protocols, we require that a decision is made at every view.

We define the stabilization property for tasks, which can be thought of as a relaxation of termination. Whereas termination requires a process to irrevocably choose its output value once and possibly even finalize its execution, stabilization allows the protocol to run indefinitely and correct its output finitely often.

Nevertheless processes must eventually stabilize on a common constant output value. We call the round on which a process $p_i$ stabilizes, i.e., never changes its output again, the stabilization round $s_i$. It should be noted that stabilization may be reached agnostically. This means that there might be protocols where processes are guaranteed to stabilize, yet they are possibly never aware that they have already reached a stable state.

We model stabilizing problems as tasks, with the following definition of solvability:

We will first introduce two particular message adversaries defined for only two processes, namely Lossy-Link (denoted by LL) and Delayed Lossy-Link (denoted by DLL). Lossy-Link was introduced by Santoro and Widmayer [25] and revisited in [26, 11], where it was shown that consensus is impossible even if at most a single message may be lost in every round. We will show that stabilizing consensus is solvable in the LL but impossible in the DLL.

Lossy-Link consists of 2 processes that communicate through a bi-directional link that may lose at most one message per round. For readability purposes, throughout this section we will denote the set of processes as $\mathrm{\Pi }=\{\text{<svg class="ltx\_picture" height="6.09" overflow="visible" version="1.1" width="6.09"><g fill="\#FFFFFF" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,6.09) matrix(1 0 0 -1 0 0) translate(3.04,0) translate(0,-0.5)"><path d="M 2.77 3.54 C 2.77 5.07 1.53 6.31 0 6.31 C -1.53 6.31 -2.77 5.07 -2.77 3.54 C -2.77 2.01 -1.53 0.78 0 0.78 C 1.53 0.78 2.77 2.01 2.77 3.54 Z M 0 3.54"></path></g></svg>},\text{<svg class="ltx\_picture" height="6.09" overflow="visible" version="1.1" width="6.09"><g fill="\#0D0D0D" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,6.09) matrix(1 0 0 -1 0 0) translate(3.04,0) translate(0,-0.5)"><path d="M 2.77 3.54 C 2.77 5.07 1.53 6.31 0 6.31 C -1.53 6.31 -2.77 5.07 -2.77 3.54 C -2.77 2.01 -1.53 0.78 0 0.78 C 1.53 0.78 2.77 2.01 2.77 3.54 Z M 0 3.54"></path></g></svg>}\}$.

Although the Lossy-Link message adversary prohibits solving terminating consensus [25], it admits a simple stabilizing protocol that solves stabilizing consensus as it satisfies both that any LL pattern has a non empty kernel, and any LL pattern has a trivially bounded broadcast time. Hence, we provide a 2-process instance of the MinMax Algorithm, introduced in  [9], for stabilizing consensus. Since we adapt it to our full-information and flooding model, it suffices to provide a decision map ${\delta }_{MinMax}:Views(\text{LL})\to O$,
${\delta }_{MinMax}(vie{w}_{\sigma }(p_i,r)):=\underset{x\in V(vie{w}_{\sigma }(p_i,r))}{\max }\{\min (\text{inputs}(x))\}$

We omit a proof (for a complete formal treatment see [9]), but provide a sketch. The case where both have identical inputs is trivial, so assume w.l.o.g. that . We distinguish three cases, either (a) never hears from , or conversely (b) never hears from , or (c) both hear from each other. In (c) both eventually know both values after some round $r$. They then always choose ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#FFFFFF" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$, as its the smallest value they know and as its the smallest value in any message they will receive, starting from round $r+1$.

Case (a) is only possible in $()ω$, so always hears from and chooses ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#0D0D0D" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$, as its the maximum heard of in the last round ( also chooses ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#0D0D0D" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$ by validity). Similarly, case (b) is only possible in $()ω$, where after round $1$ the minimum has heard of is ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#FFFFFF" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$, and will never receive a larger value, thus always chooses ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#FFFFFF" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$ ( chooses the same by validity).

Now consider a different setting, where the communication link between and is also allowed to drop both messages, but only for at most $k$ consecutive rounds for some fixed $k$. We call this model the Bounded-Delay Lossy-Link, abbreviated as $\text{BDLL}(k)$. Following our previous notation, denotes the silent graph.

Note that, as some communication is always guaranteed, $\text{BDLL}(k)$ has a non-empty kernel for any $k$, satisfying (i) and trivially (ii). This also applies to the BDLL, where any sequence is an instance of some $\text{BDLL}(k)$.

Nevertheless, just $\text{BDLL}(1)$ already breaks ${\delta }_{MinMax}$, as it is not guaranteed anymore that the maximum in the system reaches all other processes in every round: Consider the graph sequence $(⋅)ω$ with , where always alternates its decision value: it will choose ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#FFFFFF" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$ if the last communication graph was , and ${\text{x}}_{\text{<svg class="ltx\_picture" height="4.47" overflow="visible" version="1.1" width="4.47"><g fill="\#0D0D0D" stroke="\#000000" stroke-dasharray="none" stroke-dashoffset="0.0pt" stroke-width="0.4pt" transform="translate(0,4.47) matrix(1 0 0 -1 0 0) translate(2.23,0) translate(0,-1.31)"><path d="M 1.96 3.54 C 1.96 4.62 1.08 5.5 0 5.5 C -1.08 5.5 -1.96 4.62 -1.96 3.54 C -1.96 2.46 -1.08 1.59 0 1.59 C 1.08 1.59 1.96 2.46 1.96 3.54 Z M 0 3.54"></path></g></svg>}}$ if it was , as it only considers messages from the last round. In order to circumvent this alternation, we could adapt ${\delta }_{MinMax}$ to look back two rounds instead of only looking at the last one. In fact, we can generalize this idea, by adapting ${\delta }_{MinMax}$ to consider the past $k$ rounds and thus making it suitable for $\text{BDLL}(k)$: ${\delta }_{MinMax}^k(vie{w}_{\sigma }(p_i,r)):=\underset{x\in V^k(vie{w}_{\sigma }(p_i,r))}{\max }\{\min (\text{inputs}(x))\}$, where $V^k(vie{w}_{\sigma }(p_i,r)):={\bigcup }_{j=0}^{min(k,r-1)}V(vie{w}_{\sigma }(p_i,r-j))$ is the set of views $p_i$ has received in the last $k$ rounds (when ).

A similar correctness argument as the one for ${\delta }_{MinMax}$ can be used to show that ${\delta }_{MinMax}^k$ solves stabilizing consensus in $\text{BDLL}(k)$. However, any ${\delta }_{MinMax}^k$ will fail in $\text{BDLL}(k+1)$. Charron-Bost and Moran cleverly fixed this in [9] and provided an algorithm capable of solving stabilizing consensus in $\text{BDLL}(k)$ for any fixed $k$, i.e., in BDLL. Intuitively their safe MinMax algorithm works as follows: Any sequence $\sigma \in \text{BDLL}$ is also a member of $\text{BDLL}(k)$, for some $k$. Of course, one cannot choose some $l$ that is always larger than any $k$, but, as the sequence $\sigma$ is chosen beforehand and $k$ therefore fixed, one can gradually increase $l$ such that it eventually surpasses any fixed $k$. And since ${\delta }_{MinMax}^l$ also correctly runs for any , once $l$ surpassed $k$ it will run correctly forever. Note that we will formalize this in Section 4 for $n$ processes.

Nevertheless, we will prove that no stabilizing protocol can exist if there is no fixed bound $k$ on the length of consecutive silence periods. We call this model the Delayed Lossy-Link message adversary, which can be seen as the limit of the BDLL.

Note that the DLL again has a non-empty kernel, as some communication always happens. It hence satisfies (i), does not satisfy (ii), as there is no bound on how many consecutive silent rounds may happen.

Also note that any communication pattern $\sigma \in \text{DLL}$ is essentially a sequence in the LL with arbitrarily long but finite periods of no communication in-between. Consequently, any communication pattern $\sigma \in \text{DLL}$ has a unique corresponding silence-free communication pattern $\mu \in \text{LL}$ where $\mu ⊑\sigma$, which we call the silence-free core of $\sigma$. Reciprocally, we say that $\sigma$ is a delayed pattern of $\mu$.

Previously, we introduced the Lossy-Link and Delayed Lossy-Link message adversary as a starting point for our stabilizing consensus impossibility result. This is for two main reasons: first, the simplicity of the Lossy-Link highlights the source of the impossibility result without adding distracting details to the proofs, and second, the DLL impossibility translates transparently to other message adversaries that generalize DLL.

One such message adversaries is the Iterated Immediate Snapshot message adversary, which is computationally equivalent to the asynchronous Iterated-Immediate Snapshot model defined as an $n$-process asynchronous shared memory model where processes communicate via atomic snapshots. The first approach towards this model was introduced by Borowski and Gafni [6], who presented the Immediate-atomic-snapshot model as a generalization of the classical FLP model [15]. They also re-used it as a convenient model for characterizing wait-free asynchronous shared memory systems [7].

In the IIS model, one considers a set $\mathrm{\Pi }={\{p_i\}}_{i=1}^n$ of processes that communicate through a shared memory object $M$. Each process may write into its own register $M[i]$ and is able to read the whole memory $M$ in an atomic snapshot operation. A process $p_i$ that executes an atomic snapshot writes into its register $M[i]$ and reads all of $M$ instantaneously. Since snapshot operations executed by different processes may occur concurrently, it is assumed that every process in a concurrent set is capable of reading each others output. Although atomic snapshot objects appear to be very strong, it has been shown that they are equivalent to single-reader single-writer wait-free shared registers [19].

Perhaps one of its most useful features of the IIS model is that it allows us to express an asynchronous shared memory model in terms of a synchronous message adversary [1], an asynchronous snapshot by all processes, can hence be represented by a communication graph. If a process $p$ and a process $q$ execute a snapshot operation, there are $3$ possibilities, either $p$ executed its snapshot before $q$, $q$ before $p$, or both snapshots are concurrent. If $p$ executes its snapshot before $q$, then $p$ cannot read what $q$ wrote, but $q$ will be able to read the value from $p$. Reciprocally, if $q$ executes its snapshot before $p$, $q$ will see $p$’s value but not vice versa. If $p$ and $q$ have concurrent snapshots, then both are able to read each other’s value. Since we consider time to be linearly ordered, and snapshots occur within the same time frame (round), then this means that for any pair of processes $p$ and $q$, either $p$ reads $q$ or $q$ reads $p$, or both. When translated to communication graphs, this implies that each communication graph in the IIS model is semi-complete ²²2A directed graph is semi-complete if for any pair of vertices $v,w$, either $(v,w)\in E(G)$ or $(w,v)\in E(G)$.. Since the time at which each process executed its snapshot determines completely the memory registers that each process is able to read, every communication graph in the IIS model is also transitive ³³3A directed graph $G$ is transitive iff $(v,w)(w,z)\in E(G)\Rightarrow (v,z)\in E(G)$..

The converse can also be shown, such that for every communication pattern $\sigma$ of semi-complete and transitive graphs, there is an IIS schedule that matches $\sigma$. Thus, for the rest of this paper, we will simply consider that $\text{IIS}:={𝒢}^{\omega }$, where $𝒢$ is the set of semi-complete and transitive graphs on $\mathrm{\Pi }$. Note carefully that LL satisfies both transitivity and semi-completeness.