Computing in a Faulty Congested Clique

Without further restrictions on the adversary, it may fail a node at the very first round of the algorithm, preventing the others from ever completing the computation since they can never access the failed node’s input. Note that loss of information is not allowed since the output may depend on the original inputs, as opposed to some other fault models that allow the output to depend only on the inputs of non-faulty nodes. Thus, the $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model must allow at least one initial quiet round, in which no faults can occur. We therefore consider the number of quiet rounds that are needed for a $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ algorithm as an additional complexity measure which we aim to minimize. We emphasize that our method will require a very small constant number of quiet rounds. This does not render the model trivial for any task which can be solved in $O(1)$ rounds in the non-faulty $\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model, because if its exact complexity is larger than our constant then it cannot be entirely executed during the quiet rounds (also note that we do not modify the bandwidth by any constant, but rather we stick to a certain given bandwidth of $b\log n$ bits, as we cannot change the communication model based on the task that we wish to solve).¹¹1[5] work with already-coded inputs and thus avoid the notion of quiet rounds. Here, we care about how the input is coded and hence we need these constant number of preprocessing rounds.

Similarly, the adversary can fail a node at the end of the computation, preventing its output from being accessible. Thus, in the $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model, the output requirement is modified. Yet, some care should be taken when doing so. We denote by ${𝒜}_w$ the output that node $w$ should hold in a non-faulty execution of $𝒜$, and we would like to require that for every node $w$ there is a node $u$ which holds ${𝒜}_w$. However, this is still insufficient because the adversary may now fail $u$. Instead, we demand that for every $w$, the output ${𝒜}_w$ is encoded in the network such that any node $u$ can obtain it within some number of $R$ rounds of communication, even if additional nodes fail, as long as $u$ itself does not fail. We call this the decodability complexity of the algorithm. Thus, a $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ algorithm has three complexity measures: the number of quiet rounds, the number of additional (not necessarily quiet) rounds, and the number of rounds required for obtaining an output.

Our contribution is a method for computing in the $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model that yields the following. First, a simplified usage of it gives that any task that has $O(n\log n)$ bits of input per node can be solved in $\tilde{O}(n)$ rounds in the $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model, for constant $c$ (our results hold for larger values of $c$ as well, with the actual dependence on $c$ being polynomial in $c$). This nearly matches the upper bound of linear round complexity of computing such tasks in the non-faulty $\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model, and is similarly obtained by learning all the inputs.

Second, our main result improves upon this greatly for computing certain functions $f$: To this end, we identify two particular parameters which, informally, capture the locality of communication and the locality of computation that a certain computation requires, and show that our result obtains a super-fast computation of functions for which these parameters are not large (see Section 2 for formal definitions). For such functions, the complexity overhead of our approach can be as low as $\tilde{O}(1)$ for a constant $c$. This insight is what allows us to compute the semi-ring product of two matrices, whose complexity in the $\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model is $O(n^{1/3})$ due to [9], in $\tilde{O}(n^{1/3})$-rounds in the $\mathrm{𝖥𝖺𝗎𝗅𝗍𝗒}\mathrm{𝖢𝗅𝗂𝗊𝗎𝖾}$ model.

The existence of a code with these parameters ($d=N-K+1$) is a classical result in coding theory; in particular, since $q\ge n$ (i.e., since the field size is bigger than the length of the code) we have that the classical construction of Reed-Solomon codes suffices. See Section 6.8 of [37] or Section 5.2 of [31]. $◀$

We construct $𝒜$ as follows:

1. 1.

   We associate node $w$ with the gates in part $P_{0,w}$. In the first $O(1)$ quiet rounds, the nodes shuffle their data so that each node $w$ holds the inputs to its gates. This is possible by Lenzen’s routing scheme [36].

2. 2.

   In the subsequent $c=O(1)$ quiet rounds, each node $w$ encodes all of its input and sends a coded piece to each of the other nodes, as follows: denote by $\mathrm{Enc}(\mathrm{\_})$ multiplication on the right by the $K\times n$ generator matrix corresponding to the code given by Lemma 14, and define the codeword ${\tilde{P}}_{0,w}=\mathrm{Enc}(P_{0,w})\in {𝔽}_q^n$. Note that the total number of bits in a codeword is at most $cn|\mathrm{\Sigma }|$, since the size of the input of each node is $n|\mathrm{\Sigma }|$ and the first layer is the identity function by Definition 8. We refer to the action of encoding the output wires of a part and splitting the pieces of the codeword to all nodes as checkpointing this information. Thus, at this point, all nodes have checkpointed the 0-th layer of the circuit.

3. 3.

   We now recursively describe the method by which the nodes use the checkpointed values ${\tilde{P}}_{\mathrm{\ell },w}^{(k)}$ of a layer $\mathrm{\ell }$ to compute the values in $P_{\mathrm{\ell }+1,w}$ and then checkpoint them (but notice that from this point on, we are not guaranteed to have quiet rounds). The method of collecting coded checkpoints can be thought of as filling out “bingo cards”, which represent the tasks of possibly faulty virtual nodes; in particular, we now have that the data of node $w$ lives “up in the cloud” and obtaining data from $w$ is replaced with obtaining coded pieces from the entire network.

   1. i.

      Communication. Assume that the nodes have checkpointed all of the data from the previous round so that every node has a coefficient of the codeword ${\tilde{P}}_{\mathrm{\ell },v}^{(k)}:=\mathrm{Enc}(P_{\mathrm{\ell },v}^{(k)})\in {𝔽}_q^n$, where $k\in [h{n}^{\zeta }]$ (so there are $h{n}^{\zeta }$ codewords of length $n$). The reason that there are $h{n}^{\zeta }$ such codewords is because $n^{\zeta }$ is the computation locality (see Definition 10). In particular, node $u$ has the value ${({\tilde{P}}_{\mathrm{\ell },v}^{(k)})}_u\in {𝔽}_q^n$.

      Each node $w$ collects the pieces

      $$\widetilde{\mathrm{bin}}(P_{\mathrm{\ell }+1,w}):=\{\mathrm{Enc}(P_{\mathrm{\ell },v}^{(k^{\prime })})\mid P_{\mathrm{\ell },v}^{(k^{\prime })}\in \mathrm{bin}(P_{\mathrm{\ell }+1,w})\}$$

      (1)

      that they need for computing the gates contained in their part $P_{\mathrm{\ell }+1,w}$, where $k^{\prime }\in [h^{\prime }{n}^{\xi }]$ because $n^{\xi }$ is the communication locality (see Definition 10). In particular, $w$ collects $P_{\mathrm{\ell },v_1}^{(k_1)}$ in a first set of $c$ rounds, $P_{\mathrm{\ell },v_2}^{(k_2)}$ in a second set of $c$ rounds, …, and $P_{\mathrm{\ell },v_{h^{\prime }{n}^{\xi }}}^{(k_{h^{\prime }{n}^{\xi }})}$ in a $h^{\prime }{n}^{\xi }$-th set of $c$ rounds, where $h^{\prime }$ is the constant in the definition of communication locality. Therefore, this takes $O(c{n}^{\xi })$ rounds.

   2. ii.

      Computation. If for every part $P_{\mathrm{\ell },w}$ in this layer, all output wires go to the part $P_{\mathrm{\ell }+1,w}$ in the next layer (and not to any $P_{\mathrm{\ell }+1,v}$ for some $v\ne w$), we call this layer a computation layer. Otherwise, we call the layer a communication layer.

      If $\mathrm{\ell }$ is a computation layer, the node $w$ performs the computation corresponding to the gates in $P_{\mathrm{\ell }+1,w}$ locally. The node $w$ continues to do these computations locally until there is a layer $\tau :=\mathrm{\ell }+t$ for some $t$, in which either there is an output wire that goes from a part $P_{\tau ,w}$ for some $w$ into a part $P_{\tau +1,v}$ for some $v\ne w$ (that is, $\tau$ is a communication layer), or $\tau$ is the output layer. The round complexity of this step is 0, because these are all local computations.

   3. iii.

      Checkpointing. Upon arriving at some communication layer $\tau$, each node $w$ checkpoints and sends each node $u$ the value ${({\tilde{P}}_{\tau ,w}^{(k)})}_u:={(\mathrm{Enc}(P_{\tau ,w}^{(k)}))}_u\in {𝔽}_q^n$ for $k\in [h{n}^{\zeta }]$ (since $n^{\zeta }$ is the computation locality). Checkpointing a code with these parameters requires $O(c)$ rounds, since we have $n$ symbols of size $\log q=O(cb\log n)$ bits. Thus, this completes in $O(c{n}^{\zeta })$ rounds.

      We refer to a non-faulty execution of steps (i)-(iii) as an epoch. We have that the complexity of these steps is $O(c(n^{\zeta }+n^{\xi }))$.

   4. iv.

      Repeat/Fill out Missing Bingo Cards. If all of the parts in a layer have been checkpointed, then the nodes move on to the next epoch; otherwise, they divide the work of the failed nodes and simulate the computations of the gates in their parts until all are checkpointed. In particular, if $F$ nodes failed so far, and of those $F$, there are $F^{\ast }$ nodes whose parts are yet to have been checkpointed, the $n-F$ non-faulty nodes evenly divide themselves and simulate those $F^{\ast }$ parts by rerunning steps (i)-(iii). This is done as follows.

      1. a.

         If $F^{\ast }>n-F$, then each of the $n-F$ non-faulty nodes is assigned to one failed node whose part has not been checkpointed yet, and repeats steps (i)-(iii) for that part.

      2. b.

         Otherwise, there are $F^{\ast }\le n-F$ such parts $P_{\tau ,v_1},P_{\tau ,v_2},\mathrm{\dots },P_{v_{F^{\ast }}}$. We batch these into sets of size at most $6c$, and let each batch be simulated by multiple nodes, as follows. We denote $F_{batch}^{\ast }=\max \{\lfloor F^{\ast }/3c\rfloor ,1\}$, and $mult=\lfloor \frac{n-F}{F_{batch}^{\ast }}\rfloor$. We denote by $x$ the remainder when dividing $n-F$ by $F_{batch}^{\ast }$ (thus, $mult=\frac{n-F-x}{F_{batch}^{\ast }}$). The non-faulty nodes, $w_0,\mathrm{\dots },w_{n-F}$, are split into $F_{batch}^{\ast }$ batches:

         $$R_{\{v_0,v_1,\mathrm{\dots },v_{3c-1}\}}:=\{w_0,\mathrm{\dots },w_{mult-1}\},$$

         $$R_{\{v_{3c},v_{3c+1},\mathrm{\dots },v_{6c-1}\}}:=\{w_{mult},\mathrm{\dots },w_{2mult-1}\},\mathrm{\dots },$$

         $$R_{\{v_{\left(F_{batch}^{\ast }-1\right)3c},v_{\left(F_{batch}^{\ast }-1\right)3c+1},\mathrm{\dots },v_{F^{\ast }-1}\}}:=\{w_{(F^{\ast }-1)mult},\mathrm{\dots },w_{n-F-x}\}$$

         Notice that since $F_{batch}^{\ast }$ is defined using the floor of the respective ratio, the size of the last batch may be larger than $3c$, but it is at most $6c$. Further, in case $F^{\ast }$ is less than $3c$ then there is only one batch, which may also be small, but it is assigned to all non-faulty nodes. For each batch, every node in that batch is assigned to each $v_j$ in the batch, and repeats steps (i)-(iii) for the corresponding part $P_{\tau ,v_j}$.

      We call each iteration of these steps an attempt. If all of the parts have been checkpointed and $\tau$ is the output layer, then the algorithm halts. Note that additional failures can occur throughout repeating. Also, we stress that although the algorithm describes exchanging messages between any two nodes, whenever it attempts to send (receive) a message to (from) a failed node, such a message is not delivered.

      The complexity of this step is equal to the complexity of $O(c(n^{\zeta }+n^{\xi }))$ rounds for steps (i)-(iii), plus an additive overhead of $O(c{n}^{\zeta })$ rounds which corresponds to the rounds needed to decode the information corresponding to the node that is being simulated. In case (b), since the size of a batch is $O(c)$, this introduces an overhead of $O(c)$ over that round complexity, for a total of at most $O(c^2(n^{\zeta }+n^{\xi }))$ rounds per attempt. The number of attempts is bounded in what follows.

It is immediate from the construction that the algorithm produces the output of the circuit. Further, it is straightforward that the number of quiet rounds is $O(1)$.

We prove that $R$-decodability holds by induction, with $R=O(c{n}^{\zeta })=O(n^{\zeta }$ for all epochs except the last, and $R=O(c{n}^{\mu })=O(n^{\mu })$ for the last. The base case is straightforward because the computation takes place through quiet rounds: at the end of step (1), each node holds the inputs to its gates. In step (2), each node encodes its input using the code in Lemma 14, and thus $R$-decodability holds with $R=O(c)=O(1)$. For the the inductive hypothesis, assume that epoch $\mathrm{\ell }$ has been correctly checkpointed as at most $O(n^{\zeta })$ codewords of an ${[n,\frac{n}{c},\frac{c-1}{c}n+1]}_q$-code for each node. Then, by the inductive hypothesis, we have that a node can, in $O(n^{\zeta })$ rounds, obtain all of the checkpointed data it needs and then perform its local computations, and simulate any failed nodes. Thus, at the end of step 3(iv), which we show below that it indeed checkpoints the computation of all nodes (also faulty nodes), we have that epoch $\mathrm{\ell }+1$ is correctly checkpointed as at most $O(n^{\zeta })$ codewords of an ${[n,\frac{n}{c},\frac{c-1}{c}n+1]}_q$-code for each node. Thus, $R$-decodability holds with $R=O(c{n}^{\zeta })=O(n^{\zeta })$. For the last epoch, we only need to encode the output and therefore we get $R$-decodability with $R=O(c{n}^{\mu })=O(n^{\mu })$.

It remains to bound the number of attempts needed for step 3(iv), which will also prove that indeed it checkpoints the computation of all nodes (also faulty nodes). For an attempt, recall that we denote by $F$ the number of nodes that failed so far (and thus the number of non-faulty nodes is $n-F$), and by $F^{\ast }$ the number of parts that are yet to be checkpointed. Let $F^{\prime }$ be the additional number of nodes that fail throughout this attempt. We consider the two possible cases, depending on how $F^{\ast }$ relates to $n-F$.

In the first case, recall that if $F^{\ast }>n-F$ then each of the non-faulty nodes is assigned to one failed node whose part has not been checkpointed and repeats its computation. Since there are at least $n/c$ non-faulty nodes even despite the additional $F^{\prime }$ newly failed ones, we have that at least $n/c$ additional tasks get checkpointed in this attempt. Thus, such an attempt can happen at most $c$ times before all $n$ parts are checkpointed for this epoch.

In the second case, we have that $F^{\ast }\le n-F$. Recall that each part that is not yet checkpointed is now attempted to be checkpointed by a multiplicity of $mult$ or $mult-1$ nodes, where $mult=\lceil \frac{n-F}{F^{\ast }}\rceil \ge 1$. There are two possible sub-cases based on how the value of $F^{\prime }$ relates to the remaining number of allowed failures $F_{remain}=(\frac{c-1}{c})\cdot n-F$. It holds that either $F^{\prime }\ge F_{remain}\cdot \frac{1}{2}$ or . The former case can happen at most $\log ((\frac{c-1}{c})\cdot n)=O(\log n)$ times before $F_{remain}$ drops to 0.

Thus, suppose that the latter case happens in an attempt. If there is a single batch because , then all of the batch is performed by all of these nodes, and hence must succeed because at least one of them (at least $n/c$ of them) is non-faulty.

Otherwise, since $x$ is the remainder of dividing $n-F$ by $F_{batch}^{\ast }$, we have $x\le F_{batch}^{\ast }-1$. Thus, the actual number of nodes that are successful in checkpointing the tasks they are now in charge of is at least $n-F-F^{\prime }-x$. Possibly, every $mult=\lfloor (n-F)/F_{batch}^{\ast }\rfloor$ of them are performing the same batch, but even in this worst case, the number of distinct newly checkpointed batches is at least $(n-F-F^{\prime }-x)/mult$. Note that with the notation of $x$, we have that $mult=(n-F-x)/F_{batch}^{\ast }$. Further, it holds that $F_{batch}^{\ast }=\max \{\lfloor F^{\ast }/(3c)\rfloor ,1\}\le \frac{n}{3c}\le (n-F)/3$, where the first inequality is since , and the second is since $n/c\le n-F$ because the number of non-faulty nodes can never go below $n/c$.

We bound this number of newly checkpointed batches $(n-F-F^{\prime }-x)/mult$ in terms of the total number of remaining batches $F_{batch}^{\ast }$, as follows. We have that:

Since , and by plugging $F_{remain}=(\frac{c-1}{c})n-F$, we get:

Further simple algebraic manipulations give:

Removing the $\frac{n/c}{n-F}$ term from the nominator only decreases the value of the expression, as well as using $x\le F_{batch}^{\ast }-1$. We thus have:

Since $\frac{n-F}{F_{batch}^{\ast }}\ge 3$, we finally have:

This yields that after this subcase, the number of batches to be checkpointed drops from $F_{batch}^{\ast }$ to at most $(1/4)\cdot F_{batch}^{\ast }$. This implies that this can happen at most $O(\log n)$ times before all $n$ parts are checkpointed.

Thus the algorithm has all the parts checkpointed in $O(c+\log n)$ attempts. Each attempt runs in either $O(c\cdot (n^{\zeta }+n^{\xi }))$ or $O(c^2\cdot (n^{\zeta }+n^{\xi }))$ rounds, where the latter number of rounds occurs only in the case of batching, which can happen at most $O(\log n)$ attempts. Hence, we obtain a total of $O(c^2\cdot (n^{\zeta }+n^{\xi })\log n)$ rounds per epoch. In the final epoch, the nodes checkpoint the outputs in $O(c^2{n}^{\mu }\log n)$ rounds. This is done only once, and thus incurs only an additive overhead. In total, since the depth of the circuit is $n^{\delta }$, we get a running time of $O(c^2\cdot (n^{\delta +\phi +\eta }+n^{\mu })\log n)$, where $\eta =\max \{\zeta -\phi ,\xi -\phi \}$, as claimed. $◀$

We prove the theorem by showing that there is circuit computing this function that satisfies the hypothesis of Theorem 1. To describe our circuit, we define some notation.

The matrices are split as follows: $A$ is split into $n^{1/3}\times n^{1/3}$ block matrices of equal dimension $n^{2/3}\times n^{2/3}$, where the $A_j^i$ are $n^{2/3}\times n^{2/3}$ matrices, and similarly $B$ is split into $n^{1/3}\times n^{1/3}$ block matrices of equal dimension $n^{2/3}\times n^{2/3}$ where the $B_j^i$ are $n^{2/3}\times n^{2/3}$ matrices; i.e.,

Elementary linear algebra gives us that the product $C=A\cdot B$ satisfies the equation $C_j^i={\sum }_{k\in [n^{1/3}]}{(A_k{B}^k)}_j^i$, which can be computed by a total of $(\text{\# of }k\text{ in }{A}_k,B^k)\cdot (\text{\# of }i\text{ in }{A}_k^i)\cdot (\text{\# of }j\text{ in }{B}_j^k)=n^{1/3}\cdot n^{1/3}\cdot n^{1/3}=n$ block (outer) matrix multiplications; indeed, by the definition of an outerproduct we have that ${(A_k{B}^k)}_j^i=A_k^i{B}_j^k$, which we use to more efficiently distribute the tasks, and so we have:

We define sub-blocks $A_j^i[m]$ of the blocks $A_j^i$, each of size $n^{2/3}\times n^{1/3}$, as follows: ${(A_j^i[m])}_{\mathrm{\ell }}^k:={(A_j^i)}_{\mathrm{\ell }+m{n}^{1/3}}^k$, i.e., $A_j^i[m]$ is implicitly defined by the equation . Similarly, we define subblocks $B_j^i[m]$ of the blocks $B_j^i$, each of size $n^{1/3}\times n^{2/3}$, analogously to the previous construction: ${(B_j^i[m])}_{\mathrm{\ell }}^k:={(B_j^i)}_{\mathrm{\ell }}^{k+m{n}^{1/3}}$, i.e., $B_j^i[m]$ is implicitly defined by the following equation

In particular, we have that

which by Equation 2 further implies that $C_j^i={\sum }_{k\in [n^{1/3}]}{A}_k^i{B}_j^k={\sum }_{k,m\in [n^{1/3}]}{A}_k^i[m]B_j^k[m]$. For the last layer of our circuit, we will also use the fact that