Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure

The question of the optimality of the consensus algorithm performing in $\text{radius}(G,t)$ rounds in any fixed graph $G$ for every number $t\le \kappa (G)$ of failures was however left open in [4]. It was conjectured in [4] that, for every graph $G$, and for every , no oblivious algorithms can solve consensus in $G$ in less than $\text{radius}(G,t)$ rounds, but this was only proved for the specific case of symmetric (a.k.a. vertex-transitive) graphs¹¹1A graph $G=(V,E)$ is vertex-transitive if, for every two nodes $u\ne v$, there exists an automorphism $f$ of $G$ (i.e., a permutation $f:V\to V$ preserving the edges and the non-edges of $G$) such that $f(u)=v$.. Although the class of symmetric graphs includes, e.g., the complete graphs $K_n$, the cycles $C_n$, and the $d$-dimensional hypercubes $Q_d$, a lower bound $\text{radius}(G,t)$ for every graph $G$ in this class does not come entirely as a surprise since all nodes of a symmetric graph have the same eccentricity (i.e., maximum distance to any other node, generalized to include crash failures). The fact that all nodes have the same eccentricity implies that they can merely be ordered according to their identifiers for selecting the output value from the received pairs (node-identifier, input-value). Instead, if the graph is not symmetric, a node that received a pair (node-identifier, input-value) after $\text{radius}(G,t)$ rounds does not necessarily know whether all the nodes have received this pair, and thus the choice of the output value from the set of received pairs is more subtle. Not only the design of an upper bound is made harder, but it also makes the determination of a strong lower bound more involved. The main question addressed in this paper is therefore the following: For every graph $G$, and every non-negative integer , is there an oblivious algorithm solving consensus in $G$ in less than $\text{radius}(G,t)$ rounds under the $t$-resilient model (i.e., when up to $t$ nodes may fail by crashing)?

Moreover, the study in [4] let aside the design of a generic (oblivious) algorithm for solving the standard important relaxation of consensus, namely $k$-set agreement. (Recall that, in $k$-set agreement, the set of all values outputted by the nodes must be of cardinality at most $k$.) In fact, several tools developed in [4] do not extend to $k$-set agreement. Our next step is therefore to question the ability to design a generic algorithm for solving $k$-set agreement in arbitrary graphs $G$, for every $k>1$.

Last but not least, the study in [4] assumed that the number $t$ of failures is smaller that the connectivity $\kappa (G)$ of the graph $G$ at hand. We question what can be said about the case where the number of failures may be larger, that is when $t\ge \kappa (G)$, for both consensus and $k$-set agreement?

We extend the investigation of the $t$-resilient model in arbitrary graphs, in various complementary directions.

Distributed computing in synchronous networks has a long tradition, including the early studies of the message complexity and round complexity of various tasks such as leader election, spanning tree constructions, BFS and DFS traversals, etc. (see, e.g., [2, 23]). The topic has then flourished in the 2000s under the umbrella of the so-called LOCAL and CONGEST models [19, 25], with the study of numerous graph problems such as coloring, maximal independent set, minimum-weight spanning tree, etc.

Distributed computing in synchronous fault-prone networks has also a long history, but it remained for a long time mostly confined to the special case of the message-passing model in the complete networks. That is, $n$ nodes subject to crash or malicious (a.k.a. Byzantine) failures are connected as a complete graph $K_n$ in which every pair of nodes has a private reliable link allowing them to exchange messages. In this setting, a significant amount of effort has been dedicated to narrowing down the complexity of solving agreement tasks such as consensus and, more generally, $k$-set agreement for $k\ge 1$. This includes in particular the issue of early stopping algorithms whose performances depend on the actual number of failures $f$ experienced during the execution of the algorithm, and not on the upper bound $t$ on the number of failures. We refer to a sequence of surveys on the matter [5, 26, 28].

In the Byzantine case, general communication graphs were studied early on [12], and are still being investigated [20]. In the stop-fault case, on the other hand, it is only recently that this approach has been extended to arbitrary networks, beyond the case of the complete graph $K_n$ [4, 8]. Our paper is carrying on the preliminary investigations in [4], by extending them from consensus to $k$-set agreement, establishing various lower bounds including one demonstrating the optimality of the consensus algorithm in [4], and extending the analysis to the case where the number of crashes may exceed the connectivity threshold. The original work in [4] has been extended to solving consensus when links are subject to crash failures [8]. Several consensus algorithms were proposed in [8], but their round complexities are expressed as a function of the so-called stretch, defined as the number of connected components of the graph after removing the faulty links, plus the sum of the diameters of the connected components. Instead, the round-complexity of the algorithm in [4] is expressed in term of the radius, which is a more refined measure. Indeed, we show that the upper bound in [4] is tight (no multiplicative constants, nor even additive constants). The consensus algorithms in [8] however extend to the case where failures may disconnect the graph, and the task is then referred to as “disconnected agreement”. Again, the complexities of the algorithms are expressed in term of the stretch, while we shall express the complexity of our local consensus algorithm as a function of the more refined radius parameter. We actually conjecture that our local consensus algorithm is optimal (with no multiplicative nor additive constants) for all $t$, no matter whether or $t\ge \kappa (G)$. On the other hand, some consensus algorithms proposed in [8] are early stopping, but the one with round-complexity close to the stretch of the actual failure pattern is not oblivious, and it uses messages with size significantly larger than the size of the messages in oblivious algorithms.

The case of omission failures has also attracted a lot of attention. In this context, nodes are reliable but messages may be lost. This is modeled as a sequence $𝒮={(G_i)}_{i\ge 1}$ of directed graphs, where $G_i$ captures the connections that are functioning at round $i$. The oblivious message adversary model allows an adversary to choose each communication graph $G_i$ from a set $𝒢$ and independently of its choices for the other graphs. The nodes know the set $𝒢$ a priori, but not the actual graph picked by the adversary at each round). We refer to [9, 24, 29] for recent advances in this domain, including solving consensus. We also refer to the heard-of model [6, 7], which bears similarities with the oblivious message adversary model.

The case of transient failures is addressed in the context of self-stabilizing algorithms [14]. As opposed to most distributed algorithms for networks, which start from a given specific initial configuration, self-stabilizing algorithms must be able to start from any initial configuration (which may result from a corruption of the internal variables of the nodes). Under the synchronous scheduler, a self-stabilizing algorithm performs in a sequence of synchronous rounds, just that it must be able to cope with an arbitrary initial state of the system.

Last but not least, we underline the recent trend related to modeling communication between nodes (under the full-information paradigm) as a topological deformation of the input simplicial complex, and the computation (i.e., the decision of each node regarding its output value) as a simplicial map from the deformed input complex to the output simplicial complex [18]. The KNOW-ALL model [3] has been designed as a first attempt to understand the LOCAL model through the lens of algebraic topology. In particular, it was shown that $k$-set agreement in a graph $G$ known to all the nodes a priori requires $r$ rounds, where $r$ is the smallest integer such that there exists a $k$-node dominating set in the $r$-th transitive closure of $G$. A follow-up work [17] minimized the involved simplicial complexes, and extended the framework to handle graph problems such as finding a proper coloring.

The study of anonymous networks, in which nodes may not be provided with distinct identifiers, and of asynchronous communication and computing, is beyond the scope of this paper, and we merely refer the reader to [10, 11, 15, 21, 22] for recent advances in these domains, as far as computing in (non-necessarily complete) networks is concerned.

Let $G=(V,E)$ be an $n$-node undirected graph, which is also connected and simple (i.e., no multiple edges, nor self-loops). Each node $v\in V$ is a computing entity modeled as an infinite state machine. The nodes of $G$ have distinct identifiers, which are positive integers. For the sake of simplifying the notations, we shall not distinguish a node $v$ from its identifier; for instance, by “the smallest node” we mean “the node with the smallest identifier”. Initially, every node knows the graph $G$, that is, it knows the identifiers of all nodes, and how the nodes are connected. The uncertainty is thus not related to the initial structure of the connections, but is only due to the presence of potential failures, in addition to the fact that, of course, every node is not a priori aware of the inputs of the other nodes.

Computation in $G$ proceeds as a sequence of synchronous rounds. All nodes start simultaneously, at round 1. At each round, each node sends a message to each of its neighbors in $G$, receives the messages sent by its neighbors, and performs some local computation. Each node may however fail by crashing – when a node crashes, it stops functioning and never recover. However, if a node $v$ crashes at round $r$, it may still send a message to a non-empty subset of its set $N(v)$ of neighbors during round $r$. For every positive integer $t\ge 0$, the $t$-resilient model assumes that at most $t$ nodes may crash. A failure pattern is defined as a set

where $F\subset V$ is the set of faulty nodes in $\phi$, with $0\le |F|\le t$, and, for each node $v\in F$, we use $f_v$ to specify the round at which $v$ crashes, and $F_v\subseteq N(v)$ to specify the non-empty set of neighbors to which $v$ fails to send messages at round $f_v$.

A node $v\in F$ such that $F_v=N(v)$ is said to crash cleanly in $\phi$ (at round $f_v$). All the nodes in $V\setminus F$ are the correct nodes in $\phi$. The failure pattern in which no nodes fail is denoted by ${\phi }_{\mathrm{\varnothing }}$. The set of all failure patterns in which at most $t$ nodes fail is denoted by ${\mathrm{\Phi }}_{\text{all}}^{(t)}$. In any execution of an algorithm in graph $G$ under the $t$-resilient model, the nodes know $t$ and $G$, but they do not know in advance to which failure pattern they may be exposed. This absence of knowledge is the source of uncertainty in the $t$-resilient model.

The eccentricity of a node $v$ in $G$ with respect to a failure pattern $\phi$, denoted by $\text{ecc}(v,\phi )$, is defined as the minimum number of rounds required for broadcasting a message from $v$ to all correct nodes in $\phi$. The broadcast protocol is by flooding, i.e., when a node receives a message at round $r$, it forwards it to all its neighbors at round $r+1$. That is $\text{ecc}(v,\phi )$ is the maximum, taken over all correct nodes $v^{\prime }$, of the length of a shortest causal path from $v$ to $v^{\prime }$, where a causal path with respect to a failure pattern $\phi$ from a node $v$ to a node $v^{\prime }$ is a sequence of nodes $u_1,\mathrm{\dots },u_q$ with $u_1=v$, $u_q=v^{\prime }$, and, for every $i\in \{1,\mathrm{\dots },q-1\}$, $u_{i+1}\in N(u_i)$, $u_i$ has not crashed in $\phi$ during rounds $1,\mathrm{\dots },i-1$, and if $u_i$ crashes in $\phi$ at round $i$, i.e., if $(u_i,F_i,i)\in \phi$ for some non-empty set $F_i\subseteq N(u_i)$, then $u_{i+1}\notin F_i$.

Note that $\text{ecc}(v,\phi )$ might be infinite, in case $v$ cannot broadcast to all correct nodes in $G$ under $\phi$. A typical example is when $v$ crashes cleanly at the first round in $\phi$, before sending any message to any of its neighbors. A more elaborate failure pattern $\phi$ in which $v$ fails to broadcast is $\phi =\{(v,N(v)\setminus \{w\},1),(w,N(w),2)\}$ where $v$ crashes at round 1, and sends the message only to its neighbor $w$, which crashes cleanly at round 2.

The node-connectivity of $G$, denoted $\kappa (G)$, is the smallest integer $q$ such that removing $q$ nodes disconnects the graph $G$ (or reduces it to a single node whenever $G$ is the complete graph $K_n$). The following was established in [4].

Note that, in particular, thanks to proposition 1, if $v$ is correct then . Let

denote the set of failure patterns in the $t$-resilient model in which $v$ eventually manages to broadcast to all correct nodes. The $t$-resilient radius is a key parameter defined in [4]:

This section defines consensus, and survey the results in [4] regarding the round-complexity of oblivious consensus algorithms, which uses the notion of information flow graph. Note that this latter notion will be revisited, later in our paper.

The lower bound from [4] on the number of rounds for achieving consensus in vertex-transitive graphs used the core notion of information flow digraph. The (directed) graph $\mathrm{𝖨𝖥}(G,r)$ captures the state of mutual knowledge of the nodes at the end of round $r\ge 1$, assuming every node $u$ broadcasts the pair $(u,x_u)$ by flooding throughout the graph $G$, starting at round 1.

• $\mathrm{■}$

  The vertices of $\mathrm{𝖨𝖥}(G,r)$ are all pairs $(v,\text{view}(v,r,\phi ))$ for $v\in V$ and $\phi \in {\mathrm{\Phi }}_{\text{all}}^{(t)}$ in which $v$ does not crash in $\phi$ during the first $r$ rounds. Note that a same vertex of $\mathrm{𝖨𝖥}(G,r)$ can represent both $(v,\text{view}(v,r,\phi ))$ and $(v,\text{view}(v,r,\psi ))$ if $v$ has the same view after $r$ rounds in $\phi$ and $\psi$.

• $\mathrm{■}$

  There is an arc from $(u,\text{view}(u,r,\phi ))$ to $(v,\text{view}(v,r,\phi ))$ whenever $(u,x_u)\in \text{view}(v,r,\phi )$, where $x_u$ is the input of $u$.

The connected components of $\mathrm{𝖨𝖥}(G,r)$ play an important role, where by connected component we actually refer to the vertices of a connected component of the undirected graph resulting from $\mathrm{𝖨𝖥}(G,r)$ by ignoring the directions of the arcs. A node $v\in V$ of the communication graph $G=(V,E)$ is said to dominate a connected component $C$ of $\mathrm{𝖨𝖥}(G,r)$ if, for every vertex $(u,\text{view}(u,r,\phi ))\in C$ with $u\ne v$ there is a vertex $(v,\text{view}(v,r,\phi ))\in C$ with an arc from $(v,\text{view}(v,r,\phi ))$ to $(u,\text{view}(u,r,\phi ))$ in $\mathrm{𝖨𝖥}(G,r)$. The following result characterizes the round-complexity of consensus in $G$.

It was proved in [4] that, if $G$ is a symmetric graph then no node in $V$ dominates $\mathrm{𝖨𝖥}(G,\text{radius}(G,t)-1)$. Property 4 immediately implies that consensus in $G$ cannot be solved by an oblivious algorithm running in less than $\text{radius}(G,t)$ rounds under the $t$-resilient model. Their proof, however, holds only for symmetric graphs, and does not extend to general graphs.

We show that the consensus algorithm in [4] is optimal for every graph $G$, and not only for symmetric graphs. Specifically, we establish the following in Section 4.

This result was conjectured in [4], but only proved to be true for symmetric graphs. The class of symmetric graphs includes cliques, cycles and hypercubes, but remains limited. Moreover, in symmetric graphs, for every two nodes $u$ and $v$,

which implies that a naive algorithm for consensus in which every node outputs the input received from the node with smallest identifier performs in $\text{radius}(G,t)$ rounds. The fact that $\text{radius}(G,t)$ is a tight upper bound for consensus is thus not surprising for the family of symmetric graphs because, essentially, the choice of the $t+1$ nodes $s_1,\mathrm{\dots },s_{t+1}$ defined in Section 2.3.1 does not matter.

Instead, for an arbitrary graph $G$, two different nodes may have different eccentricities, which may differ by a multiplicative factor 2 at least. As a consequence, the choice of the source nodes $s_1,\mathrm{\dots },s_{t+1}$ whose input can be adopted as output by the other nodes matters, as well as the ordering of these nodes (in case a node receives the input of two different source nodes).

The algorithm from [4] for consensus in the $t$-resilient model is under the assumption that in graph $G$, that is, the number of failing nodes is (strictly) smaller than the connectivity of the graph. This assumption is motivated by the mere observation that a set of $\kappa (G)$ nodes that, e.g., fails cleanly at the very first round, might disconnect the graph $G$, preventing tasks such as consensus to be solved. We show that, by slightly relaxing consensus and set-agreement, one can still consider the case where $t\ge \kappa (G)$, in a meaningful way, in the sense that if the $t$ failing nodes do not disconnect the graph, then the standard consensus and set agreement tasks are solved.

The main issue with the notion of information flow digraph $\mathrm{𝖨𝖥}(G,r)$ as defined in [4] comes from the fact that this directed graph includes only vertices $(v,\text{view}(v,r,\phi ))$ where $v$ has not crashed in $\phi$ during rounds $1,\mathrm{\dots },r$. The main issue is related to the concept of domination, as defined in [4]. A vertex $v$ dominates a connected component $C$ of $\mathrm{𝖨𝖥}(G,r)$ if the set $\{(v,\text{view}(v,r,\phi ))\mid \phi \in {\mathrm{\Phi }}_{\text{all}}^{(t)}\}$ dominates $C$. This is too restrictive, as the correct nodes may agree on the input value of a node $v$ that has already crashed. It follows that, for some failure pattern $\phi$, the vertex $(v,\text{view}(v,r,\phi ))$ may not be present in $\mathrm{𝖨𝖥}(G,r)$ (and therefore cannot dominate any other vertices of $\mathrm{𝖨𝖥}(G,r)$), whereas the nodes that are correct in $\phi$ may agree on the input value of $v$. The characterization of Theorem 3 in [4] is therefore incorrect, even if the “spirit” of the characterization remains conceptually valid, as we shall show in this section.

To provide an illustration of the problems resulting from the original definition of information flow digraph in [4], let us clarify that this definition was aiming for capturing any subset $\mathrm{\Phi }\subseteq {\mathrm{\Phi }}_{\text{all}}^{(t)}$ of failure patterns (for instance the subset $\mathrm{\Phi }$ of failure patterns in which nodes crash cleanly), in which case only the failure patterns $\phi \in \mathrm{\Phi }$ are considered. Let us then consider the scenario displayed on Fig. 2. The graph $G$ is a 6-node path plus a universal node $v$. The set $\mathrm{\Phi }=\{\phi \}$ contains a single failure pattern $\phi$ in which $v$ crashes cleanly at the second round.

Fig. 2 displays $\mathrm{𝖨𝖥}(G,1,\{\phi \})$ and $\mathrm{𝖨𝖥}(G,2,\{\phi \})$ as defined in [4] (the direction of the arcs are omitted, each edge corresponding to two symmetric arcs). A vertex $(v,\text{view}(v,r,\phi ))$ is present in the former but not in the latter, and thus, as opposed to what one might expect since nodes acquire more and more information as time passes, $\mathrm{𝖨𝖥}(G,2,\{\phi \})$ is not a denser super graph of $\mathrm{𝖨𝖥}(G,1,\{\phi \})$ nor it includes more vertices (with larger views), as some vertices present in $\mathrm{𝖨𝖥}(G,1,\{\phi \})$ may disappear in $\mathrm{𝖨𝖥}(G,2,\{\phi \})$. In fact, node $v$ dominates $\mathrm{𝖨𝖥}(G,1,\{\phi \})$, but it does not dominate $\mathrm{𝖨𝖥}(G,2,\{\phi \})$. Therefore, when analyzing $G$ with the set $\{\phi \}$ of failure patterns using the characterization theorem in [4], consensus should be solvable in 1 round but not in 2 rounds!

We propose below a more robust notion of information flow graph (which is not directed anymore). The reader familiar with the algebraic topology interpretation of distributed computing [18] will recognize the mere 1-skeleton of the protocol complex after $r$ rounds. For the purpose of fixing the issues in [4], we introduce $\mathrm{𝖨𝖥}(G,r,\mathrm{\Phi })$ for an arbitrary set of failure patterns $\mathrm{\Phi }\subseteq {\mathrm{\Phi }}_{\text{all}}^{(t)}$.

To prove Theorem 5, we define the notion of successor of a failure pattern. Given $\phi \in {\mathrm{\Phi }}_{\text{all}}^{(t)}$, we say that a node $u$ is crashing last in $\phi$ if there exists a triple $(u,F_u,f_u)\in \phi$ (i.e., $u$ crashes in $\phi$), and, for every $(v,F_v,f_v)\in \phi$, $f_u\ge f_v$.

Note that the correct node $w$ in Definition 11 is well defined as the number of failures satisfies , where $\delta (G)$ is the minimum degree of the nodes in $G$. Intuitively, $\text{succ}(\phi ,u)$ is identical to $\phi$, except that $u$ fails at round $f_u+1$, or it still fails at round $f_u$ but sends its message to one more correct neighbor before crashing.

Note also that a failure pattern may have different successors, which depends on the choice of the node $u$ that crashes last, and on the choice of the correct neighbor $w$ of $u$ in the first and third cases of Definition 11. A correct neighbor $w$ of $u$ in Definition 11 is called a witness of the pair $(\phi ,{\phi }^{\prime })$.

Still using the notations of Definition 11, let us set $f_u^{\prime \prime }=f_u^{\prime }$ in case 1, and $f_u^{\prime \prime }=f_u$ in cases 2 and 3. At the end of round $f_u^{\prime \prime }$, there is at most one correct node with different views in $\phi$ and $\text{succ}(\phi ,u)$. The only correct node may have different views in $\phi$ and ${\phi }^{\prime }=\text{succ}(\phi ,u)$ at the end of round $f_u^{\prime \prime }$ is the witness of the pair $(\phi ,{\phi }^{\prime })$. Before applying the notion of successor to derive our lower bound, let us observe the following.