The essential idea of our detection is to run a clique-finding algorithm on \(\mathbf {G}\)  (summarized in Algorithm ). If we find a unique maximum clique, we declare it to be the set of honest workers; the gradients from the detected adversaries are ignored. On the other hand, if there is more than one maximum clique, we resort to the robust aggregation technique discussed in Section . Let us denote the number of distorted tasks upon Aspis detection and aggregation by \(c^{(q)}\)  and its maximum value (under the worst-case attack) by \(c_{\mathrm {max}}^{(q)}\) . The distortion fraction is \(\epsilon := c^{(q)}/f\) . Clique-finding is well-known to be an NP-complete problem [1]}. Nevertheless, there are fast practical algorithms that have excellent performance on graphs even up to hundreds of nodes [2]}, [3]}, [4]}. Specifically, the authors of [3]} have shown that their proposed algorithm which enumerates all maximal cliques has similar complexity as other methods [6]}, [7]} which are used to find a single maximum clique. We utilize this algorithm which is proven to be optimal. Our extensive experimental evidence suggests that clique-finding is not a computation bottleneck for the size and structure of the graphs that Aspis uses. We have experimented with clique-finding on a graph of \(K=100\)  workers and \(r=5\)  for different values of \(q\) ; in all cases, enumerating all maximal cliques took no more than 15 milliseconds. These experiments and asymptotic complexity of entire protocol are addressed in Appendix Section REF .
<FIGURE>