Abstract
A reliable communication primitive guarantees the delivery, integrity, and authorship of messages exchanged between correct processes of a distributed system. We investigate the necessary and sufficient conditions for reliable communication in dynamic networks, where the network topology evolves over time despite the presence of a limited number of Byzantine faulty processes that may behave arbitrarily (i.e., in the globally bounded Byzantine failure model). We identify classes of dynamic networks where such conditions are satisfied, and extend our analysis to message losses, local computation with unbounded finite delay, and authenticated messages.
This technical report presents the complete version of the paper published in the SIROCCO 2026 conference proceedings [1].
1 Introduction↩︎
The reliable communication primitive is a fundamental building block for distributed systems. It guarantees the proper exchange of messages between correct processes, even if they are not directly connected by a communication link or if some participating processes behave maliciously (i.e., are Byzantine). In particular, the primitive ensures the authorship, integrity, and delivery of the information exchanged between correct processes. More precisely, it mandates that (i) all messages exchanged between correct processes are not modified during their propagation (integrity), (ii) messages eventually reach their destination (delivery), and (iii) the author of a message cannot be forged (authorship). Implementations of the reliable communication primitive have been studied in several settings [2]–[8]. In this paper, we consider the globally bounded Byzantine failure model (i.e., there is an upper bound \(f\) on the number of Byzantine faulty processes, and \(f\) is known to all correct processes), and a dynamic communication network. To the best of our knowledge, the work of Maurer et al. [6] is the only one that analyzes the solvability of the primitive in such a setting. It characterizes the necessary and sufficient conditions for reliable communication from a specific source to a defined target at a given time. However, the verification of the conditions identified by Maurer et al. [6] is equivalent to solving a NP-complete problem [9], [10].
In this work, we first extend such conditions to characterize when all correct processes can achieve reliable communication in a synchronous system independently of the diffusion time. We identify classes of dynamic networks that (i) satisfy the solvability conditions (ii) and where verifying that a network belongs to these classes is polynomial in the number of processes in the system. We then expand our analysis to include an asynchronous system with lossy links and find that the solvability conditions for synchronous systems also apply to asynchronous ones. Finally, we examine the case of authenticated messages.
2 Related Work↩︎
The reliable communication problem, which aims to implement a primitive to guarantee the delivery, integrity, and authorship of messages exchanged in a distributed system, has been the subject of extensive research in static networks under various assumptions. These include various types of faults, such as omissions, crashes, and arbitrary faults; alternative fault distributions, including deterministic and probabilistic models; and the impact of these faults on links [11], processes, or both. In a seminal work, Dolev [4] identified the necessary and sufficient condition for this problem in static networks with reliable and authenticated links, assuming an upper bound \(f\) on the number of Byzantine faulty processes. The condition states that the network must be \((2f+1)\)-connected to tolerate \(f\) such processes.
Subsequent work investigated more constrained process failure distributions. Koo [12] analyzed the reliable communication problem assuming only a fraction of nodes in a process’s neighborhood can be compromised. Pelc and Peleg [8] generalized Koo’s results by characterizing a failure model with an upper bound on faulty processes in each node’s neighborhood and defining a corresponding solution. Pagourtzis et al. [13] further generalized these models by assuming non-homogeneous local bounds on the number of faulty processes in each node’s neighborhood. They also showed this failure model can be extended by assuming specific sets of potentially faulty processes (the general adversary model), and that knowledge of the network topology increases the number of faulty processes that can be tolerated in the non-homogeneous, locally bounded setting.
Most solutions to the reliable communication problem rely on node-disjoint path redundancy, thus requiring highly connected networks. Consequently, several works have investigated weaker Byzantine-tolerant reliable communication primitives for use in loosely connected networks. These primitives may allow a small minority of correct processes to either deliver invalid messages or fail to deliver genuine ones [14]–[16].
Over the past two decades, the integration of computing and communication capabilities into a growing number of devices (e.g., IoT networks) has spurred increased interest in the modeling and analysis of dynamic distributed systems. Most of the dynamic distributed system models proposed so far can be categorized as either open or closed. The former involves new processes continuously entering and leaving the system (a phenomenon often referred to as churn), while the latter assumes a fixed set of processes whose communication links may change over time. In the context of closed dynamic networks, Maurer et al. [6] identified the necessary and sufficient conditions for solving a single instance of the reliable communication problem in the presence of a subset of \(f\) Byzantine faulty processes. Bonomi et al. [2], [17] identified the solvability conditions assuming the homogeneous locally bounded failure model of Pelc and Peleg [8]. Maurer [18] later extended the primitive to also withstand transient process failures.
Cryptography (specifically, digital signatures), by ensuring the authenticity and integrity of exchanged information, can be used to achieve Byzantine-tolerant reliable communication [19], [20]. The main advantage of such cryptographic tools is that they enable reliable communication with simpler solutions and under weaker connectivity requirements. However, their correctness depends on the underlying cryptosystem and the assumption that the adversary has bounded computing power. A common assumption of Byzantine-tolerant reliable communication protocols is the use of authenticated point-to-point channels, which prevents a process from impersonating multiple others (a Sybil attack) [21]. The primary distinction between cryptographic (authenticated) and non-cryptographic (unauthenticated) protocols for reliable communication lies in how cryptographic primitives are used: non-cryptographic protocols can only use digital signatures between neighbors for authentication, while cryptographic protocols use them to allow message verification even between nodes that are not directly connected. Finally, it is worth noting that cryptography is not strictly required to implement an authenticated channel [22].
This work builds upon the seminal characterization of the reliable communication problem in closed dynamic networks by Maurer et al. [6], extending it in several directions by: (i) specifying the solvability conditions for any pair of processes at any time; (ii) identifying classes of dynamic networks where these conditions hold; and (iii) considering weaker or alternative models in which messages can be lost and local computation delays are unknown.
3 Graphs and Evolving Graphs↩︎
A static undirected graph is a pair \(G = (V,E)\) of sets \(V\) and \(E\) such that \(E \subseteq \binom{{V}}{2}\). The elements \(p_i\) of \(V\) are the vertices (or nodes) of the graph, whereas the elements of \(E\) are the (undirected) edges [23]. Two vertices \(p_s, p_t\) connected by an edge \(\{p_s,p_t\} \in E\) are called neighbors. A sequence of distinct nodes \(P = (p_1, p_2, \dots, p_m)\) constitutes a path if every pair of consecutive nodes \(p_i\) and \(p_{i+1}\) in the sequence satisfies the condition that they are neighbors. Nodes \(p_1\) and \(p_m\) in \(P\) are referred to as endpoints. Two or more paths are disjoint if they share no node except their endpoints. A graph is connected if there exists a path between every pair of nodes. A graph is \(k\)-connected if removing any subset \(S \subset V\) of \(k-1\) nodes (and all the edges having at least one node in \(S\)) results in a connected subgraph. If a graph is \(k\)-connected, then there exists a set of \(k\) disjoint paths between all pairs of nodes [24]. The node connectivity of a graph is the minimum number of nodes that have to be removed from the graph to disconnect it [23].
An evolving graph (a.k.a. temporal graph) \(\mathcal{G} = (G_0, G_1, \dots, G_j, \dots)\) [25] is a sequence of static undirected graphs, where each graph \(G_j := (V,E_j \subseteq \binom{{V}}{2})\) denotes a snapshot of \(\mathcal{G}\). All snapshots share the same set of vertices \(V\), whereas the set of edges may change at every snapshot. An evolving graph is defined over a set of time instants \(\mathcal{T} \subseteq \mathbb{N}\), potentially infinite, drawn from the natural numbers, called the lifetime of \(\mathcal{G}\). Specifically, every snapshot \(G_j \in \mathcal{G}\) is associated with time instant \(j \in \mathcal{T}\), and vice-versa. We say that a particular edge \(e\) is present (or appears) at time \(j\) if \(e \in E_{j}\) (i.e., \(e\) is among the edges of snapshot \(G_j\)). The graph \(\mathbb{G} = (V, E = \bigcup_{{j}\in \mathcal{T}} E_j)\) is the underlying graph. We refer to \(V\) and \(E\) as the vertex set and edge set, respectively, of the evolving graph.
Given a subset \(T \subseteq \mathcal{T}\), a temporal subgraph \(\mathcal{G}_{T}\) of \(\mathcal{G}\) is the evolving graph that restricts the lifetime of \(\mathcal{G}\) to the instants \(j \in T\), namely, \(\mathcal{G}_{T}\) contains only the snapshots \(G_j\) in \(\mathcal{G}\) such that \(j \in T\). Then, \(\mathcal{G}_{[x,y]}\) is the temporal subgraph induced by the contiguous interval \([x,y]\) of \(\mathcal{T}\), i.e., \(\mathcal{G}_{[x,y]}\) limits the lifetime of \(\mathcal{G}\) to the period \([x, y]\). Similarly, the temporal subgraph \(\mathcal{G}_{[x,*]}\) restricts the lifetime of \(\mathcal{G}\) to the time instants after \(x\) (\(x\) included). A spatial subgraph \(\mathcal{G}[\bar{V}, \bar{E}]\) is the evolving graph resulting from \(\mathcal{G}\) when considering the set \(\bar{V} \subseteq V\) as vertex set, and \(\bar{E} \subseteq (E \cap \binom{\bar{V}}{2})\) as edge set. We specify a spatial subgraph only by its vertex set \(\bar{V}\), namely \(\mathcal{G}[\bar{V}]\), if its edge set \(\bar{E}\) consists of all the edges in the edge set that have both endpoints in \(\bar{V}\), i.e. \(\bar{E} = E \cap \binom{\bar{V}}{2}\). A spatial temporal subgraph \(\mathcal{G}[\bar{V}]_{T}\) of \(\mathcal{G}\) considers a subset \(T\) of the lifetime \(\mathcal{T}\), a subset \(\bar{V}\) of the vertices \({V}\) as vertex set, and \(\bar{E} = E \cap \binom{\bar{V}}{2}\) as edge set. Figure 1 shows a graphical example of an evolving graph spanning over three time instants, while Figure [fig:sttvg95example] presents a spatial temporal subgraph of the former, removing node \(p_2\) and snapshot \(G_2\).
A journey is the analogue of a path in an evolving graph.
Definition 1 (Journey [6]2). Given an evolving graph \(\mathcal{G} = (G_0, G_1, \dots, G_j, \dots)\), where each \(G_j = (V, E_j)\), and two of its nodes \(p_1, p_m \in V\), a journey from \(p_1\) to \(p_m\), denoted with \(p_1 \rightsquigarrow p_m\), is a pair \(J = (A,B)\) of two sequences \(A\) and \(B\) such that: \(A\) is a sequence of distinct nodes \((p_1, p_2, \dots, p_m)\) and \(B\) is a strictly increasing sequence of time instants \((j_I, j_{II}, \dots, j_{m-1})\), with \(j_\iota \in \mathcal{T}\), such that for all \(i \in \{1, \dots, m-1\}\), it holds that \(\{p_i, p_{i+1}\} \in E_{j_\iota }\).
Definition 2 (Set \(\Sigma(\mathcal{G},p_s,p_t)\) of node sets between two vertices [6]). Given an evolving graph \(\mathcal{G}\) and two of its nodes \(p_s, p_t \in V\), \(\Sigma(p_s,p_t)\) refers to the set of node sets \(\{\{p_1, \dots, p_l\} | (p_s, p_1, \dots, p_l, p_t)\) is a journey in \(\mathcal{G}\}\).
Definition 3 (Hitting set [26]). Let \(\Omega = \{S_1, S_2, \dots, S_m\}\) be a family of subsets of a universe \(U\), where \(S_i \subseteq U\) for each \(i \in \{1, \dots, m\}\). A set \(H \subseteq U\) is called a hitting set* for \(\Omega\) if it intersects every set in \(\Omega\), that is, \[\forall i \in \{1, \dots, m\}, \quad H \cap S_i \neq \emptyset.\]*
Definition 4 (Minimum Hitting Set [26] and MinCut [6]). Let \(\Omega = \{S_1, S_2, \dots, S_m\}\) be a family of subsets of a universe \(U\), where \(S_i \subseteq U\) for each \(i \in \{1, \dots, m\}\). A set \(H \subseteq U\) is called a minimum hitting set* for \(\Omega\) if:*
\(H\) is a hitting set for \(\Omega\), i.e., \(H \cap S_i \neq \emptyset\) for all \(i \in \{1, \dots, m\}\), and
\(H\) has the smallest possible cardinality among all hitting sets for \(\Omega\), i.e., for every hitting set \(H' \subseteq U\), it holds that \(|H| \leq |H'|\).
We refer with \(MinCut(\Omega)\) to the cardinality of a minimum hitting set for \(\Omega\).
Definition 5 (Dynamic minimum cut size \(k\) between two nodes and \(p_s \rightsquigarrow_k p_t\) [6]). Given an evolving graph \(\mathcal{G}\), two of its nodes \(p_s, p_t \in V\), the dynamic minimum cut size \(k\) from \(p_s\) to \(p_t\) is the smallest number of other nodes to remove from \(\mathcal{G}\) so that no journey exists from \(p_s\) to \(p_t\). Specifically, \[DynMinCut(\mathcal{G},p_s,p_t) = MinCut(\Sigma(\mathcal{G},p_s,p_t))\] Note that if \(\exists j \in \mathcal{T} : \{p_s, p_t\} \in E_j\), then \(DynMinCut(\mathcal{G},p_s,p_t) = \infty\).
We denote with \(p_s \rightsquigarrow_k p_t\) a set of journeys in \(\mathcal{G}\) from \(p_s\) to \(p_t\) having a dynamic minimum cut size at least \(k\).
In the same way, various families of graph have been defined in graph theory (trees, planar graphs, grids, etc.), and several classes of evolving graphs have been characterized in the literature [27], [28]. Specifically, a class of evolving graphs groups all graphs that satisfy a specific set of properties. We recall or define some relevant classes to our work in Section 5.1.
4 System Model and Problem Statement↩︎
We consider a distributed system composed of a fixed set of \(n\) processes \(N = \{p_1, p_2 \dots, p_n\}\), each one associated with a unique integer identifier. The evolution of the system is characterized by events occurring at specific times defined by a fictitious global clock spanning the natural numbers \(\mathbb{N}\).
Processes can communicate with each other by exchanging messages over a dynamic communication network composed of point-to-point links. The dynamic communication network is modeled by an evolving graph \(\mathcal{G} = (G_0, G_1, \dots, G_j, \dots)\). Each snapshot \(G_j = (V, ~ E_j)\) corresponds to the actual communication network at time \(j\) where \(V = N\) represents the set of processes participating in the system and \(E_j \subseteq N \times N\) is the actual set of existing (present) edges at time \(j\) (i.e., communication links available for the point-to-point communication). In the following, we will interchangeably use the terms node and process, and the terms link and edge. The evolving graph characterizes the communication network for the entire lifetime of the system. At each time \(j\), processes can only communicate by using present links, i.e., they can send/receive messages to/from their neighbors in the snapshot \(G_j\). We refer to multicast when a process sends a message through all of its available links, namely, to all of its current neighbors. Each message \(m\) is associated with a source/author and a sender: the source is the process that generates message \(m\), the sender is the process that relays message \(m\) through a link. The source and sender of a message may coincide.
At each time instant \(j\), every process executes the following concurrent steps: compute, send, and receive. Specifically, it carries out local computation and prepares (enqueues) messages to be sent to its neighbors, transmits these messages (if any), and receives messages from other processes (if any). Consequently, a message is able to traverse only one link during a single time instant \(j\).
Processes execute a distributed protocol \(\mathcal{P}\). Processes can be either correct or Byzantine faulty. A correct process executes the protocol \(\mathcal{P}\), Byzantine faulty processes can behave arbitrarily instead. In particular, while running \(\mathcal{P}\), faulty processes can send arbitrary messages or omit to send/receive all or part of them. We assume that at most \(f\) processes can be faulty (globally bounded Byzantine failure model).
To model the asynchrony and delays that may occur in the system, we consider two types of point-to-point communication primitives that characterize the behavior of the links (PL and FLL), and two alternative settings for the local computation delay of processes (SC and AC):
perfect link (PL): it provides the reliable delivery property [29], namely that if a correct process \(p_s\) sends a message \(m\) to a correct process \(p_r\) at time \(j\) via the present link, then \(p_r\) receives \(m\) at the same time \(j\);
fair-loss link (FLL): it guarantees the fair-loss property [29], namely that if a correct process \(p_s\) infinitely often (at distinct times) sends a message \(m\) to a correct process \(p_r\) via the present link, then \(p_r\) receives \(m\) an infinite number of times;
synchronous computation (SC): the local computation time (i.e., the time to perform the compute step) is negligible and is assumed to be equal to \(0\);
asynchronous computation (AC): the local computation (i.e., the compute step) takes a finite and unknown amount of time.
For the sake of modeling, we assume that (i) link properties only hold when links are present, that (ii) links have unbounded capacity (namely, if a correct process \(p_s\) sends an arbitrary set \(M\) of messages to a correct process \(p_r\) at time \(j\), then \(p_r\) receives all messages in \(M\) at the same time instant \(j\) (PL or FLL) or they are lost (FLL)), and (iii) that processes can instantly detect whether their links are available or not. The set of assumptions PL and SC characterizes a synchronous distributed system where processes and links are able to accommodate every message propagation enabled by the dynamic communication network \(\mathcal{G}\), namely, every journey in \(\mathcal{G}\) represents a feasible propagation pattern for a message between its endpoints (for an example, the journey \((\left(p_s,p_r,p_t\right),(1,2))\) models the possible propagation of a message exchanged at time \(1\) from \(p_s\) to \(p_r\) and then forwarded by \(p_r\) to \(p_t\) at time \(2\)). It follows that a message generated by a process \(p_s\) at time \(j\) in a PL-SC system can potentially reach any process \(p_t\) such that there exists a journey from \(p_s\) to \(p_t\) in \(\mathcal{G}_{[j,*]}\). The FLL assumption characterizes potentially asynchronous and lossy links in this setting, meaning that a process may attempt a finite but unknown number of times to send a message on a link that is infinitely often present before its first reception. The AC assumption characterizes the potential inability of processes to perform timely computation and generate messages to send for a finite amount of time. Note that the AC assumption does not prevent processes from receiving messages.
Finally, we consider two alternative settings that limit the capability of faulty processes:
authenticated links (AL): the identity of the sender of a message \(m\), i.e., the process sending \(m\) through a point-to-point link, cannot be forged;
authenticated messages (AM): the identity of the author of a message \(m\), namely, the process that generated a message \(m\), cannot be forged.
Note that the AM assumption can guarantee the authenticity of the author of a message over multiple links, while the AL assumption can guarantee the authenticity of the author only if it matches the sender of the message, and that the authenticated message setting does not implicitly assume authenticated links.
In the rest of the paper, we will indicate the setting under consideration, in terms of links and local computation assumptions, by specifying a triple \(\langle \alpha, \beta, \gamma \rangle\) where \(\alpha \in \{PL, FLL\}\), \(\beta \in \{SC, AC\}\) and \(\gamma \in \{AL, AM\}\).
The Reliable Communication Problem↩︎
We aim at analyzing the reliable communication problem, whose goal is the definition of a communication primitive that allows correct processes, not directly connected by a link, to exchange contents guaranteeing their authorship, integrity, and delivery.
Let us denote as source or author the process \(p_s\) that generates a content and as target \(p_t\) the peer to which such content is addressed. A Reliable
Communication (RC) primitive is accessible by every process in the system and exposes two operations: RC.send(\(p_t\),\(c\)) and
RC.deliver(\(p_s\),\(c\)). The send operation is invoked by the source to disseminate a content, and the deliver operation
notifies a process about the delivery of a content.
A protocol \(\mathcal{P}\) implements a reliable communication primitive if it satisfies the following properties:
safety: if \(p_t\) is a correct process and delivers a content \(c\) from \(p_s\), then \(p_s\) previously sent \(c\);
liveness: if \(p_s\) is a correct process and sends a content \(c\) to a correct process \(p_t\), then \(p_t\) eventually delivers \(c\) from \(p_s\).
For the sake of notation, we denote by content the payload exchanged by a reliable communication primitive, and by message the unit of information exchanged by a distributed protocol over a point-to-point link.
We say that an instance of the reliable communication problem starts at time \(j\) (or simply at time \(j\)) if at time \(j\)
the RC.send operation is executed, and that it terminates at time \(j\) if the target process \(p_t\) executes the RC.deliver(\(p_s\),\(c\)) operation for the first time at time \(j\).
5 Solvability Conditions↩︎
We characterize the solvability of the reliable communication problem in several settings. We start by recalling the result of Maurer et al. [6] who established the necessary and sufficient conditions for a one-to-one (i.e., from a defined source to a fixed target) reliable communication starting at time \(j\), in a setting where the links are perfect and authenticated and the computation is synchronous. We then extend their conditions to any starting time and any pair of processes. Afterwards, we look for further classes of evolving graphs where the learned conditions are verified. Interestingly, the stricter enabling class we identify for the PL and SC setting remains minimal also for the weakest setting we consider, namely asynchronous computation and fair-loss links; another class instead, allows to upper bound the latency of any reliable communication instance when synchronous computation and perfect links are assumed. Finally, we extend all of our results to the settings where messages are authenticated, and we provide an analysis on the computational complexity of asserting class membership for the dynamic network classes we identified. All the results that follow, cited or provided, are based on the existence of a specific set of journeys in the communication network that support the propagation of a content in the considered settings. Note that past theorems and definitions may be rephrased to fit our notations.
Some of the intermediate results and proofs are reported in Appendix 8.
5.1 Classes of Evolving Graphs↩︎
In this paper, we consider various classes of evolving graphs. While Definitions 6-11 were previously considered in the literature [27], Definitions 12-17 are newly defined to address the presence of Byzantine processes.
Definition 6 (Class \(\mathcal{J}_{(s,t)}\) - Temporal Reachability). The class \(\mathcal{J}_{(s,t)}\) is the set of all evolving graphs \(\mathcal{G}\) where there exists a journey from node \(p_s\) to node \(p_t\).
Definition 7 (Class \(\mathcal{TC}\) - Temporal Connectivity). The class \(\mathcal{TC}\) is the set of all evolving graphs \(\mathcal{G}\) where \(\forall p_s,p_t \in V\), there exists \((p_s \rightsquigarrow p_t) \in \mathcal{G}\) (the class of evolving graphs where a journey exists between every pair of nodes).
Definition 8 (Class \(\mathcal{J}^\mathcal{R}_{(s,t)}\) - Recurrent Reachability). The class \(\mathcal{J}^\mathcal{R}_{(s,t)}\) is the set of all evolving graphs \(\mathcal{G}\) where \(\forall j \in \mathcal{T}\), \(\mathcal{G}_{[j,*]} \in \mathcal{J}_{(s,t)}\).
Definition 9 (Class \(\mathcal{TC}^\mathcal{R}\) - Recurrent temporal connectivity). The class \(\mathcal{TC}^\mathcal{R}\) is the set of all evolving graphs \(\mathcal{G}\) with infinite lifetime where \(\forall j \in \mathcal{T}\), \(\mathcal{G}_{[j,*]} \in \mathcal{TC}\) (the class where, for every time instant \(j \in \mathcal{T}\), the temporal subgraph \(\mathcal{G}_{[j,*]}\) is temporally connected).
Definition 10 (Class \(\mathcal{C^*}\) - Always-connected snapshots, or 1-interval connectivity). The class \(\mathcal{C^*}\) is the set of all evolving graphs \(\mathcal{G}\) where \(\forall G_j \in \mathcal{G}\), \(G_j\) is connected (the class where every snapshot is a connected graph).
Definition 11 (Class \(\mathcal{E}^{\mathcal{R}}\) - Recurrent Edges). The class \(\mathcal{E}^{\mathcal{R}}\) is the set of all evolving graphs \(\mathcal{G}\) with infinite lifetime where \(\forall e \in E, ~ \forall j \in \mathcal{T}, ~ \exists l > j , e \in E_l\) (the class where every edge is present infinitely often).
Definition 12 (Class \(\mathcal{J}_{(s,t,k)}\) - \(k\)-journeys from \(p_s\) to \(p_t\)). The class \(\mathcal{J}_{(a,b,k)}\) is the set of all evolving graphs \(\mathcal{G}\) where \(\exists (p_s \rightsquigarrow_k p_t) \in \mathcal{G}\) (the class where there exists a set of journeys with a dynamic minimum cut of size at least \(k\) from node \(p_s\) to node \(p_t\)).
Definition 13 (Class \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\) - Recurrent \(k\)-journeys from \(p_s\) to \(p_t\)). The class \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\) is the set of all evolving graphs \(\mathcal{G}\) with infinite lifetime where \(\forall j \in \mathcal{T}\), \(\mathcal{G}_{[j,*]} \in \mathcal{J}_{(s,t,k)}\) (the class where the temporal subgraph \(\mathcal{G}_{[j,*]}\) is in \(\mathcal{J}_{(s,t,k)}\) for every time \(j\in \mathcal{T}\)).
Definition 14 (Class \(\mathcal{TC}_k\) - Temporal \(k\)-Connectivity). The class \(\mathcal{TC}_k\) is the set of all evolving graphs \(\mathcal{G}\) where \(\forall p_s,p_t \in V, ~ \exists (p_s \rightsquigarrow_k p_t) \in \mathcal{G}\) (the class where there exists a set of journeys having a dynamic minimum cut of size at least \(k\) between every pair of nodes).
Definition 15 (Class \(\mathcal{TC}^\mathcal{R}_k\) - Recurrent \(k\)-Temporal-Connectivity). The class \(\mathcal{TC}^\mathcal{R}_k\) is the set of all evolving graphs \(\mathcal{G}\) with infinite lifetime where \(\forall j \in \mathcal{T}\), \(\mathcal{G}_{[j,*]} \in \mathcal{TC}_k\) - the class where the temporal subgraph \(\mathcal{G}_{[j,*]}\) is in \(\mathcal{TC}_k\) for every time \(j \in \mathcal{T}\).
Definition 16 (Class \(\mathcal{C}^{*}_k\) - 1-interval \(k\)-connectivity). The class \(\mathcal{C}^{*}_k\) is the set of all evolving graphs \(\mathcal{G}\) where \(\forall G_j \in \mathcal{G}\), \(G_j\) is a \(k\)-connected graph (the class where the node connectivity of every snapshot is at least \(k\)).
Definition 17 (Class \(\mathcal{E}^{\mathcal{R}}_k\) (Recurrent Edges \(k\)-connected)). The class \(\mathcal{E}^{\mathcal{R}}_k\) is the set of all evolving graphs \(\mathcal{G}\) with infinite lifetime where, given \(\mathbb{G} = (V,E)\) as underlying graph of \(\mathcal{G}\), \(\mathbb{G}\) is a k-connected graph and \(\forall e \in E, ~ \forall j \in \mathcal{T}, ~ \exists l > j , e \in E_l\) (the class where the underlying graph is \(k\)-connected and every edge is present infinitely often).
5.2 Authenticated Links↩︎
Maurer et al. [6] characterized the strict condition to solve a single one-to-one instance of the reliable communication problem in the perfect authenticated links and synchronous computation setting.
In other words, they identified the message propagation pattern that the processes and the communication network must support (i.e., the “minimum” set of journeys that a content must traverse) in order to solve a single instance of the reliable communication problem under the considered settings. We recall their contribution in Appendix 7.
Theorem 1 (One-to-one RC at time \(j\) in \(\langle PL, SC, AL \rangle\) [6]). The reliable communication problem can be solved, starting at time \(j\), from a defined source \(p_s\) to a fixed target \(p_t\), in the perfect authenticated links* and synchronous computation setting, if and only if \(\mathcal{G}_{[j,*]} \in \mathcal{J}_{(s,t,2f+1)}\).*
From this seminal result [6], we can derive the class \(\mathcal{J}_{(s,t,k)}\) as the one that characterizes the communication networks where one-to-one reliable communication in \(\langle PL, SC, AL \rangle\) can be solved at least once.
We generalize the result by Maurer et al. [6] to any pair of processes and any time \(j\).
Theorem 2 (RC at time \(j\) in \(\langle PL, SC, AL \rangle\)). The reliable communication problem can be solved at time \(j\), in the perfect authenticated links* and synchronous computation setting, if and only if the dynamic subgraph \(\mathcal{G}_{[j,*]} \in \mathcal{TC}_k\) and \(k>2f\).*
Proof. The claim follows from an extension of Theorem 1, by considering any pair of processes as the source and target of a reliable communication instance, and by the construction of class \(\mathcal{TC}_k\) (Definition 14). Definition 12 identifies the class of evolving graphs where the strict condition for one-to-one reliable communication at time \(j\) holds (Theorem 1). Given any four nodes \(p_s,p_t,p_u,p_v \in V\), \(\mathcal{G}_{[j,*]} \in \mathcal{J}_{(s,t,2f+1)}\) does not imply \(\mathcal{G}_{[j,*]} \in \mathcal{J}_{(u,v,2f+1)}\); therefore, the condition must thus be verified for every pair of nodes. Definition 14 extends Definition 12 by considering any pair of processes; the claim thus follows given the strictness of Theorem 1. ◻
The \(\mathcal{TC}^\mathcal{R}_k\) class identifies the communication networks where the reliable communication problem is solvable in \(\langle PL, SC, AL \rangle\) at any time \(j\in\mathcal{T}\).
Theorem 3 (RC in \(\langle PL, SC, AL \rangle\)). The reliable communication problem can be solved starting at any time \(j\), in the perfect authenticated links* and synchronous computation setting, if and only if \(\mathcal{G} \in \mathcal{TC}^\mathcal{R}_k\) and \(k>2f\).*
Proof. The claim follows from an extension of Theorem 2, by considering any starting time for a reliable communication instance, and by the construction of class \(\mathcal{TC}^\mathcal{R}_k\) (Definition 15).
Definition 14 identifies the class of evolving graphs where the strict condition for reliable communication at time \(j\) holds (Theorem 2). Given \(x,y \in \mathcal{T}\), where \(y > x\), \(\mathcal{G}_{[y,*]} \in \mathcal{TC}_k\) implies \(\mathcal{G}_{[x,*]} \in \mathcal{TC}_k\), but the opposite relation does not hold; thus, the condition needs to be extended to any time \(j \in \mathcal{T}\). Definition 15 extends Definition 14 by considering any time \(j \in \mathcal{T}\); the claim thus follows given the strictness of Theorem 2. ◻
We identify further dynamic network sub-classes of \(\mathcal{TC}^\mathcal{R}_k\), thus providing additional classes where the primitive is feasible. We defined a sub-class of \(\mathcal{E}^{\mathcal{R}}\) that relates to the \(\mathcal{TC}^\mathcal{R}_k\) class and extends the result reported in the Theorem 3.
Theorem 4. Let \(\mathcal{G}\) be an evolving graph with infinite lifetime. If there exists a spatial subgraph \(\mathcal{G}' := \mathcal{G}[V, \bar{E}]\) of class \(\mathcal{E}^{\mathcal{R}}_k\) then \(\mathcal{G}\) is in \(\mathcal{TC}^\mathcal{R}_k\).
Proof. Consider a \(k\)-connected graph \(\mathbb{G}' = (V, \bar{E})\) where \(p_a\) and \(p_b\) are two of its nodes. It is known [23] that it is possible to identify a set of paths \(p_a \rightarrow_k p_b\) between \(p_a,p_b\) in \(\mathbb{G}'\) such that its minimum cut is at least \(k\) (namely, there exists a set of paths \(p_a \rightarrow_k p_b\) between \(p_a,p_b\) in \(\mathbb{G}'\) such that it is not possible to identify a subset \(S \subset V \setminus \{p_a, p_b\}\) of size \(k-1\) in which each path in \(p_a \rightarrow_k p_b\) shares at least one node with \(S\)). If \(\mathbb{G}'\) is the underlying graph of an evolving graph \(\mathcal{G}'\) of class \(\mathcal{E}^{\mathcal{R}}\) (thus \(\mathcal{G}' \in \mathcal{E}^{\mathcal{R}}_k\)) , then there always exists a set of journeys \(p_a \rightsquigarrow_k p_b\) traversing the paths \(p_a \rightarrow_k p_b\), because every edge re-appears infinitely often. It follows that \(\mathcal{G}' \in \mathcal{TC}^\mathcal{R}_k\) and the claim follows for any temporal graph \(\mathcal{G}\) having as underlying graph \(\mathbb{G} = (V, E \supseteq \bar{E})\). ◻
Corollary 1 (RC in \(\langle PL, NC, AL \rangle\) - recurrent edges). The reliable communication problem can be solved starting at any time \(j\), in the perfect authenticated links* and synchronous computation setting, if there exists a spatial subgraph \(\mathcal{G}' := \mathcal{G}[{V}, \bar{E}]\) in \(\mathcal{G}\) such that \(\mathcal{G}' \in \mathcal{E}^{\mathcal{R}}_k\) and \(k>2f\).*
Proof. It follows from Theorems 3 and 4. Theorem 3 characterizes class \(\mathcal{TC}^\mathcal{R}_k\) as the one where reliable communication is solvable at any time when \(k>2f\); Theorem 4 identifies \(\mathcal{E}^{\mathcal{R}}_k\) class as a subclass of \(\mathcal{TC}^\mathcal{R}_k\). ◻
Relations between recurrent reachability/connectivity and recurrent edges classes exist in both directions, as shown in the following.
Theorem 5. If an evolving graph \(\mathcal{G}\) is in \(\mathcal{J}^\mathcal{R}_{(s,t)}\) then there exists a spatial subgraph \(\mathcal{G}' := \mathcal{G}[\bar{V}, \bar{E}]\) of class \(\mathcal{E}^{\mathcal{R}}\) having a path between \(p_s\) and \(p_t\) in its underlying graph \(\bar{\mathbb{G}}=(\bar{V},\bar{E})\).
Proof. The \(\mathcal{J}^\mathcal{R}_{(s,t)}\) class guarantees the existence of a journey from node \(p_s\) to node \(p_t\) in all temporal subgraphs \(\mathcal{G}_{[j,*]}\) of \(\mathcal{G}\).
Let \(J_1 = (A_1,B_1)\) be a journey \((p_s \rightsquigarrow p_t) \in \mathcal{G}\), and let \(x_{1}\) and \(y_{1}\) be respectively the lowest and highest time instant associated to an edge in \(J_1\), namely the first the and last elements of \(B_1\). Let \(J_2 = (A_2,B_2)\) be a journey \((p_s \rightsquigarrow p_t) \in \mathcal{G}_{[y_1+1,*]}\), and let \(x_{2}\) and \(y_{2}\) be respectively the lowest and highest time instant associated to an edge in \(J_2\). The power set of a set \(R\) is the set of all subsets of \(R\). The power set of a set that has a finite number of elements has a finite number of elements as well. It follows that, continuing the reasoning above, and thus identifying edge set \(A_1, A_2, \dots\) there is at least one edge set \(A_j\) that occurs infinitely often, and the claim follows. ◻
Corollary 2. If an evolving graph \(\mathcal{G}\) is in \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\) then there exists a spatial subgraph \(\mathcal{G}' := \mathcal{G}[\bar{V}, \bar{E}]\) of class \(\mathcal{E}^{\mathcal{R}}\) having a set of \(k\) disjoint paths between \(p_s\) and \(p_t\) in its underlying graph \(\bar{\mathbb{G}}=(\bar{V},\bar{E})\).
Proof. The claim follows for the same argument provided in Theorem 5.
The \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\) class guarantees the existence of a set of journeys from \(p_s\) to \(p_t\), having a dynamic minimum cut of size at least \(k\), for all temporal subgraphs \(\mathcal{G}_{[j,*]}\) of \(\mathcal{G}\), namely \(\forall j \in \mathcal{T}, \exists (p_a \rightsquigarrow_k p_b) \in \mathcal{G}_{[j,*]}\).
Let \(P_1\) be a set of journeys \((p_a \rightsquigarrow_k p_b) \in \mathcal{G}\), let \(x_{1}\) and \(y_{1}\) be respectively the lowest and highest time instant associated to an edge of a journey in \(P_1\), and let \(E_1 \subseteq E\) be the set of edges in \(P_1\). Let \(P_2\) be a set of journeys \((p_a \rightsquigarrow_k p_b) \in \mathcal{G}_{[y_1+1,*]}\), let \(x_{2}\) and \(y_{2}\) be respectively the lowest and highest time instant associated to an edge of a journey in \(P_2\), and let \(E_2\subseteq E\) be the set of edges in \(P_2\). The power set of a set that has a finite number of elements has a finite number of elements as well. It follows that, continuing the reasoning above, and thus identifying edge set \(E_1, E_2, \dots\), there is at least one edge set \(E_j\) that occurs infinitely often, and the claim follows. ◻
Corollary 3. Let \(\mathcal{G}\) be an evolving graph with infinite lifetime. If \(\mathcal{G}\) is in \(\mathcal{TC}^\mathcal{R}_k\) then there exists a spatial subgraph \(\mathcal{G}' := \mathcal{G}[V, \bar{E}]\) of class \(\mathcal{E}^{\mathcal{R}}_k\)
Proof. The claim follows for the same argument provided in Corollary 2, considering any pair of nodes \(p_s,p_t\). ◻
We prove that the classes \(\mathcal{C}^{*}_k\) and \(\mathcal{TC}^\mathcal{R}_k\) are also related. Specifically, \(\mathcal{C}^{*}_k\) is a sub-class of \(\mathcal{TC}^\mathcal{R}_k\) if \(\mathcal{G}\) has infinite lifetime, and we accordingly extend previous solvability results on the reliable communication problem.
Theorem 6. Given an evolving graph \(\mathcal{G}\) with infinite lifetime, if \(\mathcal{G} \in \mathcal{C}^{*}_k\) then \(\mathcal{G}_{[j,{j +n-k}]} \in \mathcal{TC}_k\) for any \(j \in \mathcal{T}\), and thus \(\mathcal{G} \in \mathcal{TC}^\mathcal{R}_k\).
Proof. Consider an evolving graph \(\mathcal{G} \in \mathcal{C}^{*}_k\) with \(V\) as vertex set, \(|V| = n\), and a pair of its nodes \(p_s,p_t \in V\).
Let \(\Pi_{(s,t)}\) be the set of all the journeys from \(p_s\) to \(p_t\) in the temporal subgraph \(\mathcal{G}_{[j,j +n-k]}\). Note that every temporal subgraph \(\mathcal{G}_{\bar{T}}\) of an evolving graph \(\mathcal{G}\) in \(\mathcal{CK}^{*}_k\) is by definition also in \(\mathcal{CK}^{*}_k\).
Let \(S\) be a subset of \(k-1\) nodes of \(V\) not containing \(p_s\) and \(p_t\), namely \(S \subset V \setminus \{p_s,p_t\}\), \(|S| = k-1\), and let \(\mathcal{G}'\) be the spatial temporal subgraph of \(\mathcal{G}\) such that \(\mathcal{G}' := \mathcal{G}[V \setminus S]_{[j,{j+n-k}]}\). The evolving graph \(\mathcal{G}'\) is 1-interval connected by construction because at least \(k\) nodes must be removed from \(\mathcal{G}\) to disconnect any of its snapshots.
Let \(\Pi[V \setminus S]_{(s,t)}\) be the set of all the journeys from \(p_s\) to \(p_t\) in \(\mathcal{G}'\). It has been proven in [30] that \(n'-1\) instants, where \(n'\) is the number of nodes in an evolving graph, are sufficient to traverse a journey between any two nodes in a 1-interval connected graph (class \(\mathcal{C^*}\)); the evolving graph \(\mathcal{G}'\) is composed of \(n-(k-1)\) nodes, thus a journey from \(p_s\) to \(p_t\) can always be traversed in at most \(n-(k-1)-1 = n -k\) instants, and thus \(\Pi[V \setminus S]_{(s,t)} \neq \emptyset\).
It follows that there exists a set of journeys with a dynamic minimum cut size at least equal to \(k\) in \(\mathcal{G}_{[j,{j+n-k}]}\) from \(p_s\) to \(p_t\) because there exists at least one journey in \(\Pi_{(s,t)}\) from \(p_s\) to \(p_t\) when removing any subset \(S \subset V \setminus \{p_s, p_t\}\) of \(k-1\) nodes.
Given that, for any \(j \in \mathcal{T}\), \(\mathcal{G}_{[j,{j +n-k}]} \in \mathcal{TC}_k\), it follows that \(\mathcal{G} \in \mathcal{TC}^\mathcal{R}_k\) by Definition 15. ◻
Corollary 4 (RC in \(\langle PL, SC, AL \rangle\) - 1-interval). The reliable communication problem can be solved starting at any time \(j\), in the perfect authenticated links* and negligible computation setting, if \(\mathcal{G} \in \mathcal{C}^{*}_k\) and \(k>2f\). Furthermore, it can be solved in \(n-k\) time.*
Proof. It follows from Theorems 2 and 6. Theorem 2 characterizes class \(\mathcal{TC}_k\) as the one where reliable communication is solvable when \(k>2f\); Theorem 6 identifies \(\mathcal{C}^{*}_k\) class as a subclass of \(\mathcal{TC}^\mathcal{R}_k\) where all of its temporal subgraphs with lifetime \(n-k\) are in \(\mathcal{TC}_k\). The upper bound on the latency follows from the fact that \(\forall j \in \mathcal{T}, \mathcal{G}_{[j,j+n-k]} \in \mathcal{TC}_k\), thus \(p_s \rightsquigarrow_k p_t\) are traversable in \(n-k\) times for whatever pair of \(p_s\) and \(p_t\). ◻
For the sake of completeness, we state a relation that exists between evolving graphs classes \(\mathcal{C}^{*}_k\) and \(\mathcal{E}^{\mathcal{R}}_k\).
Theorem 7. Let \(\mathcal{G}\) be an evolving graph with infinite lifetime. If \(\mathcal{G} \in \mathcal{C}^{*}_k\) (1-interval k-connectivity) then there exists a spatial subgraph \(\mathcal{G}[V, E^\mathcal{R}]\) of class \(\mathcal{E}^{\mathcal{R}}_k\) (recurrent edges k-connected).
Proof. If an evolving graph \(\mathcal{G}\) is 1-interval \(k\)-connected and has an infinite lifetime, then a subset of its edges \(E^\mathcal{R} \subseteq E\) must be present within an infinite number of snapshots. Indeed, the number of nodes in \(\mathcal{G}\) is finite and equals to \(n\), and the number of possible edges is finite as well (at most \(n^2\)). It follows that some edges in \(E\) must re-appear infinitely often. We prove that if \(\mathcal{G}\) is 1-interval \(k\)-connected then the set of edges \(E^\mathcal{R}\) that re-appears infinitely often forms a \(k\)-connected graph \(\mathbb{G}' = (V, E^\mathcal{R})\).
Let us partition the edges of \(E\) in \(\mathcal{G}\) in two sets: \(E^\mathcal{R}\) containing all the edges that re-appear infinitely often and \(\tilde{E}\) that are present a finite number of times in \(\mathcal{G}\). Let \(t_z\) be the time when the last appearance of an edge in \(\tilde{E}\) occurs in \(\mathcal{G}\). It follows that starting at time \(t_{z+1}\) all edges in \(\mathcal{G}\) must appear infinitely often. The 1-interval \(k\)-connectivity property of \(\mathcal{G}\) requires that all the edges \(E^\mathcal{R}\) must form a \(k\)-connected graph, and the claim follows. ◻
Finally, we study the solvability conditions of the reliable communication problem while relaxing the assumptions of perfect links and synchronous computation.
Theorem 8 (One-to-one RC in \(\langle FLL / AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the one-to-one reliable communication problem can be solved starting at any time \(j\) if and only if \(\mathcal{G} \in \mathcal{J}_{(s,t,k)}^\mathcal{R}\) and \(k>2f\).
Proof. Provided in Appendix 8. ◻
Theorem 9 (RC in \(\langle FLL/AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the any-to-any reliable communication problem can be solved starting at any time \(j\) if and only if \(\mathcal{G} \in \mathcal{TC}^\mathcal{R}_k\) (Recurrent \(k\)-Temporal-Connectivity) and \(k>2f\).
Proof. The claim follow by extending arguments provided in Theorem 8 to any pair of nodes. Given any four nodes \(p_s,p_t,p_u,p_v \in V\), \(\mathcal{G} \in \mathcal{J}_{(s,t,k)}^\mathcal{R}\) does not imply \(\mathcal{J}_{(u,v,k)}^\mathcal{R}\); therefore, the condition must thus be verified for every pair of nodes. Definition 14 extends Definition 12 by considering any pair of processes; the claim thus follows given the strictness of Theorem 8. ◻
Different from the \(\langle PL, SC, AL \rangle\) setting, the start time of the RC instance in the \(\langle FLL/AC, AL \rangle\) case is irrelevant for the solvability conditions of the examined problems. Further details are reported in Corollaries 8 and 9 in Appendix 8.
All the additional results identified for the defined sub-classes of \(\mathcal{TC}^\mathcal{R}_k\) extend in the setting where either links are fair-loss, or local computation is asynchronous, or both.
Corollary 5 (RC in \(\langle FLL/AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the reliable communication problem can be solved starting at any time \(j\) if \(\mathcal{G} \in \mathcal{E}^{\mathcal{R}}_k\) (recurrent edges k-connected) and \(k>2f\).
Corollary 6 (RC in \(\langle FLL/AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the reliable communication problem can be solved starting at any time \(j\), if \(\mathcal{G} \in \mathcal{C}^{*}_k\) (1-interval k-connectivity) and \(k>2f\).
5.3 Authenticated messages↩︎
Theorem 1 by Maurer et al. [6] identifies the base condition enabling one-to-one reliable communication from a defined source \(p_s\) and a specific target \(p_t\) starting at time \(j\), that is, the existence of a set of journeys \(p_s \rightsquigarrow_k p_t\) in \(\mathcal{G}_{[j,*]}\) with \(k>2f\). More specifically, there must exist a set of journeys \(p_s \rightsquigarrow_{2f+1} p_t\) in \(\mathcal{G}_{[j,*]}\) that cannot be cut by any set of \(2f\) nodes [6]. Maurer et al. [6] additionally studied the one-to-one at time \(j\) specification in the perfect links, synchronous computation and authenticated message setting. We recall its solution in Appendix 8.2 and the identified solvability condition in the following.
Theorem 10 (One-to-one RC at time \(t_j\) in \(\langle PL, SC, AM \rangle\) [6]). The one-to-one reliable communication problem can be solved starting at time \(j\) from a process \(p_s\) to a process \(p_t\), in the perfect link, synchronous computation, and authenticated messages* setting, if and only if it exists a set of journeys \(p_s \rightsquigarrow_k p_t\) in \(\mathcal{G}_{[t_i,*]}\) and \(k>f\).*
All extension results are collected in the following Corollary.
Corollary 7 (RC in \(\langle *, *, AM \rangle\)). All the results available on the reliable communication problem for the authenticated link setting (AL), specifically Theorems 2, 3, 8, 9, and 11, and Corollaries 1, 4, 5, 6, 8 and 9, extend to the authenticated message setting (AM) while requiring \(k>f\) (instead of \(2f\)). More in detail, the solvability conditions to the reliable communication problem in the authenticated message settings are the ones reported in Table 1.
Proof. The Corollary follows from the same argument given for the results presented in Subsection 5.2. Theorem 10 provides the network conditions for solving the one-to-one problem at a given time. The extension follows by identifying classes of evolving graphs for which such conditions are verified, considering every pair of processes and infinitely often occurrences of the conditions. The results differ on the parameter \(k\), which must be greater than \(f\). Note that the Maurer et al. solution reported in Algorithm 1 (Appendix 7) needs to be modified as reported in Algorithm 2 (Appendix 8) to extend to fair-loss links and/or asynchronous computation settings. ◻
5.4 On the complexity of verifying class membership↩︎
The evolution of the communication network of a distributed system can be assumed, in the sense that in certain real deployments it is reasonable to consider a particular model for the dynamic communication network. For example, it could be reasonable to assume that a swarm of mobile robots, moving inside a limited area, are repeatedly able to establish temporary communication links, and the resulting dynamic communication network provides recurrent temporal connectivity (class \(\mathcal{TC}^\mathcal{R}\)). Alternatively, the complete characterization of the evolution of a communication network, such as an evolving graph detailing the sets of available links over time, can be known in advance. For example, considering the same example of a swarm of mobile robots, if the schedule of the exact movements of all the robots are known in advance, it is possible to deduce exactly when every pair of robot is able to establish a communication link. In the latter setting, it is worth to notice that if a characterization of the communication network is provided as an evolving graph, the verification of class membership can be impractical to perform. More in detail, it has been proven [9], [10], [31] that it is NP-complete to decide whether the dynamic minimum cut size from a node \(p_s\) to \(p_t\) in an evolving graph is equal to a certain value \(k\). It follows that the solvability conditions presented in Theorems 1, 2, 3, 9, and 11, and Corollaries 8, and 9, are NP-complete to verify on any temporal subgraph of the evolving graph. On the other hand, conditions defined on the recurrent edges \(k\)-connected (\(\mathcal{E}^{\mathcal{R}}_k\)) and 1-interval \(k\)-connectivity (\(\mathcal{C}^{*}_k\)) classes can be verified with a polynomial algorithm on any temporal subgraph of an evolving graph, motivating the analysis of such subclasses of \(\mathcal{TC}^\mathcal{R}_k\), particularly in light of the result presented in Corollary 3.
6 Conclusion↩︎
In this work, starting from the seminal contribution of Maurer et al. [6], we characterized the conditions that allow reliable communication between all processes at any time, and identified classes of dynamic networks that satisfy them. All the relations we identified between the classes of evolving graphs are summarized in Figure 2. In particular, class \(\mathcal{TC}^\mathcal{R}_k\) is the smallest class of evolving graph for which the problem is solvable under all the settings we considered. Classes \(\mathcal{E}^{\mathcal{R}}_k\) and \(\mathcal{CK}^{*}_k\) are subclasses of \(\mathcal{TC}^\mathcal{R}_k\) that can be verified in polynomial time on any temporal subgraph of an evolving graph. All the identified results are outlined in Table 1.
| Solvability Conditions | |
|---|---|
| \(\langle AL, PL, SC\rangle\) | 1-to-1 at \(j\) : \(\mathcal{J}_{(a,b,k)} \land k>2f\) [6] 1-to-1 at any \(j\) : \(\mathcal{J}_{(a,b,k)}^\mathcal{R} \land k>2f\) *-to-* at \(j\) : \(\mathcal{TC}_k \land k>2f\) *-to-* at any \(j\) : \(\mathcal{TC}_k^{\mathcal{R}} \land k>2f\) |
| \(\langle AL, FLL, * \rangle\) \(\langle AL, *, AC \rangle\) | 1-to-1 at (or at any) \(j\) : \(\mathcal{J}_{(a,b,k)}^\mathcal{R} \land k>2f\) *-to-* at (or at any) \(j\) : \(\mathcal{TC}_k^{\mathcal{R}} \land k>2f\) |
| \(\langle AM, PL, SC \rangle\) | 1-to-1 at \(j\) : \(\mathcal{J}_{(a,b,k)} \land k>f\) [6] 1-to-1 at any \(j\) : \(\mathcal{J}_{(a,b,k)}^\mathcal{R} \land k>f\) *-to-* at \(j\) : \(\mathcal{TC}_k \land k>f\) *-to-* at any \(j\) : \(\mathcal{TC}_k^{\mathcal{R}} \land k>f\) |
| \(\langle AM, FLL, * \rangle\) \(\langle AM, *, AC \rangle\) | 1-to-1 at (or at any) \(j\) : \(\mathcal{J}_{(a,b,k)}^\mathcal{R} \land k>f\) *-to-* at (or at any) \(j\) : \(\mathcal{TC}_k^{\mathcal{R}} \land k>f\) |
Several interesting lines of future research include: compare our deterministic classes of dynamic networks with those induced by probabilistic models, and identify (with high probability) equivalence conditions between the two models; analyze real datasets of dynamic networks (vehicles, drones, etc.), verifying whether identified conditions are satisfied; extend the study to open dynamic networks (where infinitely many processes may join and leave), or to the more demanding reliable broadcast problem [32], [33] (where the sender also can be Byzantine).
6.0.1 ↩︎
This work was partially supported by ANR project SAPPORO 2019-CE25-0005.
6.0.2 ↩︎
The authors have no competing interests to declare that are relevant to the content of this article.
Appendix↩︎
7 Maurer et al. [6] Reliable Communication Results↩︎
Maurer et al. [6] defined a protocol solving the reliable communication problem in the perfect authenticated links and synchronous computation setting. The solution is provided in Algorithm 3. Every message exchanged by the protocol has the format \((s,c,S)\), where \(s\) is the identifier of the source of the relayed content \(c\), whereas \(S\) is the set of nodes traversed by the content. Byzantine processes are able to generate messages with arbitrary fields. Correct processes only deliver the contents that have been received through a collection of journeys that cannot be cut by \(f\) nodes (where \(f\) is a parameter of the protocol and supposed to be the upper bound of the total number of faulty nodes).
Initially, \(\Omega_i\) in Algorithm 3 is initialized to the empty set. When a process \(p_s\) aims to reliably communicate a content \(c\) at time \(j\), it triggers the RC.send(\(*\),\(c\)) operation. This action adds \((s,c,\emptyset)\) to \(\Omega_s\) and triggers RC.deliver(\(s\),\(c\))3. The solution is then defined by three rules: (i) whenever the \(\Omega_i\) or the set of neighbors changes, the process multicast \(\Omega_i\); (ii) upon receiving \(\Omega_r\) from process \(p_r\), the sender identifier \(r\) is added to the set
\(S\) contained in each tuple \((s,c,S)\) in \(\Omega_r\), and the resulting tuple is inserted in \(\Omega_i\)4; (iii) whenever, among all the sets \(S_x\) associated to a source \(s\) and content \(c\) in \(\Omega_i\), it is possible to identify a minimum hitting set of size greater than \(f\), then the content \(c\) from
\(p_s\) is delivered.
![Figure 3: Maurer et al. [6] Authenticated Link solution](/article/2503.22452/_pdflatex/rubjfsdi.png "fig:")
Lemma 1 (Necessary Condition to One-to-One RC at time \(j\) in \(\langle PL, SC, AL \rangle\) [6]). For a given evolving graph \(\mathcal{G}\), let us suppose that there exists an algorithm ensuring one-to-one reliable communication from \(p_s\) to \(p_t\) at time \(j\). Then, we necessarily have \(DynMinCut(\mathcal{G}_{[j,*]},p_s,p_t)>2f\).
Lemma 2 (Sufficient Condition to One-to-one RC at time \(j\) in \(\langle PL, SC, AL \rangle\) [6]). For a given evolving graph \(\mathcal{G}\), let \(p_s\) and \(p_t\) be two correct processes. If \(DynMinCut(\mathcal{G}_{[j,*]},p_s,p_t)>2f\) then the Maurer et al. solution (Algorithm 3) ensures one-to-one RC at time \(j\) in \(\langle PL, SC, AL \rangle\).
Proof. The proofs for Lemmas 1 and 2 are provided in [6]. Given that several of the subsequent results follow from these seminal Lemmas, we provide an intuitive proof for the sufficient condition (Lemma 2).
Let us refer with \(\Pi_{s,t,j}(P)\) to the set of all the journeys in \(\mathcal{G}_{[j,*]}\) passing through the path \(P \in \mathbb{G}\) between \(p_s\) and \(p_t\). The assumption \(DynMinCut(\mathcal{G}_{[j,*]},p_s,p_t)>2f\) implies that \(\Pi_{s,t,j}(P)\) is not empty
for at least one path \(P \in \mathbb{G}\). We start by showing there is a correspondence between the journeys in \(\mathcal{G}_{[j,*]}\) and the evolution of Algorithm 3. Specifically, that if a process \(p_s\) triggers RC.send(\(*\),\(c\)) at time \(j\), then \(\Omega_t\) will eventually contain \((s,c,P\setminus\{t\})\). For the sake of contradiction, let us assume that process \(p_s\) triggers RC.send(\(*\),\(c\)) at time \(j\), that the set \(\Pi_{s,t,j}(P)\) is not empty, and that process \(p_t\) will never store \((s,c,P \setminus \{t\})\) in \(\Omega_t\). The
RC.send(\(*\),\(c\)) trigger at time \(j\) inserts \((s,c,\emptyset)\) to \(\Omega_s\). Such an insertion satisfies rule 1 of Algorithm 3, thus if a link is present between a process \(p_s\) and a process \(p_u\) at time \(j\), where \(p_u\) is the second element of \(P\), \((s,c,\emptyset)\) is sent
to \(p_u\), and \((s,c,\{s\})\) is then stored in \(\Omega_u\). If the link \(\{p_s,p_u\}\) is not available at time \(j\) it will be at time \(l>j\). Then, rule 1 of Algorithm 3 will be satisfied, and \((s,c,\{s\})\) will be stored in \(\Omega_u\) at time \(l\). If subsequently the insertion in \(\Omega_u\) a link is present between \(p_u\) and a process \(p_v\), where \(p_v\) is the third element of \(P\), \((s,c,\{s\})\) is sent to \(p_v\), and
\((s,c,\{s,u\})\) is then stored in \(\Omega_v\). The argument extends till the last element of \(P\) leading to a contradiction.
We proceed with proving the liveness property of reliable communication, thus showing that if \(DynMinCut(\mathcal{G}_{[j,*]},p_s,p_t)>2f\) and \(\texttt{{RC.send(*, c)}}\) is
triggered at time \(j\), then RC.deliver(\(s\),\(c\)) will eventually be triggered by process \(p_t\). The assumption \(DynMinCut(\mathcal{G}_{[j,*]},p_s,p_t)>2f\) implies the existence of a set of journeys \(Q = (p_s \rightsquigarrow_{>2f} p_t) \in
\mathcal{G}_{[j,*]}\). It follows from what has been proven above that \(p_t\) will eventually store \((s,c,P \setminus \{t\})\) in \(\Omega_t\) for
each path \(P\) underlying a journey in \(Q\). The Byzantine processes can block only the propagation of tuples \((s,c,*)\) passing through them, thus at
most \(f\) journeys in \(Q\) may not lead to the reception of the corresponding tuple by correct processes. Therefore each correct process will eventually receive at least \(f+1\) corresponding tuple among \(Q\), ensuring eventual delivery of the content \(c\).
We conclude by proving the safety of reliable communication. Let us assume that process \(p_s\) does not trigger \(\texttt{{RC.send(*, c)}}\) and that Byzantine processes multicast tuples \((s,c,P)\), thus pretending content \(c\) has been diffused by \(p_s\). Each correct peer that receives \((s,c,P)\) from a Byzantine process \(p_b\) adds the identifier \(b\) of its sender to \(P\) and then multicasts \((s,c,P \cup\{b\})\). It follows that all the tuples \((s,c,P)\) stored by correct processes contain at least one identifier of a Byzantine process in \(P\). Given that Byzantine processes are at most \(f\), the minimum hitting set size of all the received tuples associated to \((s,c)\) cannot exceed \(f\), and the claim follows. ◻
8 Intermediate Results and Missing Proofs↩︎
8.1 Authenticated Links↩︎
8.1.1 One-to-one RC in \(\langle PL, SC, AL \rangle\).↩︎
The condition provided by Maurer et al. [6] can easily be extended to consider any starting time \(j\) in the class \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\).
Theorem 11 (One-to-one RC in \(\langle PL, SC, AL \rangle\)). The one-to-one reliable communication problem can be solved starting at any time \(j\), from a process \(p_s\) to a process \(p_t\), in the perfect authenticated links* and synchronous computation setting, if and only if \(\mathcal{G} \in \mathcal{J}_{(s,t,2f+1)}^\mathcal{R}\).*
Proof. It follows from the construction of the \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\) class, extending Theorem 1, that the condition identified by Maurer et al. is verified in \(\mathcal{G}\) for any time \(j\) according to the class specification.
(Sufficient) - Lemma 2 guarantees reliable communication from \(p_s\) to \(p_t\) at time \(x\) if \(\mathcal{G}_{[x,*]} \in \mathcal{J}_{(s,t,2f+1)}\); if \(\forall j \in \mathcal{T}, \mathcal{G}_{[j,*]} \in \mathcal{J}_{(s,t,2f+1)}\) then it follows that the problem is solvable in the specific setting at any time \(j\).
(Necessary) - Lemma 1 demands \(\mathcal{G}_{[x,*]} \in \mathcal{J}_{(s,t,2f+1)}\) to achieve reliable communication from \(p_s\) to \(p_t\) at time \(x\). A second instance between the same endpoints at time \(y > x\) requires \(\mathcal{G}_{[y,*]} \in \mathcal{J}_{(s,t,2f+1)}\) to be satisfied. \(\mathcal{G}_{[y,*]} \in \mathcal{J}_{(s,t,2f+1)}\) implies \(\mathcal{G}_{[x,*]} \in \mathcal{J}_{(s,t,2f+1)}\) when \(y>x\), but the opposite relation does not hold. The claim thus follows from the definition of class \(\mathcal{J}_{(s,t,2f+1)}^\mathcal{R}\) by extending previous argument to any time \(j \in \mathcal{T}\): \(\mathcal{G}_{[j,*]} \in \mathcal{J}_{(s,t,2f+1)}\) will be required for any time \(j\). ◻
The same conditions identified in Theorem 11 are necessary and sufficient to solve one-to-one reliable communication at time \(j\), with the addition of transient failures [18].
8.1.2 Mauerer et al. protocol extension in FLL-AC.↩︎
The Maurer et al. protocol has been proven correct to support reliable communication in the PL and SC setting. In order to extend its validity to weaker scenarios with FLL and AC, we modify the first of its rules as reported in Algorithm 4, while keeping the rest unchanged. Fair-loss links do not guarantee single message deliveries but infinite deliveries in case of infinite transmissions. It follows that, after a finite number of transmission attempts for a message \(m\), \(m\) is delivered for the first time. We thus edit Algorithm 3 accordingly in order to overcome such link behavior.
Theorem 8 (One-to-one RC in \(\langle FLL / AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the one-to-one reliable communication problem can be solved starting at any time \(j\) if and only if \(\mathcal{G} \in \mathcal{J}_{(s,t,k)}^\mathcal{R}\) and \(k>2f\).
Proof. (Sufficient): We show that Algorithm 4 solves reliable communication in the considered setting. The AC assumption may delay the local compute phase on processes for an unknown but finite amount of time, namely, the execution of all three rules of Algorithm 4 and the execution of the \(\texttt{{RC.send(*, c)}}\) operation may take a non-unitary amount of time. We have from the FLL assumption that if a link is present infinitely often and a process sends a message through such a link repetitively, then such a message is received infinitely often by the link specification. It follows that if a process sends a message over an FLL link at time \(j\), and at an infinite amount of subsequent times, then such a message will be received for the first time after a finite amount of time.
Let us consider \(P\) as a path between \(p_s\) and \(p_t\) in \(\mathbb{G}\) whose edges re-appear infinitely often (its
existence is guaranteed by Theorem 5). We start by showing that if Algorithm 4 is executed and process \(p_s\) triggers
\(\texttt{{RC.send(*, c)}}\) at time \(j\), then process \(p_t\) eventually stores \((s,c,P \setminus \{t\})\) in \(\Omega_t\). The RC.send(\(*\),\(c\)) trigger at time \(j\) inserts \((s,c,\emptyset)\) to \(\Omega_s\). The AC assumption may delay such an insertion for a finite amount of time \(\delta\). Meanwhile, rule 1 is satisfied for the
entire lifetime of the system. It follows that, starting from time \(j+\delta\), \((s,c,\emptyset)\) is enqueued to be multicast at every time instant, thus for an infinite amount of times.
Again, the execution of such a rule may take an arbitrary but finite amount of time. The first edge \(e\) of P, let’s say \(\{p_s, p_r\}\), will be present infinitely often. It follows that:
(i) \((s,c,\emptyset)\) is enqueued to be sent infinitely often, and (ii) the link \(e\) will be present infinitely often. Accordingly, after a finite amount of time, \((s,c,\emptyset)\) will be received by process \(p_r\) for the first time. The argument extends till traversing all the processes in \(P\), and generalizes to
\(k\) disjoint paths of recurrent edges available in \(\mathcal{J}_{(s,t,k)}^\mathcal{R}\). For the same reasons provided in the proof of Lemma 2, the claim follows.
(Necessary): Theorem 11 states that the same class \(\mathcal{J}_{(s,t,2f)}^\mathcal{R}\) is necessary in a system model where PL and SC are assumed. The system model is weakened in the considered setting; indeed, links may lose messages, and computation may take arbitrary time. It follows that stricter necessary conditions cannot be found. ◻
Corollary 8 (One-to-one RC at time \(j\) in \(\langle FLL/AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the one-to-one reliable communication problem can be solved starting at time \(j\) if and only if \(\mathcal{G} \in \mathcal{J}_{(a,b,k)}^\mathcal{R}\) (Recurrent k-journeys from \(p_a\) to \(p_b\)) and \(k>2f\).
Corollary 9 (RC at time \(j\) in \(\langle FLL/AC, AL \rangle\)). Given a setting where either links are fair-loss, or local computation is asynchronous, or both, the any-to-any reliable communication problem can be solved starting at time \(j\) if and only if \(\mathcal{G} \in \mathcal{TC}^\mathcal{R}_k\) (Recurrent \(k\)-Temporal-Connectivity) and \(k>2f\).
Proof. (Sufficient): Theorems 8 and 9 define the enabling one-to-one and any-to-any conditions in the considered setting at any time \(j\in\mathcal{T}\); thus, the conditions hold for a specific starting time.
(Necessary): For the same argument provided in Theorem 8, the FLL and AC assumptions may not support message propagation for a limited but unknown amount of time, thus requiring the enabling condition to be verified indefinitely. ◻
8.2 Authenticated Messages↩︎
Maurer et al. [6] provided another protocol solving the reliable communication problem in the authenticated message and synchronous computation setting. The solution is provided in Algorithm 5.
The solution assumes an asymmetric encryption system is set up on the processes. Each process \(p_i\) has a private key \(priv_i\) (only known by \(p_i\)) and a public key \(pub_i\) (known by all processes). The node \(p_i\) can digitally sign a content \(c\) with the function \(sign(priv_i,c)\). Any node \(p_t\) can verify content from \(p_i\) with the function \(verify(pub_i,c,\tilde{c})\). Note that \(verify(pub_i,c,sign(priv_i,c)) = TRUE\).
![Figure 5: Maurer et al. [6] Authenticated Message Solution](/article/2503.22452/_pdflatex/hoyraqjs.png "fig:")
Every message \(m\) exchanged by the protocol has the format \((s,c,\tilde{c})\), where \(s\) is the identifier of the source of the relayed content \(c\), whereas \(\tilde{c}\) is a digital signature. Byzantine processes are able to generate messages with arbitrary fields, but they are unable to generate a valid digital signature of content \(c\) from a correct process. A correct process only accepts contents that are relayed with a valid digital signature \(\tilde{c}\), namely it accepts a content \(c\) from \(p_s\) only if it receives \(\tilde{c}\) such that \(verify(pub_s,c,\tilde{c}) = TRUE\).
References↩︎
Corresponding author: Giovanni Farina - giovanni.farina@unicusano.it
This work is dedicated to Alexandre Maurer, whose work sparked this research journey.↩︎Any definition or theorem followed by a reference has been defined or proven in that reference. All other definitions and theorems are novel to this work.
This definition has been simplified due to the absence of the latency function in the model we adopted, and has been adapted to a discrete lifetime.↩︎Notice that the reliable communication specification allows any correct process to reliable deliver a content as long as it has been sent by its source.↩︎
Note that \(S\) and \(\Omega_i\) are sets; thus, the insertion of an already-contained element does not alter them.↩︎