Probabilistic Group Testing for Distributed Matrix-Vector Products With Attacked Workers

In this work, we consider the problem of distributed matrix-vector product, where a server distributes the task of the computation among n worker nodes. In particular, it is assumed that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">T</i> matrix-vector products have to be computed, where the matrix remains constant, whereas the vector changes each time. It is assumed that <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</i> out of the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</i> workers are compromised (but non-communicating) and may return incorrect results to the task assigned to them. Moreover, these compromised workers are unreliable, that is, each compromised worker may return an incorrect and correct result with probabilities α and 1 − α, respectively, at any given time. The server aims to identify this set of unreliable compromised workers so that it can remove them from future computations. This work proposes and analyzes three probabilistic group testing schemes to achieve this: (i) a noise-level-independent non-adaptive scheme, (ii) a noise-level-dependent non-adaptive scheme, and (iii) a noise-level-dependent two-stage adaptive scheme. In particular, the third scheme is shown to be order-optimal, up to a constant multiplicative factor, for certain regimes of α and <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</i>. Using the proposed group testing schemes, sparse parity-check codes are constructed, which are used in the considered distributed computing framework for encoding, decoding, and identifying the unreliable workers. This methodology has two distinct features: (i) the computational cost of identifying the set of <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">L</i> unreliable workers at the server is considerably lower than existing distributed computing methods in the literature, and (ii) the encoding and decoding functions are computationally efficient.