<figure><img src="image_8.png" /><figcaption>Fig. 5. Example of a process-time graph prefix $PTG^3$ of a lock-step execution at time $t = 3$, for $n = 3$ processes and initial values $x = (1, 0, 1)$. Process 1's view $V_1(PT^2)$ is highlighted in bold green.</figcaption></figure>

Figure 5 shows an example of a process-time graph prefix occuring in a run with lock-step synchronous or asynchronous rounds. The nodes are horizontally aligned according to global time, progressing along the vertical axis.

Figure 6 shows an example of a process-time graph prefix occuring in a run with processes that do not execute in lock-step rounds and may crash. Nodes are again horizontally aligned according to global time, progressing along the vertical axis. The frontier $C^k$ of the $k^{th}$ consistent cut, reached at the end of round $k$, is made up of $C_p^k = \{(p, l_p(k), *) \in PTG^k | 0 \le l_p(k) \le k \text{ is maximal}\}$. That is, starting from the (possibly inconsistent) cut made up of the nodes $(p, k, *)$ of all processes, one has to go down for process $p$ until the first node is reached where no edge originating in a node with time $> k$ has been received.

Let $\mathcal{PT}^t$ be the set of all possible process-time graph $t$-prefixes, and $\mathcal{PT}^\omega$ be the set of all possible infinite process-time graphs, for all possible runs of our system. Note carefully that $\mathcal{PT}^t$, as well every set $\mathcal{P}^\ell$ of round-$\ell$ process-time graphs for finite $\ell$, is necessarily *finite* (provided the encoding $(*)$ for external environment events has a finite domain, which we assume). Clearly, $\mathcal{PT}^t$ resp. $\mathcal{PT}^\omega$ can be expressed as a finite resp. infinite sequence $(P^0, \dots, P^t) \in \mathcal{P}^0 \times \mathcal{P}^1 \times \dots \times \mathcal{P}^t = \mathcal{PT}^t$ resp. $(P^0, P^1, \dots) \in \mathcal{P}^0 \times \mathcal{P}^1 \times \dots = \mathcal{PT}^\omega$ of round-$\ell$ process time graphs.<fnref n="7" />

We will denote by $PS \subseteq \mathcal{PT}^\omega$ the set of all admissible process-time graphs in the given model, and by $\Sigma \subseteq \mathcal{C}^\omega$ the corresponding set of admissible executions. Note carefully that process-time graphs are *independent* of the (decision function of the) consensus algorithm, albeit they do depend on the initial values.

Due to the one-to-one of process-time graphs and executions established before, the topological machinery developed in Section 4–Section 5 for $\Sigma \subseteq \mathcal{C}^\omega$ can also be applied to $PS \subseteq \mathcal{PT}^\omega$. Since, in sharp contrast to the set of configurations $\mathcal{C}$, the set of process-time

<footnote n="7">⁷Note that we slightly abuse the notation $\mathcal{PT}^\omega$ here, which normally represents $\mathcal{PT} \times \mathcal{PT} \times \dots$.</footnote>
<figure><img src="image_9.png" /><figcaption>Fig. 6. Example of a process-time graph prefix in a non-lockstep execution of a system of $n = 3$ processes with initial values $x = (2, 0, 1)$, where process $p_3$ crashes in its step at time 1, in round 1. The vertical axis is the global time axis, and nodes at the same horizontal level occur at the same global time. The length of the edges represent end-to-end delay of a message resp. the access latency of a shared memory operation. Process 1's local view $V_1(PTG^3)$ in $PTG^3$ is highlighted in bold green.</figcaption></figure>

graphs $\mathcal{PT}^t$ is finite for any time $t$ and hence compact in the discrete topology, Tychonoff's theorem$^8$ implies compactness of the $p$-view topology on $\mathcal{PT}^\omega$.

Whereas this is not necessarily the case for $C^\omega$, we can prove compactness of the image of $\mathcal{PT}^\omega$ under an appropriately defined operational transition function: Given the original transition function $\tau_\epsilon : \mathcal{G} \times \mathbf{ACT}_\epsilon \to \mathcal{L}_\epsilon$, it is possible to define a PTG transition function $\hat{\tau} : \mathcal{PT}^\omega \to C^\omega$ that just provides the (unique) execution for a given process-time graph. The following Lemma A.2 shows that $\hat{\tau}$ is continuous in any of our topologies.

**LEMMA A.2 (CONTINUITY OF $\hat{\tau}$).** For every $p \in \Pi$, the PTG transition function $\hat{\tau} : \mathcal{PT}^\omega \to C^\omega$ is continuous when both $\mathcal{PT}^\omega$ and $C^\omega$ are endowed with any of $d_p$, $p \in \Pi$, $d_u$, $d_{nu}$.

**PROOF.** Let $U \subseteq C^\omega$ be open with respect to $d_p$, and let $a \in \hat{\tau}^{-1}[U]$. Since $U$ is open and $\hat{\tau}(a) \in U$, there exists some $\varepsilon > 0$ such that $B_\varepsilon(\hat{\tau}(a)) \subseteq U$. Let $t \in \mathbb{N}$ such that $2^{-t} \le \varepsilon$. We

<footnote>$^8$Tychonoff's theorem states that any product of compact spaces is compact (with respect to the product topology).</footnote>
will show that $B_{2-t}(a) \subseteq \hat{\tau}^{-1}[U]$. For this, it suffices to show that $\hat{\tau}[B_{2-t}(a)] \subseteq U$. By the equivalence of process-time graph prefixes and the corresponding consistent cuts, which is ensured by construction, it follows for the views of process $p$ that $V_p(a^t) = V_p(b^t)$ implies $V_p(\hat{\tau}(a)^t) = V_p(\hat{\tau}(b)^t)$. Using this in Section 4.1 implies

$$ \hat{\tau}[B_{2-t}(a)] \subseteq B_{2-t}(\hat{\tau}(a)) \subseteq B_{\varepsilon}(\hat{\tau}(a)) \subseteq U, $$

which proves that $\hat{\tau}^{-1}[U]$ is open as needed.

The proof for $d_u$ resp. $d_{nu}$ is analogous, except that Section 4.1 must be replaced by Section 4.2 resp. Section 4.3. $\square$

Since the image of a compact space under a continuous function is compact, it hence follows that the set $\hat{\tau}[\mathcal{PT}^\omega] \subseteq \mathcal{C}^\omega$ of admissible executions is a compact subspace of $\mathcal{C}^\omega$. The common structure of $\mathcal{PT}^\omega$ and its image under the PTG transition function $\hat{\tau}$, implied by the continuity of $\tau$, hence allows us to reason in either of these spaces. In particular, with Definition A.3, the analog of Theorem 5.2 and Theorem 5.3 read as follows:

*Definition A.3 (v-valent process-time graph).* We call a process-time graph $z_v$, for $v \in \mathcal{V}$, v-valent, if it starts from an initial configuration where all processes $p \in \Pi$ have the same initial value $I_p = v$.

**THEOREM A.4 (CHARACTERIZATION OF UNIFORM CONSENSUS).** *Uniform consensus is solvable if and only if there exists a partition of the set PS of admissible process-time graphs into sets $PS_v$, $v \in \mathcal{V}$, such that the following holds:*

(1) Every $PS_v$ is an open set in PS with respect to the uniform topology induced by $d_u$.

(2) If process-time graph $a \in PS$ is v-valent, then $a \in PS_v$.

**THEOREM A.5 (CHARACTERIZATION OF NON-UNIFORM CONSENSUS).** *Non-uniform consensus is solvable if and only if there exists a partition of the set PS of admissible process-time graphs into sets $PS_v$, $v \in \mathcal{V}$, such that the following holds:*

(1) Every $PS_v$ is an open set in PS with respect to the non-uniform topology induced by $d_{nu}$.

(2) If process-time graph $a \in PS$ is v-valent, then $a \in PS_v$.