Nearly-Optimal Consensus Tolerating Adaptive Omissions:
Why is a Lot of Randomness Needed?

As mentioned earlier, we focus on the classical message-passing model in which processes are autonomous, synchronous and can exchange messages via point-to-point communication channels. The adversary corrupts and controls at most $t$ processes, causes omission failures at them, and is (full-information) strongly adaptive. In Sections 3, LABEL:sec:overview-lower and LABEL:sec:overview-randomness, we present an extended overview of the three main results and novel techniques obtained in this work; for the sake of overview, we typically assume $t=\Theta(n)$. A summary of them can be found in Table 1. In Section LABEL:sec:related we discuss the related work in more details. Section 2 presents detail formal description of the model. Sections LABEL:sec:main-algo, LABEL:sec:proof-lower and LABEL:sec:tradeoff-upper contain the full and formal analysis of our main results. Section LABEL:sec:future states major research directions opened by our work.

Not all processes are reliable. Up to some $t=O(n)$ processes may become (omission) faulty during the execution – once a process becomes faulty, it stays faulty through the end of computation and some of its incoming/outgoing messages could be lost. We assume that $t$ is a part of the problem input and thus known up-front to all processes. The decision which process becomes faulty and when, as well as the control over the faulty processes, is governed by an adversary. We consider an adaptive full-power full-information adversary that

• •

  has unlimited computational power, knows the algorithm and input parameters and can see the states (and thus also the current random bits used) of all processes, as well as the content of all arriving messages, at any time, and

• •

  can select online which (non-faulty) processes to fail and when, and with respect to faulty processes – it can omit any subset of messages incoming/outgoing to/from the faulty processes (i.e., such messages are not delivered to their destinations, having the same effect as no message sent).

Consequently, an adversarial strategy is a deterministic function, which assigns to each possible history that may occur in any execution some adversarial action for the subsequent phase of the execution, i.e., which processes to fail in that phase and in which moment and which messages sent by/to them would reach their destinations. Note, that in the above definition, the adversary has flexibility to adapt its actions between any two phases of the algorithm (not only between consecutive rounds). In the remainder, we will be referring to this adversary simply by adaptive adversary.

We remark that crash failures of processes can be viewed as omission failures – the adversary simply bans all their incoming and outgoing messages after the failure round (while in the round of a crash, the adversary could allow any subset of outgoing messages to reach their destinations).⁴⁴4In case of crashes, incoming messages are not relevant, because the faulty process could not influence correct processes any more and it is not required from them to satisfy any of the consensus properties.

A randomized algorithm for processes $\mathcal{P}=\{1,\ldots,n\}$, where each process $p\in\mathcal{P}$ holds initial input $b_{p}\in\{0,1\}$, is a consensus protocol tolerating $t$ faulty processes if all the three following conditions hold with probability $1$ in the presence of an adaptive adversary failing/controlling at most $t$ processes:

Agreement. All non-faulty processes output the same value.

Validity. If all non-faulty processes begin with the same input value $b$, then all of them output $b$.

Termination. Non-faulty processes have to decide and terminate.

Consider a randomized consensus algorithm against a fixed adversarial strategy. The following metrics determine the quality of the execution against that strategy:

• •

  Time of an execution of the algorithm is defined as the smallest number $\tau_{1}$ such that the number of rounds that occur by termination of the last non-faulty process is at most $\tau_{1}$;

• •

  The number of communication bits in an execution of the algorithm is the smallest number $\tau_{2}$ such that the total number of bits sent by all processes in point-to-point messages by termination of the last non-faulty process is at most $\tau_{2}$;

• •

  Randomness of an execution of the algorithm is defined as the smallest number $\tau_{3}$ such that the number of (independent and uniform) random bits used by all processes by termination of the last non-faulty process is at most $\tau_{3}$; when describing the lower bound result, we abuse the notation slightly, and define randomness of an execution as the total number of times when processes access their random sources during the local computation phase. Complying to the definition of the local computation phase, in each such access a process can use a sequence of random bits of finite length. Observe that such definition makes a lower bound result even stronger.

We define time/communication/randomness complexity of a (distributed) algorithm as a supremum of time, the number of communication bits, and the number of random bits, respectively, taken over all adversarial strategies.⁵⁵5Note that the supremum for different measures could be achieved by sequences of different strategies – nevertheless, each of the complexities of our solutions is still close to optimal. Finally, time/communication/randomness complexity of a distributed problem is an infimum of all algorithms’ time/communication/randomness complexities, respectively. In our paper, we are interested in studying almost-optimal solutions, i.e., optimal within a polylogarithmic factor, wrt the abovementioned complexities. The bounds on the complexities should hold with high probability. We say that a random event occurs with high probability (whp for short), if its probability could be made $1-O(n^{-c})$ for any positive constant $c$ by linear scaling of parameters of the considered random process.⁶⁶6We would like to note that, after ignoring polylogarithimic factors, all our upper bounds hold with the same asymptotic complexities in even stronger regime where the probabilities are of form $1-O(n^{\omega(1)})$.

We introduce a new partitioning of processes into operative and inoperative, based on the communication received by each process from a certain pre-defined set of other processes which maintain their operative status (this set may vary, depending on what procedure is executed – it will be emphasized later). This partition is not equivalent to the standard classification into faulty / non-faulty ones. With our partition, we can guarantee that faulty processes either communicate well enough to contribute to the progress towards a unified decision (i.e., stay operative) or become excluded from the set of operative processes, having no impact on the final decision. Our partition also avoid a major performance problem in omission-tolerant or Byzantine-tolerant computation – identifying a single faulty process may require at least quadratic number of messages, cf., [AbrahamCDNPRS19], which makes it fast, local and incorporated in efficient communication schedules.

Then, we employ the idea of reaching consensus by applying the biased-majority-voting rule, as proposed in [Bar-JosephB98], but with a novel twist – only the operative processes implement the vote protocol to agree on a consensus decision. It uses $O(\sqrt{n}\log{n})$ repetitions of the single vote subroutine, called epochs in the pseudo-code, see lines 1-1 in Algorithm 1. Each repetition/epoch consists of $O\left(\log n\right)$ rounds of communication-efficient counting, see the description below), however it succeeds in unifying the votes only if the number of newly failed processes is $O(\sqrt{n})$ and only with a constant probability (this is why we need $O(\sqrt{n}\log{n})$ epochs). Only after the part implementing the biased-majority-voting rule ends, the operative processes communicate the decision to the remaining parties. We first describe how we implement a single epoch, based on two technical advancements, and conclude with more details on how the overall consensus protocol (based on the biased-majority-voting rule) is designed.

In our case, a single epoch (i.e., a single repetition of the biased-majority-vote subroutine, lines 1-1) heavily relies on counting, collaboratively by every operative process, the number of operative processes that have candidate decision value $0$ and, separately, value $1$. These numbers must be approximate, up to an additive factor linearly dependent on the number of processes that become inoperative, as the operative status may change dynamically – some processes can lose it before the calculation finishes and, in consequence, their candidate values might not be properly counted by others. Moreover, this calculation has to consider the fact that some operative processes can be controlled by adversary, thus it must, regardless, exploit the property that the operative processes communicate with enough other processes. A protocol performing this calculation in $O(\log{n})$ rounds and using $O(n^{3/2}\log^{2}{n})$ communication bits, in total, is the main technical advancement of this algorithm and we present it next in a form of two technical advancements.

As mentioned above, there are some inherit difficulties in the omission failure model that complicate the time- and communication-efficient counting of the number of candidate values (i.e., votes) $0$ and $1$ among the operative processes. Here, we present the techniques we use to mitigate them. We pre-define fixed partition of the set of processes into $\left\lceil\sqrt{n}\right\rceil$ groups of size $\left\lfloor\sqrt{n}\right\rfloor$ or $\left\lceil\sqrt{n}\right\rceil$ each (see line 1 of Algorithm 1 and example in Figure 1), and first require the operative processes to count the number of operative $0$’s and $1$’s only within the groups (executed procedure GroupBitsAggregation in line 1). In this part, we use a virtual sparse data structure on some subsets of processes, structured into a balanced binary tree, which is used to aggregate the counts.

Vertices of the binary tree correspond to specific subsets of processes in the group: leaves of the binary tree are singletons in the group, and each vertex in a higher layer corresponds to the union of the subsets that are already identified with the children of that vertex in the tree. The root of the binary tree corresponds to the set of all processes in the group. Processes calculate the number of operative $0$’s and $1$’s, called operative counts, starting from the leaves of the tree (i.e., singletons) and then keep moving up the tree. At each vertex in a higher layer, the processes in the subset corresponding to that vertex work together to relay and sum up the operative counts from the lower layer. In this relay-and-aggregation procedure, all operative processes in the group exchange messages, not only to relay and aggregate values from children to parents in the virtual tree, but also to keep track who remains operative in the whole group. More precisely, if a process receives information from less than half of the other processes from the group, during the procedure of relaying and aggregating the operative counts of $0$’s and $1$’s from the lower layer, it becomes inoperative. See example in Figure 2. After $O(\log{n})$ rounds, corresponding to the height of the binary tree, the operative counts for the entire group – corresponding to the root of the tree – can be calculated. Complying with the rule of receiving enough number of messages in order to maintain an operative status, only the processes of the group that remain operative use the operative counts further in the protocol. In the analysis, we will be able to prove that, regardless of the omission failures’ pattern, there is a group of $\Theta(n)$ operative processes whose counts of operative $0$’s and $1$’s differ by, at most, the number of processes who have become inoperative. Taking the advantage of the binary-tree-structured communication, we can guarantee that processes of each group exchange at most $\tilde{O}(n)$ bits in total and that the procedure of operative counting $0$’s and $1$’s takes only $O\left(\log{n}\right)$ rounds. Summarizing, we prove the following result about a single execution of the procedure GroupBitsAggregation. Detailed description can be found in Appendix LABEL:subsec:comm-patterns and in Algorithm LABEL:alg:bits-agreg; the formal analysis is in Appendix LABEL:subsec:analysis-main.

After the tree-based communication, the operative processes in each group have a shared knowledge about the count of operative $0$’s and $1$’s within their group. Since there are $\left\lceil\sqrt{n}\right\rceil$ different groups, the number of logically different counts is $O(\sqrt{n})$. To exchange these $O(\sqrt{n})$ counts between the groups, the operative processes communicate along the links in a sparse, but well-connected, graph – neighborhoods of which are pre-selected locally in line 1 – that underlays the entire network; see the executed procedure GroupBitsSpreading in line 1 of Algorithm 1 and the illustration of the graph on the top of the group partition in Figure 1. The graph used by the operative processes is selected as follows. We consider a random graph, where each edge is selected independently at random with probability $\Theta(\log{n}/n)$. Next, we use the probabilistic analysis to show that the following event holds whp: a random graph with such edge density has the property that every subgraph of a constant-fraction size is dense and shallow – see Theorem LABEL:thm:random-graph-properties in Appendix LABEL:subsec:analysis-main. The “dense” property refers to the fact that removing an arbitrary but at most $\alpha$-fraction of edges incident to any vertex from a linear number of vertices, allows to find a connected subgraph of this linear number of vertices such that every vertex has degree at least $\beta\log{n}$ within this subgraph. The “shallow” property refers to the fact that the latter subgraph has logarithmic diameter (asymptotically). These two properties justify our partition into operative and inoperative classes, from perspective of the inter-group communication: as long as the process has more than $\beta\log{n}$ active links, intuitively it belongs to the connected shallow subgraph and thus it is capable of exchanging information with any other process with this property in $O(\log{n})$ rounds. This holds regardless of the factual faulty / non-faulty state of the processes. Therefore, the operative processes can spread among themselves the operative counts of the $\left\lceil\sqrt{n}\right\rceil$ different groups, yielding the property that as long as a process remains operative it knows some operative counts of any group with at least one operative process. More specifically, every operative process stores a data structure memorizing the operative counts of each of the $\left\lceil\sqrt{n}\right\rceil$ groups present in the system. Initially, it knows only the counts of the group it belongs to. In $\Theta(\log{n})$ rounds of communication it keeps sending these counts along every edge determined by the underlying graph, maintaining the fact that operative counts of a particular group are sent only once via each edge; at the same time it receives counts of other groups and updates the data structure based on this information. In case a process receives two or more different count values of some group, it can choose arbitrarily any of them – as argued earlier, all of them could differ by at most the number of processes that have become inoperative in that group. To summarize, the procedure  GroupBitsSpreading has the following outcome (the formal description is given in Algorithm LABEL:alg:bits-spread and in Appendix LABEL:subsec:comm-patterns; the formal analysis is provided in Appendix LABEL:subsec:analysis-main).

The combination of the two above technical advancements lead to calculating the number of candidate values 0 and 1 among the operative processes. Although these numbers are approximate, as they can differ by the number of processes that have become inoperative, this difference is acceptable to still employ a variant of the biased-majority-voting consensus, as we discuss in the next part.

Assuming that each operative process has the approximate numbers of other operative processes having a candidate value $1$ and $0$, we explain the modification to the consensus framework based on the biased-majority-voting by Bar-Joseph and Ben-Or [Bar-JosephB98] in order to adapt to the dynamic characteristic of the operative set of processes and to the properties that our new efficient single-epoch implementation of a voting has. Our modification takes into account that, in our case, the counts of operative $0$’s and $1$’s are not the same in every operative process. The communication protocols guarantee only that a candidate value of an operative process is accounted by any other operative process, however, it gives no guarantee regarding the candidate values of the processes that become inoperative during the calculation and communication. Also, in our implementation of a single biased-majority-voting subroutine (epoch), described earlier, the operative processes do not assign any default values to the candidate values of the inoperative processes. Thus, any operative process estimates the number of all operative processes simply by adding the operative counts of $0$’s and $1$’s. Based on the above estimates, the algorithm employs the procedure of converging the candidate values of the operative processes to the final decision value according to the following: if an operative process has an operative count of $1$’s (meaning the candidate values of operative processes assigned to $1$) at least $\frac{18}{30}$ of the estimated total of all operative processes, it sets the candidate value to 1. If the operative count is less than half of the estimated total, it sets the candidate value to 0. In all other cases, the candidate value for the next step is a uniformly chosen random bit. See lines 1-1 and Figure LABEL:fig:random-coin for an illustration.