We consider the problem of Byzantine fault-tolerance in the peer-to-peer
(P2P) distributed gradient-descent method -- a prominent algorithm for
distributed optimization in a P2P system. In this problem, the system comprises
of multiple agents, and each agent has a local cost function. In the fault-free
case, when all the agents are honest, the P2P distributed gradient-descent
method allows all the agents to reach a consensus on a solution that minimizes
their aggregate cost. However, we consider a scenario where a certain number of
agents may be Byzantine faulty. Such faulty agents may not follow an algorithm
correctly, and may share arbitrary incorrect information to prevent other
non-faulty agents from solving the optimization problem. In the presence of
Byzantine faulty agents, a more reasonable goal is to allow all the non-faulty
agents to reach a consensus on a solution that minimizes the aggregate cost of
all the non-faulty agents. We refer to this fault-tolerance goal as
$f$-resilience where $f$ is the maximum number of Byzantine faulty agents in a
system of $n$ agents, with $f < n$. Most prior work on fault-tolerance in P2P
distributed optimization only consider approximate fault-tolerance wherein,
unlike $f$-resilience, all the non-faulty agents' compute a minimum point of a
non-uniformly weighted aggregate of their cost functions. We propose a
fault-tolerance mechanism that confers provable $f$-resilience to the P2P
distributed gradient-descent method, provided the non-faulty agents satisfy the
necessary condition of $2f$-redundancy, defined later in the paper. Moreover,
compared to prior work, our algorithm is applicable to a larger class of
high-dimensional convex distributed optimization problems.

本文研究了使用委比丘密特容错处理方式解决点对点分布式梯度下降算法中存在的非诚实代理引起的优化问题，提出了一种能够保证容错性的机制并可应用于更高维度的凸分布式优化问题。

点对点分布式梯度下降中的拜占庭容错

Byzantine Fault-Tolerance in Peer-to-Peer Distributed Gradient-Descent

This report considers the problem of Byzantine fault-tolerance in synchronous
parallelized learning that is founded on the parallelized stochastic gradient
descent (parallelized-SGD) algorithm. The system comprises a master, and $n$
workers, where up to $f$ of the workers are Byzantine faulty. Byzantine workers
need not follow the master's instructions correctly, and might send malicious
incorrect (or faulty) information. The identity of the Byzantine workers
remains fixed throughout the learning process, and is unknown a priori to the
master. We propose two coding schemes, a deterministic scheme and a randomized
scheme, for guaranteeing exact fault-tolerance if $2f < n$. The coding schemes
use the concept of reactive redundancy for isolating Byzantine workers that
eventually send faulty information. We note that the computation efficiencies
of the schemes compare favorably with other (deterministic or randomized)
coding schemes, for exact fault-tolerance.

本文研究了在基于并行随机梯度下降（parallelized-SGD）算法的同步并行学习中的拜占庭容错问题。我们提出了两种编码方案，确定性编码方案和随机编码方案，用于保证在包含最多 f 个拜占庭错误的 n 个计算单元的体系结构下实现精确容错，且其计算效率比其他编码方案都好。