  State-of-the-art machine learning models are routinely trained on large-scale
distributed clusters. Crucially, such systems can be compromised when some of
the computing devices exhibit abnormal (Byzantine) behavior and return
arbitrary results to the parameter server (PS). This behavior may be attributed
to a plethora of reasons, including system failures and orchestrated attacks.
Existing work suggests robust aggregation and/or computational redundancy to
alleviate the effect of distorted gradients. However, most of these schemes are
ineffective when an adversary knows the task assignment and can choose the
attacked workers judiciously to induce maximal damage. Our proposed method
Aspis assigns gradient computations to worker nodes using a subset-based
assignment which allows for multiple consistency checks on the behavior of a
worker node. Examination of the calculated gradients and post-processing
(clique-finding in an appropriately constructed graph) by the central node
allows for efficient detection and subsequent exclusion of adversaries from the
training process. We prove the Byzantine resilience and detection guarantees of
Aspis under weak and strong attacks and extensively evaluate the system on
various large-scale training scenarios. The principal metric for our
experiments is the test accuracy, for which we demonstrate a significant
improvement of about 30% compared to many state-of-the-art approaches on the
CIFAR-10 dataset. The corresponding reduction of the fraction of corrupted
gradients ranges from 16% to 99%.
