Adversarially-Robust Gossip Algorithms for Approximate Quantile and Mean Computations

Distributed computing provides a resource-efficient framework for scalable algorithms that can handle the vast amounts of data produced by the increasingly interconnected and digitalized world. Designing fast and reliable algorithms to compute aggregates, such as averages, quantiles, maxima, or minima, is one active area of research in this field. These algorithms are especially vital in the context of sensor networks and P2P networks [9, 16, 18, 20].

A promising class of distributed algorithms are gossip algorithms, which are typically simple, fast, scalable, and robust to errors. Due to this, many gossip algorithms have been developed for the aggregation of information in the real world. Their communication protocol is strikingly simple. In these algorithms, communication between nodes occurs in (synchronous) rounds – in each round, every node selects a communication partner uniformly at random from the set of all nodes and chooses to either push or pull a message from its partner. These messages are usually small – $O(\log n)$ bits, where $n$ is the total number of nodes.

Push-based and pull-based protocols each have their own unique advantages and shortcomings. In [14], the authors gave a simple, fast gossip algorithm to compute the mean and built on this to compute other aggregates, including arbitrary quantiles. The main algorithm to compute the mean is a simple yet elegant push-based protocol where each node pushes half of its current value to a random node in every round. Since such a push-protocol preserves the total sum of the values, it is not hard to see why this algorithm computes the mean, and it can be shown that it converges in $O(\log n)$ rounds with high probability. Improved algorithms that reduce the total number of messages sent were given in [3] and [13]. In [10], the authors gave a faster, elegant, and in fact optimal algorithm to compute exact quantiles in $O(\log n)$ rounds with high probability, even in the presence of random faults. Their main algorithm is a pull-based tournament-style algorithm, where each node repeatedly updates its value to the median of the values of three randomly chosen nodes. This computes an approximate median extremely quickly – in $O(\log \log n+\log \frac{1}{\epsilon })$ rounds for an $\epsilon$-approximation – and can be bootstrapped to compute exact quantiles in $O(\log n)$ rounds.

One obstacle to the real-world deployment of these algorithms is the presence of message corruptions, be they malicious or benign. In the case of some algorithms, such as the median finding algorithm in [10], they are shown to be robust to random failures, that is, where nodes fail to perform their (pull- or push-) operation. The much more challenging problem, however, lies in the design of algorithms that are also robust to – potentially adversarial – message corruption. This arguably also greatly increases their applicability in the real world. Indeed, some algorithms break completely in the presence of even a few adversarial faults in each round. This is the case for the push-protocol in [14], where if even a single node reports a value that is abnormally large, all nodes would converge to an average that is much larger than the true average. Moreover, the proof techniques used there, such as the mass preservation property, completely break down in the presence of adversarial corruption. However, a pull-based approach like the one used in [10] naturally limits the number of corrupted messages, making it a powerful paradigm to address adversarial message faults. Our algorithms additionally ensure that every node sends the same value in a given round, regardless of how many nodes pull from it in that round. This approach simplifies the problem of adversarial corruption and makes the algorithm itself simpler.

To ensure that our algorithms are suitable for realistic settings, we strive to model faults in the most general manner possible. Some fundamental questions that arise include the amount of (computational) power that a potential adversary may have or how many messages may be affected by corruptions. We need to strike a balance and allow enough power to retain a meaningful adversary, but not so much that it stifles all reasonable attempts at node communication and eliminates nontrivial results. In the following, we briefly sketch the setting, concentrating for convenience on the example of an adversary, but the model readily covers nonmalicious message corruptions.

We propose an adversary that can influence a $\beta$ fraction of the nodes in each round, which we call a $\beta$-strong adversary, see section 3 for a more formal definition. The adversary can corrupt any message pulled from the nodes under its influence in this round and can arbitrarily change their contents. We do not make any assumptions about the computational power of the adversary. This model covers the special case where the same $\beta n$ nodes are controlled by the adversary throughout all rounds (in other words, the case where there are $\beta n$ adversarial nodes).

With the introduction of such adversarial faults, it is not reasonable to ask the nodes to produce exact answers. Thus, the best that we can hope for is an approximate solution, which is exactly the type of problem we investigate. In the $\epsilon$-approximate quantile problem, the goal is to compute a value whose rank is in the interval $[(\varphi -\epsilon )n,(\varphi +\epsilon )n]$. We will start by tackling the special case $\varphi =1/2$ of computing an $\epsilon$-approximate median, and show afterwards how the problem of computing an approximation of arbitrary quantiles can be reduced to that case. We then turn to the problem of finding the (approximate) mean, which is not as robust to outliers as the median. Thus, computing the mean, even approximately, in the presence of adversarial faults is difficult, as they can sabotage any algorithm by injecting extreme outliers into the computation. The best one can hope for this $\epsilon$-approximate mean problem is therefore to find a value that is at most an additive $\epsilon M$ away from the true mean, where the values are assumed to be restricted to the interval $[0,M]$.

The scenario with $\beta n$ adversarial nodes tells us that we cannot hope for an approximation factor $\epsilon$ smaller than $\beta$. Indeed, one could simply have all the adversarial nodes reliably report an extremely large or an extremely small value, which would shift the quantiles of the “good nodes” by $\beta$, and the same scenario can be applied to the mean approximation problem as well. Hence, all our results have $\epsilon \ge \beta$ as an (implicit) assumption. In some applications – and given that a $\beta$ fraction of nodes might never output a correct answer anyway – it might be acceptable that some other nodes also hold an incorrect answer, provided this number is small enough, especially if this accelerates the algorithm in return. To investigate the possibility of trading off speed with correctness, we analyze our algorithms from the perspective of parametrized correctness, which is new in this setting. Our gossip algorithms are said to have correctness level $\gamma$ if at most $\gamma n$ nodes are storing an incorrect value (e.g. a value with rank outside $[1/2-\epsilon ,1/2+\epsilon ]$ for the $\epsilon$-approximate median problem) upon termination. Note that we can always assume that $\gamma \ge \frac{1}{2n}$, since already implies that there must be no incorrect node.

In the remainder of the paper, we say that an event $ℰ$ occurs with high probability (w.h.p.) if $\mathbb{P}\left[ℰ\right]=1-n^{-\mathrm{\Omega }(1)}$. Our first main result gives a fast and robust algorithm for estimating the median. The pseudocode can be found in Algorithm 1 and is complemented by the runtime and correctness guarantees provided in our first theorem.

Next, we investigate the problem of approximate quantiles, where the objective is to compute an $\epsilon$-approximate $\varphi$-quantile, i.e. the $\lceil \varphi \rceil$-th smallest value. Notice that it suffices to first transform the values of the nodes such that an $\epsilon$-approximate $\varphi$-quantile in the original setting is the same as an $\epsilon$-approximate median in this new setting. Our next main result allows for adversarially robust quantile shifting, which along with our previous result yields an adversarially robust algorithm to approximate quantiles. The pseudocode of the quantile shifting algorithm is provided in Algorithm 2, the corresponding runtime guarantees are given in the theorem below.

Next, we investigate the approximate mean problem with $M$-bounded values. Here, every node is initially given a value in the range $[0,M]$ (where $M$ is polynomially bounded in $n$), and the problem is to find the mean of the values up to an additive error of $\epsilon M$. In this setting, we provide the following adversarially robust result for computing approximate means. The pseudocode for our algorithm is given in Algorithm 3, its runtime and correctness guarantees are stated in the subsequent theorem.

We note that the approximation here is weaker as it depends on the promised bound on $M$. The reason for this is simple: the adversary can always claim to have a value that is very large, and this would inevitably skew the computed average to a very large value. Thus, the best one can hope for is to give an error bound as a function of a bound on the possible communicated values.

Note that in the special case where all nodes have values in $\{0,1\}$, the above yields an approximate counting algorithm with an additive error of at most $\epsilon n$.

Finally, we prove the following theorem, which can be used to lower-bound the round complexity of gossip algorithms in the presence of adversarial nodes.

We also extend the $\mathrm{\Omega }\left(\log \log n+\log \frac{1}{\epsilon }\right)$ lower bound given in [10] to an $\mathrm{\Omega }\left(\log \log \frac{1}{\gamma }+\log \frac{1}{\epsilon }\right)$ lower bound in our setting, see Proposition 5 in section 8. These results prove that our median and quantile algorithms have optimal round complexity and the mean algorithm has almost optimal round complexity. We note that our theorems require varying upper bounds of $\beta$ in terms of $\epsilon$. As mentioned in the introduction, it is not possible to hope for $\epsilon$-approximation with $\beta >\epsilon$, as in particular all adversarial nodes might always output values that are completely out of the range of the correct values. Our analysis here is likely not tight and we did not optimize these bounds since our algorithms already cover a substantial range of values. The same holds for the upper bound on $\epsilon$ in Theorem 2. For lower bounds of $\epsilon$, note that any would yield an exact algorithm, which is out of reach due to the presence of the adversary. Hence a lower bound which is inversely polynomial in $n$ follows naturally, where again we did not optimize for the precise exponent, and simply stated what was required for our analysis in order to prove concentration of the expected behavior of the algorithms. However, the key reason why we do not view this restriction as major is a different one: For many applications, approximation factors that are a small constant fraction are completely sufficient. Moreover, this is also the parameter range in which our algorithms are extremely fast. More concretely, when both $\epsilon$ and $\gamma$ are constant, our algorithms are guaranteed to terminate in constant time, no matter how large $n$ is.

We summarize our results in Table 1.

We consider a network of $n$ nodes that are all connected to each other (one can think of it as a complete graph on $n$ vertices). For all the problems that we study, each node is initially assigned a value that is polynomially bounded in $n$. Communication occurs in synchronous rounds, during each of which every node contacts some node chosen uniformly at random (including itself) and then either pushes or pulls a message – of size $O(\log n)$ bits – from the chosen node. As mentioned before, all our algorithms use the pull operation only, and the message sent out by a pulled node is the same, no matter which (and how many) nodes are pulling from it.

In every round, the messages sent out by at most $\beta n$ of the nodes can become corrupted. More precisely, we assume that these corruptions can be adversarial in the following sense: At the beginning of each round, the adversary can choose at most $\beta n$ nodes so that any message pulled from or pushed to these nodes can be entirely and arbitrarily modified by the adversary, that is, the message can be changed to whatever the adversary wants. Crucially, the adversary does not know beforehand the random choice of partners of the nodes in this round. We do not assume any additional restrictions on the adversary. For example, the adversary may have unbounded computational power and know the entire history of the algorithm at any given moment of time.

Before describing our new adversarially-robust algorithms, we briefly describe the state-of-the-art in the non-adversarial setting. The approximate median find algorithm given by [10] uses a pull-based tournament-style protocol. Here, every node repeatedly updates its value to the median of three randomly chosen node values. The effect is that after $O\left(\log \log n+\log \frac{1}{\epsilon }\right)$ rounds, every node has communicated directly or indirectly with $\log n/{\epsilon }^2$ other nodes. Notice that the problem becomes straightforward with large message sizes, as every node can collect all the information about every node it has directly or indirectly heard from, and $\log n/{\epsilon }^2$ many uniformly randomly chosen node values are sufficient to prove the concentration of the median value for this node. As the authors show, we do not need to store all such information, and we can make do with just maintaining the median. Their algorithm then concludes with a majority vote over a constant number of nodes to allow for a union bound.

Our algorithms retain the simplicity of these previous algorithms with minor changes while being robust to adversarial corruptions. Some of the crucial changes include giving a more nuanced termination condition which takes into account $\beta$ and $\gamma$, and deriving tailored bounds on expressions involving binomial coefficients to bound the effect of the adversaries on each round. We also introduce an extended second phase – now collecting values from $O\left(\frac{\log (1/\gamma )}{\log (1/\beta )}\right)$ many nodes – to ensure that at most a $\gamma$ fraction of the nodes are storing an incorrect value upon termination, as desired.

More specifically, for the approximate median computation, as outlined above, we first let the nodes conduct a 3-tournament, that is, in the first phase, each node pulls three node values uniformly at random and updates its own value to the median of the three. In the second, additional, phase, the algorithm then uniformly samples a number of nodes and outputs their median. The pseudocode for our approximate median algorithm is given in Algorithm 1.

To compute approximate quantiles $\varphi$, [10] gives another tournament-style algorithm which reduces the problem to that of finding an approximate median. Our algorithm is based on their ingeniously simple algorithm. Its basic principle can be described in one sentence: In each round, each node pulls two node values uniformly at random and updates its value to be the minimum (if ) or maximum (if $\varphi >1/2$) of the two. Our algorithm here requires a more refined tracking of its own progress and knowing when to terminate, taking into account the magnitude of the potential corruption, which we measure in terms of $\beta$. This also greatly affects the required analysis. The pseudocode for our quantile shifting algorithm is given in Algorithm 2 (for the case ).

To compute the approximate mean, [14] gives the elegant push-sum algorithm, which works roughly as follows: In each round, every node pushes half of its value to another node which is chosen uniformly at random. After $O\left(\log n+\log \frac{1}{\epsilon }\right)$ rounds, the algorithm converges to an approximate solution. The authors use a crucial property of this push-based protocol, mass preservation, to show that the sample variance of the values decreases exponentially, while the sample mean remains more or less unchanged.

As discussed before, the mass preservation property breaks down in the presence of adversarial corruption. Additionally, push-based protocols are not ideal as adversarially corrupted nodes gain a significant amount of influence by pushing faulty values to an arbitrary number of nodes (unless we restrict their power). Moreover, pull-based approaches generally work better than push-based ones in the presence of adversarial faults, as they inherently restrict the influence that adversarial corruptions can have. We adopt a novel approach and design a tournament-style algorithm, but use, however, a similar proof technique as in [14], despite the absence of mass preservation. The algorithm itself is very simple – each node repeatedly updates its value to the average of two node values chosen uniformly at random. Finally, we also end with a majority vote, as in the approximate median algorithm, to ensure that at most a $\gamma$ fraction of the nodes output a wrong answer. The pseudocode of our adversarially robust mean approximation algorithm can be found in Algorithm 3.

We highlight the trade-off between the tournament-style aggregation in the first phase and the sequential collection of values for the majority vote in the second phase. Though the former is more efficient, it also gives the adversary more (exponentially more in fact) influence over the values.

There are a variety of directions for follow-up work. In terms of other aggregation tasks, beyond computation of median, other quantiles, and mean, the main open problem which may robustly be solved in our setting is the computation of the mode (since there is no hope for computing the minimum or maximum value in the presence of adversaries). We also think it would be interesting to investigate the model in the asynchronous setting or relax the assumption that communications occur on an underlying complete graph.

The Gossip Protocol is also known as the Epidemic Protocol, as these algorithms were first developed to mimic the spread of epidemics [4]. One of the first gossip algorithms studied was rumor spreading or randomized broadcast [12, 19], where in [12] the authors give an algorithm for rumor spreading in $O(\log n)$ rounds and $O(n\log \log n)$ messages.

In [14], the authors study a gossip protocol to compute aggregates such as sums and counts in $O(\log n)$ rounds. Furthermore, they also develop algorithms for random sampling and quantile computation (also known as randomized selection), the latter of which can be computed in $O({\log }^{2}n)$ rounds. The work in [10] improves that and gives an algorithm to compute exact quantiles in $O(\log n)$ rounds and approximate quantiles in $O\left(\log \log n+\log \frac{1}{\epsilon }\right)$ rounds. The problem of computing quantiles has also been studied in the centralized setting [2] and the distributed setting [15]. Other problems such as computing the mode [8] (also known as plurality consensus), have also been studied in the gossip setting.

In both [1] and [12], the authors investigate a gossip-based rumor spreading in the presence of adaptive failures, but the adversary here only has the power to crash certain messages and cannot send altered messages (which is much more powerful). To the best of our knowledge, this is the first time a gossip model has been investigated for general aggregation problems in the presence of adversarial nodes. We note that for the special case of median computation, restricting the adversarial influence to $\beta \le \frac{1}{n^{1/2}}$, the authors of [5] derive a runtime bound of $O(\log n\log \log n)$ for the computation of an approximate median from their approach to the stabilizing consensus problem. In this special case, at the cost of an additional factor of $O(\log \log n)$ compared to our runtime, they get an approximation factor of $O\left(\frac{{(\log n)}^{1/2}}{n^{1/2}}\right)$, thus yielding a tighter approximation than provided by our Theorem 1, which stipulates that $\epsilon =\mathrm{\Omega }(\frac{1}{n^{0.0019}})$. We note that we did not try to optimize the exponent in this lower bound on $\epsilon$. We note that Byzantine-robust gossip algorithms have been widely studied in the context of decentralized machine learning [11], [6], [7].

In the deterministic setting, the approximate median computation in the presence of byzantine nodes has been studied [21]. The algorithm presented there was shown to produce an approximation factor of at most $\frac{\beta }{2}$ and runs in time $O(\beta n)$, as long as . The latter requirement on the fraction of adversarial nodes was proven to be tight. This was later generalized to approximate the $k$ -th largest values in the presence of Byzantine nodes [17].

In this section, we sketch the ideas behind our median approximation algorithm and the proof of its correctness and runtime guarantees stated in Theorem 1.

The algorithm, which draws on ideas from [10], is described in Algorithm 1, and proceeds in two phases. In the first phase, every iteration consists of $3$ rounds. More concretely, in every iteration, each node pulls the value of three random nodes and updates its value to the median of these three values. In the second phase, every node obtains $K$ many independent samples and outputs the median of these $K$ values.

We consider the sets of nodes whose quantiles lie in $[0,\frac{1}{2}-\epsilon ),[\frac{1}{2}-\epsilon ,\frac{1}{2}+\epsilon ]$ and $(\frac{1}{2}+\epsilon ,1]$ at the end of iteration $i$ in line $7$ of Algorithm 1, and call these sets $L_i,M_i,H_i$ respectively. Additionally, we also define $l_i$ to be such that $l_0≔\frac{1}{2}-\epsilon$ and $l_{i+1}≔{\overline{B}}_{3,1}(l_i+\beta )=3{(l_i+\beta )}^2-2{(l_i+\beta )}^3$.¹¹1${\overline{B}}_{3,1}(l_i+\beta )$ is defined as $1-B_{3,1}(l_i+\beta )$ with $B_{n,k}(p)$ the Cumulative Distribution Function of the binomial distribution with parameters $n,k,p$. For details, see the Appendix. These values capture the expected values of $\frac{|L_i|}{n}$ as we will show later. We remark that $H_i$ and $L_i$ behave symmetrically, hence without loss of generality, we focus on bounding $|L_i|$ in the following proof. In the end, we use this symmetry to infer matching bounds for $|H_i|$.

In this section, we give some intuition underlying our quantile shifting algorithm and the proof of its correctness and runtime guarantees given in Theorem 2.

Note that we can assume $\varphi \le 1/2$ without loss of generality, as the algorithm and analysis are exactly symmetric for the other case.

The pseudocode for our algorithm is described in Algorithm 2. We consider the sets of nodes whose quantiles lie in $[0,\varphi -\epsilon ),[\varphi -\epsilon ,\varphi +\epsilon ]$ and $(\varphi +\epsilon ,1]$ at the end of iteration $i$ of the while loop and call these sets $L_i,M_i,H_i$ respectively. We want to show that $|L_i|$ and $|H_i|$ decrease rapidly as the algorithm progresses.

The values $h_i^{\prime }$ in Algorithm 2 determine when the algorithm terminates, and will also be helpful for the analysis. We define another quantity recursively as

which we will use for the analysis as well. As will be shown later, the values $h_i,h_i^{\prime }$ capture the expected values of $\frac{|H_i|}{n}$.

In this section, we give a proof sketch for the runtime and correctness guarantees of our adversarially robust approximate mean algorithm stated in Theorem 3.

The pseudocode is described in Algorithm 3. In the first phase of the algorithm, in each round, every node $u$ samples two nodes and updates its value to their arithmetic mean. Samples of node value that exceed the acceptable value interval $[0,M]$ are cut to the interval limits. In the second phase, the algorithm globally samples a set of nodes uniformly at random and outputs the median value of these nodes. Let $x_v(t)$ denote the value $x_v$ stored in the node $v$ at the end of iteration $t$. Additionally, let us denote by $V$ the set of all nodes.

To help analyze the progress of the algorithm, we define the potential function.

where the sum covers all subsets of $V$ of size $2$ (that is, we do not double-count the pairs). Notice that this potential captures the variation in the values stored in the nodes. As the algorithm progresses, we expect the potential to decrease to a small value as the values stored in the nodes converge to the average. We also define the quantity $\psi (t)≔{\sum }_{u\in V}{x}_u(t)$ as the sum of the node values. Notice that $\frac{\psi (0)}{n}$ is the true average that we want to approximate.

In this section, we prove Theorem 4, which yields a general tool for calculating the lower bounds for the round complexity of gossip algorithms in the presence of adversaries. In essence, the theorem quantifies a lower bound on the number of rounds needed for all but a $\gamma$ fraction of the nodes to produce a correct answer, in the presence of $\beta n$ adversaries. Note that a similar lower bound was proven for the non-adversarial setting in [10], but its proof does not extend readily to our case because our parametrized notion of correctness allows a $\gamma$ fraction of nodes to be incorrect in addition to the $\beta n$ adversarial nodes. However, what remains true is that even with the slack provided by $\gamma$, a correct algorithm cannot terminate in fewer than $\mathrm{\Omega }\left(\frac{\log (1/\gamma )}{\log (1/\beta )}\right)$ rounds, since up to this point, more than a $\gamma$ fraction of nodes will have communicated only with bad nodes. Therefore, they will have received no accurate information whatsoever and could not possibly output the correct result. This is formalized in Theorem 4.