Probabilistic Group Testing in Distributed Computing with Attacked Workers
Probabilistic Group Testing in Distributed Computing with Attacked Workers
复制标题
DOI：
10.1109/isit54713.2023.10206705
复制
发表时间：
2023-05
期刊：
影响因子：
--
通讯作者：
Sarthak Jain;Martina Cardone;S. Mohajer
中科院分区：
文献类型：
--
作者：
Sarthak Jain;Martina Cardone;S. Mohajer
分布式矩阵向量积的问题被认为是，其中的服务器分配的计算任务之间的n个工作节点，其中L是妥协（但非串通），并可能返回不正确的结果。具体地说，假设受损的worker是不可靠的，也就是说，在任何给定的时间，每个受损的worker都可能分别以概率α和1−α返回错误和正确的结果。因此，测试是嘈杂的。本文提出了一种新的概率群测试方法，通过$O\left（{\frac{{L\log（n）}}{\alpha }} \right）$测试来识别不可靠/受损的工人。此外，使用所提出的组测试方法，稀疏奇偶校验码的构造和使用在所考虑的分布式计算框架的编码，解码和识别不可靠的工人。这种方法有两个明显的特点：（i）在服务器上识别L个不可靠工作者的成本可以被证明是大大低于现有的分布式计算方法，以及（ii）编码和解码功能是容易实现和计算效率。
The problem of distributed matrix-vector product is considered, where the server distributes the task of the computation among n worker nodes, out of which L are compromised (but non-colluding) and may return incorrect results. Specifically, it is assumed that the compromised workers are unreliable, that is, at any given time, each compromised worker may return an incorrect and correct result with probabilities α and 1−α, respectively. Thus, the tests are noisy. This work proposes a new probabilistic group testing approach t o identify the unreliable/compromised workers with $O\left( {\frac{{L\log (n)}}{\alpha }} \right)$ tests. Moreover, using the proposed group testing method, sparse parity-check codes are constructed and used in the considered distributed computing framework for encoding, decoding and identifying the unreliable workers. This methodology has two distinct features: (i) the cost of identifying the set of L unreliable workers at the server can be shown to be considerably lower than existing distributed computing methods, and (ii) the encoding and decoding functions are easily implementable and computationally efficient.