On Time-Optimal, Fault-Tolerant Algorithms for Connected Consensus Beyond Grade Two

A central task in theoretical distributed computing is to enquire whether it is possible to achieve some agreement notion between processes that participate in a distributed system. Commonly, this task involves solving agreement problems – coordination tasks defined using a list of properties that establish how processes must decide over a set of valid values. Typically, one must fix a specific computation model with a well-defined communication mechanism between processes to formally describe the setting of such problems. Taking this into consideration, a classical model for studying agreement problems is the asynchronous model. In this model, processes communicate point-to-point via message passing over a complete network; also, there is a guarantee of the arrival of messages, yet there is no bound on their delay. In particular, we are interested in the solvability of agreement problems in such a model when we consider processes that exhibit faulty behaviour, such as crash failures or Byzantine faults.

A cornerstone result in the area is precisely the impossibility of deterministically reaching consensus in the asynchronous model if we assume the presence of even a single faulty process [18]. In order to circumvent this impossibility, different algorithmic approaches are often explored to achieve termination for consensus protocols under particular circumstances, which combine classic mechanisms such as randomisation or failure detectors with coordination primitives, which are precisely agreement problems with weaker agreement notions than consensus. Some of such primitives include adopt-commit [20], crusader agreement [13], and graded broadcast [16].

After some consideration, it is clear that the latter primitives are similar in nature: all of them depend upon the agreement on either the same or adjacent vertices of a specific kind of graph, thus, intuition suggests an intrinsic relationship between them. Recently, Attiya and Welch [11] presented an agreement problem called connected consensus. This problem effectively unifies the resolution of the three previous primitives by reaching approximate agreement on a particular class of graphs parametrised by a positive integer $R$ which is called the refinement parameter. In [15], $R$ is also referred to as the grade of the graph; hence, an alternate name for the problem is graded consensus. Moreover, the authors further generalise such primitives by extending the problem in order to accept multi-valued inputs. Furthermore, this recent problem definition also incorporates the binding property previously defined for the binary crusader agreement problem, which results helpful at limiting the decision power of malicious processes over the protocol’s final outcome.

There exist agreement problems, such as approximate graph agreement, that generalise connected consensus. Yet their known algorithms, for example [5], though capable of tolerating Byzantine failures, do not satisfy the binding property while also requiring exponential local computation. Therefore, the connected consensus problem remains a relevant research topic when we both need agreement on special-case graphs, and adversarial decision-power limitation by means of the binding property; not to mention its usefulness in works such as [15].

It is worth mentioning that, in the paper that introduced the connected consensus problem, Attiya and Welch also present algorithms for instances where the refinement parameter $R$ is either $1$ or $2$ – one for crash faults and two for malicious failures – while preserving the binding property. Additionally, the authors prove that the crash-resilient algorithm and one Byzantine-tolerant algorithm are optimal with respect to the number of communication rounds between processes. However, it remained an open question whether it was possible to devise algorithms for connected consensus instances where $R>2$, and if so, if it was possible to satisfy the binding property all the same.

Therefore, as our main contribution within this work, we present algorithms that solve connected consensus for any positive integer parameter $R$ in the presence of both crash and Byzantine failures, therefore answering the open question in the affirmative.

As a first result, we present an algorithm that is tolerant to crash failures, with $n$ being the total number of processes and $f$ the maximum number of faulty parties. This algorithm successfully solves connected consensus for any positive integer $R$ parameter. For this algorithm, we make use of an averaging approach, which allows us to quickly reduce the decision space of possible vertices that processes are able to output as a solution. We prove this algorithm optimal with respect to the maximum number of crashed processes it can tolerate; and we do so by using a fault-resilience lower bound introduced by Attiya and Welch in their seminal work, which we explain in more detail in the section dedicated to prior work. We also prove that the binding property holds in this algorithmic solution. This algorithm runs in ${\log }_{2}R+1$ rounds, hence matching the time complexity for $R=1,2$ of the previous algorithm for crash faults by Attiya and Welch, which was in turn, optimal according to the number of rounds.

Next, as a second and core contribution, we introduce a Byzantine-tolerant algorithm for connected consensus, which again manages to solve the problem for any instance with parameter $R\ge 1$. This algorithm tolerates up to Byzantine failures which, albeit suboptimal in the general case, is in fact optimal for a class of connected consensus algorithms that Attiya and Welch call uniform. For this class of algorithms, we refer to a proof presented by the authors of the connected consensus paper. This proof is discussed within the “previous work” section of this paper. Regarding this second algorithm, we take inspiration from an algorithm tool called witness technique; which originally Abraham, Amit, and Dolev [1] introduced to achieve a Byzantine-tolerant approximate agreement algorithm on the asynchronous setting.

By combining this approach with an averaging technique similar to the crash-tolerant algorithm, we are able to devise an algorithm that makes use of a reduced number of communication rounds. In fact, we are able to match the time complexity for $R=1,2$ of the fast Byzantine-tolerant algorithm proposed by Attiya and Welch; which in turn, is optimal for these two parameter scenarios.

For reference, Table 1 compares the algorithms introduces in this paper with prior work, from where it becomes clear that the algorithms introduced in this work match time-optimality from previous algorithms for $R=1,2$, while achieving for the first time solutions for positive values of $R$ beyond grade $2$. It is important to mention that both algorithms introduced in this paper work for the multi-valued input scenario; and that, as a key feature, preserve the binding property. In brief, our contributions are the following:

• $\mathrm{■}$

  We introduce a connected consensus algorithm resilient to crash failures for multi-valued inputs. This first algorithm exhibits tolerance to at most faulty processes, which is optimal using a result discussed in the next section. Also, it uses one communication round for $R=1$ and two communication rounds for $R=2$. Therefore, our Algorithm matches the time-complexity of the crash-fault algorithm introduced by Attiya and Welch for the $R=1$ and $R=2$ cases; which turns out to be optimal for these scenarios. Moreover, this algorithm achieves solutions for $R>2$ for the first time using a logarithmic number of rounds. We also show that this approach satisfies the binding property.

• $\mathrm{■}$

  As a second contribution, we provide a Byzantine-resilient algorithm with fault tolerance of and logarithmic time complexity. As with the crash-tolerant algorithm, this algorithm effectively solves connected consensus for any positive parameter $R$. In a similar fashion to the previous algorithm, our algorithm matches the time-complexity of the only known algorithm for malicious failures, also optimal for the $R=1,2$ scenarios. Regarding fault-tolerance, we rely on a preliminary result which we present in the subsequent section to argue that our approach attains the best possible resilience bound without sacrificing clarity in its implementation. Finally, we prove that the binding property holds for this second algorithm as well.

The remainder of this paper is structured as follows. In Section 4, we provide a review of the previous results known algorithms for connected results presented by Attiya and Welch, in addition, we will briefly describe the interesting witness technique, which served as inspiration for the development of the Byzantine-tolerant algorithm we present in this work. Section 2 covers the definition of the asynchronous model upon which our problem is defined. Next, Section 3 presents the formal definition of the connected consensus problem for multi-valued inputs; we define the binding property, and include several other key definitions and useful notation as well.

As the core discussion of our work, Sections 5 and 6 present the fault-tolerant connected consensus algorithms for crash and Byzantine faults respectively. Finally, we bring our work to a close in Section 8.

In this work, we consider a standard message-passing asynchronous model consisting of a set of $n$ processes. In this model, processes communicate by sending messages to one another through a complete communication network of reliable bi-directional channels. These channels are point-to-point, therefore every process is able to directly communicate with any other (including itself) within the network.

As we consider full asynchrony in our model, we assume that messages sent in the communication network have an unbounded, yet finite transit time between the instant a certain process sends a message and the moment the target process receives it.

We also consider two possible kinds of failures that processes in our model may present: crash and malicious failures. Crash failures occur when faulty parties stop taking any additional computing steps and, consequently, stop communicating with other processes in the network from a certain instant in time onwards. For this kind of failure, we assume that processes do not recover and stay silent during the remainder of the execution of any distributed algorithm. On the other hand, parties that exhibit malicious failures (also known as Byzantine failures) behave in an arbitrary manner that may be even aimed to corrupt the outcome of the algorithm for correct parties. We call any process that exhibits faults faulty; furthermore, we use the terms malicious or dishonest for a process if its faults are Byzantine. Additionally, we denote by $f$ the maximum number of parties that behave in a faulty manner in the execution of a protocol.

In our model, processes are given a particular input value $v$ at the start of their execution from a set of possible input values $V$. Furthermore, as we are interested in the decision that correct processes reach during the execution of a distributed algorithm, we also consider a particular output set from which processes end up deciding a particular value which we refer to as the output or decision of the process. If some correct process has decided a value among the output set, we say that it has decided on a value; notice that this decision may occur at any point of the execution of the algorithm.

Finally, in order to evaluate the performance of algorithms that solve the connected consensus problem, we present both time and communication measures for complexity. Take into account that we analyse complexities for the worst-case scenario of any execution. For time complexity, we adopt the same definition for asynchronous message-passing systems that Attiya and Welch use in the previous paper [11]. It is important to note that the definition used in this paper is, in turn, adopted from [9]. While this time measure is adequate for a granular time complexity analysis, for simplicity, we analyse our algorithms in terms of “rounds”. This is a time measure used likewise in the previous paper, which is directly comparable “time complexity” measure. A proper definition of this measure appears in [2]. Throughout this paper, we use the terms rounds and communication rounds interchangeably.

For communication complexity, we simply consider the maximum number of messages sent by correct processes over all the possible executions of a connected-consensus solving algorithm.

Let $V$ be a set of well-ordered values, and consider a special value $\perp \notin V$. Given a specific positive integer value $R$ which we call the refinement parameter (also grade, following [15]), we denote by $G_S(V,R)$ the “spider” graph with central vertex $(\perp ,0)$, such that $G_S$ has exactly $|V|$ paths spanning from the central vertex, each with length $R$ and having $R$ vertices different than the central vertex, labelled $(v_i,1)$ through $(v_i,R)$ for $i\in \{1,\mathrm{\dots },|V|\}$. Notice that $G_S(V,R)$ is indeed a special kind of tree, thus connected and acyclic, and that for any value $v\in V$, the vertex $(v,R)$ is a leaf.

Hence, $G_S(V,R)$ is given by the vertex set

and the edge set

Moreover, consider a subset of input values $V^{\prime }\subseteq V$ and define $T(V,R,V^{\prime })$, the minimal subtree of $G_S(V,R)$ as the induced subtree that connects the set of leaves $\{(v,R)\mid v\in V^{\prime }\}$. It is important to note that when $V^{\prime }$ consists of a singleton $\{v\}$, then the minimal subtree is a single leaf, namely $(v,R)$. Furthermore, let $I=\{(v,R)\mid v\text{ is the input of a (correct) process}\}$ be the set of leaves induced by the inputs of correct processes. We define $T(V,R,I)$ as the correct minimal subtree of $G_S(V,R)$.

Finally, let $(v,r),(v^{\prime },r^{\prime })$ be a pair of vertices of $G_S(V,R)$. We define the middle vertex of $(v,r),(v^{\prime },r^{\prime })$ as $(\perp ,0)$ if $v\ne v^{\prime }$ and and neither $v$ nor $v^{\prime }$ equal $\perp$, $(v,\lceil \frac{r+r^{\prime }}{2}\rceil )$ if $v=v^{\prime }$, and, without loss of generality, $(v,\lceil \frac{r+r^{\prime }}{2}\rceil )$ if $v\ne v^{\prime }$ and $v^{\prime }=\perp$.

Thus, we define the connected consensus problem for $V$,$R$, with each process receiving a particular input value from $V$ through the following properties:

Termination.

Each correct process must decide on a vertex of $G_S(V,R)$.

Validity.

The decision of each (correct) process must be a vertex within the correct minimal subtree of $G_S(V,R)$. It is important to note that, in particular, if all processes start with the same input $v$ (and thus $I$ is a singleton), then the vertex $(v,R)$ must be the decision for each (correct) process.

Agreement.

The distance between the vertices labelled by the decisions of all (correct) processes is at most one.

Notice that the output set for the connected consensus problem for $V,R$ is exactly the set $V_{G_S(V,R)}$, but since there is only one input value associated with each vertex of such set, a value $v\in V$ is uniquely determined from the decision of each process.

Alongside the previous requirements for the connected consensus problem, we may require yet another interesting safety condition called binding, as proposed before for the Crusader Agreement primitive [13]. Such property can be stated as follows:

Binding.

After the first (correct) process decides a vertex $(v,r)$, with $v\in V,r\in \{1,\mathrm{\dots },R\}$, the decision of every other (correct) process must be on the same branch labelled by $v$ of the spider graph.

It is noteworthy that in any execution in which the first correct process decides any vertex but $(\perp ,0)$, then the binding condition follows from Agreement; moreover, it is not difficult to deduce that the same argument holds when $R=1$.

In the full version of the paper defining the connected consensus problem [10], the authors also establish lower bounds on both fault-resilience and time-complexity for connected consensus algorithms that tolerate either crash faults or malicious behaviour. Using these bounds as a reference, Attiya and Welch proposed the only multi-valued connected consensus algorithms with the binding property to date.

In this section, we first review and formally state these lower bounds, noting that that they also hold for the algorithms that we present as the main contribution of our paper. Then, we discuss the only known connected consensus algorithms, highlighting their time and message complexity, while examining both their strengths and limitations.

Finally, we provide a brief overview of the witness technique, a recently proposed method originally applied to the closely related approximate agreement problem. This discussion is included since the technique plays a central role in the Byzantine-tolerant algorithm that we propose, which solves multi-valued connected consensus with binding for any positive integer parameter $R$.

Consider an asynchronous system with $n$ processes, out of which $f$ may crash. Recall that, following Proposition 1, $n>2f$ is required to solve connected consensus for any instance where $R\ge 1$. Taking this into consideration, we introduce in this section a connected consensus algorithm for $n$ processes that works for any positive integer refinement parameter $R$ using logarithmic time, more specifically, it uses ${\log }_{2}R+1$ communication rounds, thus matching the optimal complexity for $R=1,2$ as detailed in Proposition 2.

The central idea behind this algorithm is to note that the fault-resilience bound $n>2f$ nicely outlines a fixed number of different scenarios in which the input values of processes may be categorised in any instance of the connected consensus problem. More precisely, it turns out that there exist only three viable scenarios for any input set $V$ (Appendix A, Corollary 17). Using this result as a starting point, we devise an algorithm whose core property is the following: at the end of each round we preserve a restricted number of scenarios for the values that processes hold as their current value. We achieve this by using an averaging approach, in which processes exchange values, and compute values that lie in the average of the set of received values. In a nutshell, we initialise the current decision as a leaf on the spider graph, and we then update it as new information regarding the topology of the network is gathered.

The algorithm proceeds as follows. At the beginning of the algorithm, each process with input $v\in V$ starts with a vertex variable, initially pointing to the leaf vertex $(v,R)\in V_{G_S(V,R)}$. It is important to notice that this approach differs from the one used in the previous crash-tolerant algorithm from [11]; since we begin at leaf vertices and then work inwards, instead of first choosing a branch and then work outwards.

Afterwards, during each round labelled by $r$, every process sends its current vertex value in a message tagged with the Round_r flag. Next, each process waits for exactly $n-f$ messages for the current round, and stores the corresponding vertex values in a $W_r$ set. Then, the process computes a new vertex value for its vertex variable, based in the number of different values stored in the $W_r$ set. For any process, one out of three possible vertices is assigned to its $vertex$ variable. These vertices are either:

• $\mathrm{■}$

  A vertex $v\in V_{G_S(V,R)}$ if $W_r$ is a singleton $W_r=\{v\}$.

• $\mathrm{■}$

  A middle vertex if $W_r$ consists of exactly one pair of vertices.

• $\mathrm{■}$

  The special central vertex $(\perp ,0)$ if $W_r$ consists of more than two vertices.

As the core result behind the behaviour of the algorithm, we prove an important invariant: that at the end of any round, there exist only two possible vertices that figure as values of the $vertex$ variable of any process. Finally, after exactly ${\log }_{2}R+1$ rounds, each process decides the vertex value stored in its $vertex$ variable during the final round. By stating the previous invariant as an extended result (Appendix A, Lemma 21); we show that, at the end of the algorithm, all decided vertices lie at distance at most one in the spider graph. Hence, the agreement property holds.

As a subtle (yet important) result, we prove that for the single-input-value scenario, all processes decide the same vertex of the spider graph (Appendix A, Lemma 19). Therefore, the validity property also holds. Moreover, since the number of rounds does not depend on the input of the algorithm, termination holds.

From the previous arguments, we now present the main result regarding Algorithm 1. The complete proof of this result appears in Appendix A.

As we mentioned in the introduction, a main reason behind proposing ad-hoc algorithms for connected consensus is that achieving the binding property is not trivial in algorithms for more general families of graphs. Thus, as a fundamental result, we prove that this algorithm also satisfies such property. We state this result as follows:

The proof behind this result is also addressed in Appendix A. The intuition behind this proof is simple: we show that at the end of the first round, the $vertex$ variable of any process can only point to one vertex out of a fixed pair of vertices which is solely determined by the inputs. Therefore, the corresponding branch of the spider graph whose ends are such vertices is already determined at the end of the first round.

In this section, we outline the description of a connected consensus algorithm resilient to Byzantine failures. We take inspiration from the Attiya and Welch Byzantine-resilient algorithm with the same fault-tolerance discussed in Section 4.2, as well from the witness technique presented by Abraham, Amit, and Dolev [1], which we already discussed in the Previous Work section.

The idea of the algorithm is similar to the one used for the crash-tolerant algorithm introduced in the previous section; with the difference that we incorporate an additional mechanism to prevent malicious processes from corrupting the decision of correct processes. For this end, we rely on the use of the witness technique in each but the second round, alongside the convenient application of the reliable broadcast primitive, for which we assume a given implementation such as the one from Bracha [12].

In order to modularise the algorithm and to make the use of the two mentioned tools clear, we first define a subroutine called WitnessCollect, parametrised with a round number $r$.

This subroutine receives as additional parameters a value $v$ which will be sent to other processes, a multiset $M_r$ where values coming from other processes will be stored, and an integer set $S_r$ that will store process identifiers in order to maintain small message sizes. The subroutine proceeds as follows for round $r$: Firstly, each process sends the $v$ value alongside their identifier within a message labelled with ${\text{Value}}_r$ using reliable broadcast. Next, after receiving $n-f$ such messages (at most one per process) each process sends the set of identifiers of processes corresponding to received messages together with their identifier under the ${\text{Report}}_r$ label via reliable broadcast, while it keeps receiving ${\text{Value}}_r$ messages and storing their respective senders in the integer set. Afterwards, each process $p$ waits to receive ${\text{Report}}_r$ messages, reporting sets $S_r^{\prime }$ with $n-f$ process identifiers. If, at some given moment, a $S_r^{\prime }$ set of processes received from some process $q$ is entirely contained in the $S_r$ set of processes of process $p$, then $p$ marks $q$ as a witness and adds it to a set of witnesses. Finally, once a process has successfully collected at least $n-f$ witnesses, then it removes the $f$ largest and $f$ smallest values from $M_r$ and stops adding further values to it.

Once we have outlined the signature of the WitnessCollect subroutine, we describe in detail the behaviour of the main algorithm.

At the beginning of the algorithm (as in the crash-tolerant approach) processes with input $v\in V$ are assumed to “point” to the corresponding leaf vertex $(v,R)\in V_{G_S(V,R)}$ through a vertex variable. Next, the number of rounds to perform is determined by the refinement parameter $R$, each communication round being labelled with an integer $r$. Upon the start of each round labelled with $r$, a $M_r$ multiset and a $S_r$ set are defined. Next, the algorithm performs a different sequence of steps depending on the current round counter.

If the first round is executed (namely, if $r=1$), each process calls the WitnessCollect subroutine with the first entry of their vertex variable as the $v$ value argument. In other words, each process communicates its input value with all other processes, and waits to learn theirs. Subsequently, each process gathers input values from other processes and removes outlier values upon collecting at least $n-f$ witnesses. After removing outliers, each process sets its vertex variable to the leaf $(v,R)$ corresponding to value $v$ branch of the spider graph if the remaining values in the $M_r$ multiset are all copies of some value $v$. Otherwise, if there is more than one distinct remaining value in $M_r$, the process sets vertex to the central vertex $(\perp ,0)$. As we did for the crash-tolerant algorithm, we also show that there is a restricted number of different vertices that any correct process stores in the vertex variable at the end of the first round (Appendix B, Lemma 38). More precisely, those vertices are either $(\perp ,0)$ or $(v,R)$, with $v$ being some fixed input value coming from correct processes. In fact, this result prevents Byzantine processes from proposing invalid vertices in subsequent rounds, by fixing a branch at the end of the first round.

Next, during the second round, processes exchange the value of the branch computed during the first round: either $\perp$, or $v$. After receiving $n-f$ Branch messages, and storing the corresponding values, processes recompute their vertex value if necessary, according to the multiplicity of the values gathered in the multiset. Therefore, each process finishes the round with one out of three possible vertices in their vertex variable: either $(\perp ,0)$, $(v,1)$, or $(v,R)$. The reason behind this idea is to ensure that the branch values across all processes are consistent at the end of the round. Namely, all process point to vertices different than the central vertex within the same branch $v$. Otherwise, if some process points to the central vertex, the only other vertex that any other process may point to is $(v,1)$. This way, in subsequent rounds, processes avoid inconsistent values in their vertex variable, such as $(\perp ,1)$, which may appear if we use an averaging approach in each round. We use a result to show that these are the only two possible scenarios (Appendix B, Lemma 42).

Finally, in the remaining rounds we use the same approach as in the first round, with the only difference that processes aim to agree in the grade of their current vertex. As an important remark, we ensure that if the scenario with at least one process pointing to $(\perp ,0)$ happens, then each subsequent round preserves the property of consistent vertices. Otherwise, each round contributes in reducing the distance between vertices lying in the same branch. This approach is key to making grade values converge rapidly.

Using the previous arguments, we manage to prove that in any scenario, the vertices decided by correct processes converge to distance at most one. As for proving validity and termination, we rely on analogous arguments to those of Algorithm 1.

Hence, as our central correctness result for the Byzantine-tolerant Algorithm 1 we have the following Theorem, whose complete proof is presented in Appendix B.

Finally, to conclude this section; in the same manner as with Algorithm 1, we prove that our Byzantine-tolerant algorithm also satisfies the binding property. The full proof is presented in Appendix B, and the formal result is as follows:

Again, the proof follows a simple argument that we previously discussed while presenting the algorithm. Recall that at the end of the first round, the algorithm fixes a particular branch, namely, the one induced by the only two possible vertices $(\perp ,0)$, and $(v,R)$. As we mentioned, this particular result prevents malicious process from proposing invalid branches for the remainder of the algorithm, following the removal of outliers within the WitnessCollect subroutine.

Now, we analyse both the time and message complexities of the algorithms introduced in the previous sections. First, we do it so for the crash-tolerant algorithm, and then, we do it again for the Byzantine-tolerant one.

Before we move on to the discussion of such complexities; it is worth noting that the prior work by Attiya and Welch already introduced some useful time lower-bounds for connected-consensus algorithms when $R=2$ in the full version of the paper. We can summarise those results through the following remark:

In this work, we successfully obtained connected consensus algorithms that work for cases where the refinement parameter $R$ is any positive integer, thus filling the gap left open by the algorithms presented in the original paper for scenarios where $R>2$. We achieve this both for crash and Byzantine failures, while being driven by the goal of achieving asymptotic time-optimality in terms of communication rounds. Furthermore, in all presented algorithms we achieved the much-desired binding property, which is clearly deduced by the modular and clear nature of the algorithms. Our crash-tolerant algorithm achieves both time and resilience optimality, while using an approach that improves the $R$-round-dependant approach used by Attiya, Welch. Moreover, although this algorithm works for any positive $R$, it is self-contained in terms of employed primitives, since it relies only on basic message deliveries.

As the main contribution of this work, we provide an affirmative result concerning the possibility of achieving connected consensus in the presence of malicious faults for $R\ge 1$ via our Byzantine-tolerant algorithm, which achieves round optimality for the $R=1,2$ cases as prior algorithms did, while doing it so for $R>2$. Furthermore, although it requires $n>5f$, we deduce following the discussed result presented by Attiya and Welch that this resilience is needed given the uniform nature of the algorithm. We consider that the tradeoff between time and resilience complexity employed by our approach is justifiable in the light of the clarity and modularity achieved by our algorithm (cf. [11, Algorithm 3], which achieves fault-optimality through a significantly more complex code than the fault-suboptimal [11, Algorithm 2]). It is worth noting that concurrent work by Attiya, Flam, and Welch, presented as a DISC Brief Announcement [7] (full version [6]) also achieves a Byzantine-tolerant connected consensus algorithm for any $R$ through a reduction from the gather primitive.

As this work addresses the question of algorithmic solutions for connected consensus in any possible $R$ parametrised scenario where time-optimality is prioritised, an interesting further research direction is to inquire whether achieving fault-optimality in the presence of malicious faults justifies the intuitive required tradeoff with time-optimality. Another development is the possibility of translating the presented algorithms to models that differ from the one we used throughout this work either in communication mechanism (e.g. shared memory), timing (e.g. eventual synchrony), connectivity, or the nature of allowed faults. Finally, a possible future work is clearly the one related to find possible applications of connected consensus in different problems that benefit from the intuitive semantic behind the $R$ parameter, this is, a parametrisation of the degree of certainty (or preference) that a given process has over a proposed value. This may well include practical applications such as voting systems that quantify the trust/distrust of the participating agents, or theoretical ones that benefits from the use of variants of the commonly used crusader agreement primitive, such as [4].